推 madokamagika: 感謝回答 02/23 06:10
推 XII : 一般而言,若丟出k點的機率是p(k) (k=1,..,n) 02/23 08:53
→ XII : 則lim p_k = 1/(p(1)+2p(2)+3p(3)+..+np(n)) 02/23 08:55
※ 引述《madokamagika (まどか☆マギカ)》之銘言：
: 玩遊戲時想到的題目 不太確定這算不算機率
: 現在有一個n面骰
: 每擲一次就依擲出點數前進
: 現在有一個距離起點極遠的格子
: 試問在這過程中剛好停留此格而不是直接穿越的機率是多少
: 用excel拉答案應該是 2/(n+1)
: 但想不太出算法
設 p_k 為踩中第 k 格的機率，從第 0 格開始
因此 p_0 = 1, p_k = 0 if k < 0
令 a = 1/n, 則可以得到遞迴式
p_1 = a p_0
p_2 = a p_0 + a p_1
p_3 = a p_0 + a p_1 + a p_2
...
p_(n-1) = a p_0 + a p_1 + a p_2 + ... + p_(n-2)
n-1
p_(k+n) = a sum p_(k+i)
k=0
令 v_k = (p_(k-n+1), p_(k-n+2), ..., p_(k-1), p_k)
可以得到矩陣 v_(k+1) = T v_k, k >= 0
[ 1 ]
[ 1 ]
T = [ ... ]
[ 1 ]
[ 1 ]
[ a a a...a a ]
可得 T 的特徵方程式為 f_T(t) = (1/n) (n t^n - t^(n-1) - ... - t - 1)
顯然 t = 1 是其中一根。
可以證明若 t 是複數，|t| >= 1 且 f_T(t) = 0，則 t 只能 1
以及 f_T(t)/(t-1) 顯然係數全正
因此 T 的特徵值為 1 = t_1, t_2, ..., t_n
其中 |t_i| < 1 if i = 2, 3, ..., n
所以 T 的 Jordan form 是 [ 1 0 ], K 對角線元素絕對值皆小於 1
[ 0 K ]
因此 R = lim_(s->inf) T^s 會有 rank R = 1
現在考慮 T^t 是一個轉移矩陣，每行總和為 1
且對所有 (T^t)^s 仍然是一個轉移矩陣
因此 R^t 還是轉移矩陣，由 rank R^t = 1 可得 R^t = [z z ... z]
顯然 R^t z = z 且 T^t z = z, 直接硬幹 z = (z_1, z_2, ..., z_n) 可得
z_1 = a z_n = a z_n
z_2 = z_1 + a z_n = 2 a z_n
z_3 = z_2 + a z_n = 3 a z_n
...
z_n = z_(n-1) + a z_n = n a z_n
且 z_1+z_2+...+z_n = 1, 得到 z_n = 2/(n+1) = b，因此
[ 1ab 2ab ... b ]
[ 1ab 2ab ... b ]
R = [ 1ab 2ab ... b ]
[ ... ... ... ...]
[ 1ab 2ab ... b ]
[ 1ab 2ab ... b ]
現在 v_0 = (0, 0, ..., 0, 1)
可得 R v_0 = (b, b, ..., b)，因此 b = 2/(n+1) 是答案沒錯
=============================================================
直觀的看法是，每走一步平均會跳 (n+1)/2 格
所以每一格平均被踩中的機率是 p = 2/(n+1)
雖說如此，即使要證明 p_k 會趨近於定值都不是很容易
嚴謹的情況還是用矩陣會好一點，雖然很煩
--
嗯嗯ow o
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.5
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1550859091.A.B4E.html