作者stimim (qqaa)
看板puzzle
標題Re: [問題] 通過機率
時間Wed Jan 27 18:33:56 2010
首先，假設一開始的時候所有的門都是關著的，並且，人站在第一個按鈕的位置。
當一個人按下某一個按鈕後，他可能站在：{A,B,C} 其中一個按鈕上
而3個門的狀況可能是：{(0,0,0), (0,0,1), ... , (1,1,1)}等八種(0為關, 1為開)
於是便有 24 種狀況
A 0 0 0 B 0 0 0 C 0 0 0
A 0 0 1 B 0 0 1 C 0 0 1
A 0 1 0 B 0 1 0 C 0 1 0
A 0 1 1 B 0 1 1 C 0 1 1
A 1 0 0 B 1 0 0 C 1 0 0
A 1 0 1 B 1 0 1 C 1 0 1
A 1 1 0 B 1 1 0 C 1 1 0
A 1 1 1 B 1 1 1 C 1 1 1
針對每一種狀況，都會有一個過關的機率，其中，有一些的機率是很簡單的：
{A,B,C} 0 0 0 是無法繼續遊戲的，故過關機率為0
C - - 1 已經過關了，故機率為 1
如果，你所佔的位置，前後的門都是關起來的，哪也無法繼續，
綜合以上幾點，可以先找到某一些狀態的通過機率
A 0 0 0
0 B 0 0 0
0 C 0 0 0
0
A 0 0 1
0 B 0 0 1
0 C 0 0 1
1
A 0 1 0
0 B 0 1 0 C 0 1 0
A 0 1 1
0 B 0 1 1 C 0 1 1
1
A 1 0 0 B 1 0 0 C 1 0 0
0
A 1 0 1 B 1 0 1 C 1 0 1
1
A 1 1 0 B 1 1 0 C 1 1 0
A 1 1 1 B 1 1 1 C 1 1 1
1
現在還剩下12格尚未填入，對於每一個狀態，都有他可能的下一個狀態，
我假設玩家會優先選擇向前走，如果無法向前才向後移動
而當移動到下一個按鈕後，立刻按下該按鈕，會有3個可能的下一個狀態
例如：A 1 0 0，玩家會走到B並按下按鈕，可能的下一個狀態為：
B 1 1 1, B 0 0 1, B 0 1 0，如果3個狀態的過關機率分別為 x, y, z，
則 A 1 0 0 的過關機率為 (x+y+z)/3 ，我們替剩下的狀態設定變數：
A 0 0 0 0 B 0 0 0 0 C 0 0 0 0
A 0 0 1 0 B 0 0 1 0 C 0 0 1 1
A 0 1 0 0 B 0 1 0
2/3 C 0 1 0
j
A 0 1 1 0 B 0 1 1
e C 0 1 1 1
A 1 0 0
a B 1 0 0
f C 1 0 0 0
A 1 0 1
b B 1 0 1
g C 1 0 1 1
A 1 1 0
c B 1 1 0
2/3 C 1 1 0
k
A 1 1 1
d B 1 1 1
h C 1 1 1 1
其中，B 0 1 0的下一個狀態可能是：C 0 0 1, C 1 1 1, C 1 0 0，過關的機率為 2/3
B 1 1 0的下一個狀態可能是：C 1 0 1, C 0 1 1, C 0 0 0, 過關的機率為 2/3
根據每個狀態的下一個可能狀態，可以得到下面的關係式：
a = h/3 + 2/9 e = k/3 + 1/3 j = h/3 + f/3
b = e/3 + 2/9 f = d/3 k = g/3 + e/3
c = g/3 + e/3 g = c/3
d = f/3 + 2/9 h = j/3 + 1/3
解上述的聯立方程式，可得：
a = 101/288 b = 22/63 c = 1/7
d = 1/4 e = 8/21 f = 1/12
g = 1/21 h = 37/96 j = 5/32
k = 1/7
如果一開始的3個門都是關著的，則當玩家按下A鈕後，可能的狀態為：
A 0 1 1 (過關的機率為 0 )
A 1 0 1 (過關的機率為 b )
A 1 1 0 (過關的機率為 c )
故過關的機率為：
(0 + 22/63 + 1/7)/3 = 31/189 ≒ 0.164021 = 16.4021%
另外，用程式模擬的結果也大約是這個數字。
如果要改成
當玩家處於B時，只要情況允許，會隨機的向前或向後，
(不考慮明明可以直接贏卻不走的狀況，那太不合常理了@@)
則就需要將上面的等是稍作修改，再解一次：
A 0 0 0 0 B 0 0 0 0 C 0 0 0 0
A 0 0 1 0 B 0 0 1 0 C 0 0 1 1
A 0 1 0 0 B 0 1 0 2/3 C 0 1 0
j
A 0 1 1 0 B 0 1 1
e C 0 1 1 1
A 1 0 0
a B 1 0 0
f C 1 0 0 0
A 1 0 1
b B 1 0 1
g C 1 0 1 1
A 1 1 0
c B 1 1 0
L C 1 1 0
k
A 1 1 1
d B 1 1 1
h C 1 1 1 1
a = h/3 + 2/9 e = k/3 + 1/3 j = h/3 + f/3
b = e/3 +
L/3 f = d/3 k = g/3 + e/3
c = g/3 + e/3 g = c/3
L = (2/3)/2 + b/2
d = f/3 + 2/9
h = (j/3 + 1/3)/2+a/2
解之，得：
a = 173/504 b = 2/7 c = 1/7
d = 1/4 e = 8/21 f = 1/12
g = 1/21 h = 61/168 j = 25/168
k = 1/7 L = 10/21
過關的機率： (b+c)/3 = 1/7 ≒ 14.2857% 比一直向前走略小
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.160.35
※ 編輯: stimim 來自: 61.228.160.35 (01/27 18:35)
1F：推 etrexetrex:跟我想的差不多只是我還沒解完 01/27 18:38