環形隨機傳遞帽子問題？
6個人a,b,c,d,e,f坐成環形，從a開始傳遞帽子，向左向右傳遞的可能性分別是1/2，一旦所有人都有傳遞到過這個帽子，傳遞停止，問最後一個被傳遞到帽子的人最可能是誰？
按理說應該是d吧？但是如何證明呢？還有是他的概率能算出來嗎？最可能傳遞次數能算出來嗎？
翻譯一下這道題目：
有一個隨機過程，狀態集合是：【已訪問過的節點集合】 和 【當前所處的節點】的笛卡爾積，例如起始狀態是，如果 a 第一次傳遞時把帽子傳給了 b ，就到達了狀態
；如果此時 b 再把帽子傳回 a ，就到達了狀態
。如果最後一個接受帽子的人是d，對應於狀態
。
狀態集合的基數上界是（實際可行的狀態只有
個），題目是要求從起始狀態到達每個吸收狀態的吸收概率 和 首達時間的分布。寫出狀態轉移矩陣後列線性方程組可解。
只算了一下最終停止在各點的概率： P（b）=P（c）=P（e）=P（f）=P（d）=1/5。也可能不對，畢竟我是個學渣orz...
獻醜呈上步驟吧，錯了也請大家指正：
首先介紹一個會用到的結論：
考慮一個一維的對稱隨機遊動，起點為原點，在P、-Q處各有一個吸收壁（P、Q為正整數）
那麼粒子最終被P處吸收的概率為Q/(P+Q),Q處吸收的概率為P/(P+Q)。
把六個人看成一個六邊形，為了求最終停止在某點的概率，就從這一點把六邊形剪開，構成一個七點連成的線段。比方說求P(d)，我們就考慮d-e-f-a-b-c-d。
直接應用上面的結論，我們得到P（b）= P（f）=1/6+1/5*1/6=1/5。
然後考慮P（c）。我們寫出線段：c-d-e-f-a-b-c。a點出發，在被吸收之前，遊動子需要遍歷d-e-f-a-b。下一步，遊動子要麼到b，等價於b-c-d-e-f-a-b，要麼到f，等價於d-e-f-a-b-c-d。必須強調一下這種等價的合理性：不論是在b或者f，為了遍歷，遊動子必需回頭穿過a點，所以可以看作a點沒被移動到，因此等價是合理的。
以此類推，我們可以寫出方程組：P（c）= P（d）/2+ P（b）/2；P（d）= P（c）/2+ P（e）/2；P（e）= P（d）/2+ P（f）/2。
這樣就可以解出各處的概率了。
然後我就發現我的過程明明可以簡化成兩種不同的解法...
解法一：大體跟上面一致，但是不用先計算P（b）= P（f）=1/6+1/5*1/6=1/5。只需要P（b）= P（f）以及各概率和為1，這樣就寫出了n-1個方程，可以解出n-1個位置的概率了。
解法二：重複利用計算P（b）= P（f）=1/6+1/5*1/6=1/5的思路。
事實上，考慮起點為零點的對稱隨機遊動，在k和k-N處各有一個吸收壁。要求遊動子在被吸收之前遍歷兩個吸收壁之間的點。
這種遍歷只有兩種可能：先到k-1再到k+1-N；或者反過來。
前者相當於前後兩個隨機遊動：原點出發，k-1和k+1-N有兩個吸收壁並且被k-1吸收，然後再出發，k和k+1-N兩個吸收壁被k+1-N吸收。k-1/N-2*1/N-1。
等效地求出另一半概率，最後和為1/N-1。
這是一個n-cycle上的隨機行走，在每個點上停止的概率都是1/n，用簡單隨機行走的性質可以推出，這個問題在mathoverstack也有討論了，我就不抄答案了，有興趣的可以自己看一下Random walk on $n$-cycle。
所需次數的期望就是Coverimg time，等於n(n-1)/2，參見Markov Chains and Mixing Times Example11.1（鏈接如下），不過題主問得好像是這個分布的Mode，我就不曉得了，或許可以強行算一下，不過我想睡覺了，以我對離散分布的大致印象來看，Mode估計就是這個期望了。
http://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf#page159
前一個問題其實是這本書的Exercise6.9
PS:一個題外話，曾經有個兄弟面Quant在線筆試題目就有這個。為什麼我知道呢，因為當時我和另外兩個兄弟花了三個小時幫他差不多做完了。。。於是乎他拿到了面試的資格，面試官告訴他，本來人已經招滿了，但是他筆試成績實在太突出就破例面了他，當然結果是他跪的體無完膚。。。
- 第一問: 停止位置是除了a之外的所有點,且概率相同
第二問: Cover Times Distribution
圓環內隨機遊走 遍歷所有節點需要的步數的期望？
解矩陣這個你們比我擅長, 僕行列解苦手, 我就編程解了...
CoverTime[M_,i_]:=Module[{Start,Roads,Ex,Si},
Start=UnitVector[Length@M,i];
Roads=Subsets[DeleteCases[Range@Length[M],i]][[2;;-1]];
Ex=PDF[FirstPassageTimeDistribution[DiscreteMarkovProcess[Start,M],#],k]/@Roads;
Si=If[Length[#]~Mod~2==1,1,-1]/@Roads;
Total[Ex*Si]];
M={{0,1/2,0,0,0,1/2},{1/2,0,1/2,0,0,0},{0,1/2,0,1/2,0,0},{0,0,1/2,0,1/2,0},{0,0,0,1/2,0,1/2},{1/2,0,0,0,1/2,0}};
ff = FullSimplify[CoverTime[M, 1], k [Element] Integers]
這個程序很眼熟? 沒錯,就是十二星座找男友那個題扒下來的...
程序輸出為:
期望就是 15 啦...
這個和 @張一釗 的程序跑出來是一樣的
補充一個: n 步後在k點的概率為:
我筆記本上就寫了個 Herbert Kociemba...大概表示是他得出的意思...
這就是個馬爾可夫過程啊。回去寫個程序跑一跑。
關於最可能傳遞次數，簡單搜索就能得到結果：
5 0.0625000000
6 0.0312500000
7 0.0781250000
8 0.0468750000
9 0.0781250000
10 0.0507812500
11 0.0712890625
12 0.0483398438
13 0.0617675781
14 0.0429687500
15 0.0517578125
16 0.0366210938
17 0.0423736572
18 0.0303421021
19 0.0341072083
20 0.0246391296
21 0.0271034241
22 0.0197114944
23 0.0213243961
24 0.0155900717
25 0.0166457295
26 0.0122203827
27 0.0129113197
28 0.0095107555
29 0.0099629797
30 0.0073591787
31 0.0076551633
32 0.0056673763
33 0.0058611007
34 0.0043473945
35 0.0044741887
顯然傳遞次數越多概率越小，所以只算了前幾個。
可以看出概率最大的傳遞次數為7和9。設已經到達了4個點，由於對稱性，目標點隨意取一個，此處取右邊那一個。
a b c d 0 1設從4個點開始成功轉移到目標點的概率分別為a, b, c, d。由狀態轉移，得以下方程：a = 1/2 * 1 + 1/2 * b;b = 1/2 * a + 1/2 * c;c = 1/2 * b + 1/2 * d;
d = 1/2 * c + 1/2 * 0;不難看出0, d, c, b, a, 1為等差數列，解為1/5, 2/5, 3/5, 4/5。設已經到達了3個點，由於對稱性，目標點有兩種。
1)a b c0 0 1則0, c, b, a, 4/5為等差數列，解為1/5, 2/5, 3/5。2)a b c0 1 0
則1/5, c, b, a, 1/5為等差數列，解為1/5, 1/5, 1/5。設已經到達了2個點，由於對稱性，目標點有兩種。
1) a b0 0 0 1則0, b, a, 3/5為等差數列，解為1/5, 2/5。2) a b0 0 1 0則1/5, b, a, 1/5為等差數列，解為1/5, 1/5。
設已經到達了1個點，由於對稱性，目標點有3種。
1) a0 0 0 0 1則0, a, 2/5為等差數列，解為1/5。2) a0 0 0 1 0則1/5, a, 1/5為等差數列，解為1/5。3)
a0 0 1 0 0則1/5, a, 1/5為等差數列，解為1/5。所以每個點停止的概率都是1/5。對於第一問
a 0.0
b 0.008333333333333333
c 0.20000000000000004
d 0.5833333333333334
e 0.20000000000000004
f 0.008333333333333333
對於第二問，最可能的傳遞次數為7次和9次，概率都為0.078125
0 0.0
1 0.0
2 0.0
3 0.0
4 0.0
5 0.0625
6 0.03125
7 0.078125
8 0.046875
9 0.078125
10 0.05078125
11 0.0712890625
12 0.04833984375
13 0.061767578125
14 0.04296875
15 0.0517578125
16 0.03662109375
17 0.0423736572265625
18 0.03034210205078125
19 0.034107208251953125
20 0.024639129638671875
21 0.027103424072265625
22 0.01971149444580078
23 0.02132439613342285
24 0.015590071678161621
25 0.016645729541778564
26 0.012220382690429688
27 0.012911319732666016
渣代碼
PERSON_CNT = 6
left = [[0.0 for _ in range(PERSON_CNT)] for _ in range(PERSON_CNT)]
right = [[0.0 for _ in range(PERSON_CNT)] for _ in range(PERSON_CNT)]
def update(mat, i, j, delta):
j = ((j % PERSON_CNT) + PERSON_CNT) % PERSON_CNT
mat[i][j] += delta
left[0][0] = 1.0
for i in range(1, 6):
left[0][i] = 0.0
for d in range(0, 5):
for i in range(6):
update(left, d + 1, i - 1, left[d][i] / (d + 2))
update(right, d + 1, i, left[d][i] * float(d + 1) / (d + 2))
update(left, d + 1, i - 1, right[d][i] * float(d + 1) / (d + 2))
update(right, d + 1, i, right[d][i] / (d + 2))
ans = [0.0 for _ in range(PERSON_CNT)]
for i in range(6):
ans[i] += left[PERSON_CNT-1][i]
ans[(i+PERSON_CNT-1) % PERSON_CNT] += right[PERSON_CNT-1][i]
for i in range(6):
print("abcdef"[i], ans[i])
this_status = [[[0.0 for _ in range(PERSON_CNT)] for _ in range(PERSON_CNT)] for _ in range(PERSON_CNT)]
this_status[0][0][0] = 1.0
for t in range(1000):
next_status = [[[0.0 for _ in range(PERSON_CNT)] for _ in range(PERSON_CNT)] for _ in range(PERSON_CNT)]
# print(t =, t)
for d in range(PERSON_CNT - 1):
for i in range(PERSON_CNT):
for j in range(PERSON_CNT):
val = this_status[d][i][j]
# going right
next_j = (j + 1) % PERSON_CNT
next_i = i
if j != (i + d) % PERSON_CNT:
next_d = d
else:
next_d = d + 1
next_status[next_d][next_i][next_j] += val * 0.5
# going left
next_j = j - 1 if j != 0 else j - 1 + PERSON_CNT
if j != i:
next_i = i
next_d = d
else:
next_i = next_j
next_d = d + 1
next_status[next_d][next_i][next_j] += val * 0.5
d = PERSON_CNT - 1
prob = 0
for i in range(PERSON_CNT):
for j in range(PERSON_CNT):
prob += this_status[d][i][j]
tot_prob += prob
if 1 - tot_prob &< 0.078125:
break
print(t, prob)
this_status = next_status
我理解是個隨機過程，而且是個馬爾科夫鏈，那解出來就很容易了。
運行100萬次，結果如下
using System;
class Program
{
static int index = 0;
static void Main(string[] args)
{
int[] unit = { 1, 0, 0, 0, 0, 0 };//共6人
int times = 1;//運行次數
int deliverTime = 0;//傳遞次數
int[] count = { 0, 0, 0, 0, 0, 0 };//每人獲得帽子次數
int[] deliver=new int[41];//傳遞次數統計
do
{
deliverTime++;
int x = newRandom();
if (x == 1)
indexPlus(unit);
else
indexMinus(unit);
if (judgemnt(unit))
{
times++;
count[index]++;
if (deliverTime &>= 40)
deliver[40]++;
else
deliver[deliverTime]++;
for (int i = 0; i &< 6; i++)
unit[i] = 0;
unit[0] = 1;
index = 0;
deliverTime = 0;
}
} while (times&<=10000);
for (int i = 0; i &< 6; i++)
Console.WriteLine("第"+(i+1)+"人得到"+count[i]+"次帽子");
for (int i = 6; i &< 40; i++)
Console.WriteLine("傳遞" + (i + 1 &<= 10 ? " ":"") + i + "次出現的次數為 " + deliver[i]);
Console.WriteLine("40次以上的出現次數為 "+deliver[40]);
}
static int newRandom()
{
Random x = new Random(Guid.NewGuid().GetHashCode());
int a = x.Next(1,3);
return a;
}
static void indexMinus(int[] a)
{
if (index == 0)
{
index = 5;
a[index] = 1;
}
else
{
index--;
a[index] = 1;
}
}
static void indexPlus(int[] a)
{
if(index==5)
{
index = 0;
a[index] = 1;
}
else
{
index++;
a[index] = 1;
}
}
static bool judgemnt(int[] a)
{
int sum = 0;
foreach (int x in a)
sum += x;
if (sum == 6)
return true;
else
return false;
}
}
推薦閱讀：
※喝飲料或者吃零食中一等獎是怎樣的體驗？
※上海一個公司所有女員工配偶均為警察的概率是多少？
※「剪刀石頭布」遊戲中，出什麼勝算最大？
※兩根長度 1 的線段完全落入單位正方形內，求相交概率？
※爐石傳說中，利用新卡逐星得到的猿猴在牌庫中的倒數第幾張的期望值是多少？