剛剛想到所有期望值形式上的算法。還是以三乘三為例 ａｂｃ
ｄｅｆ
ｇｈｉ
馬可夫矩陣 起始狀態矩陣 (以b為例)
Ａ= Ｓ=
0 1/3 0 1/3 0 0 0 0 0 a 0
1/2 0 1/2 0 1/4 0 0 0 0 b 1
0 1/3 0 0 0 1/3 0 0 0 c 0
1/2 0 0 0 1/4 0 1/2 0 0 d 0
0 1/3 0 1/3 0 1/3 0 1/3 0 e 0
0 0 1/2 0 1/4 0 0 0 1/2 f 0
0 0 0 1/3 0 0 0 1/3 0 g 0
0 0 0 0 1/4 0 1/2 0 1/2 h 0
0 0 0 0 0 1/3 0 1/3 0 i 0
在程式的例子中，每到終點(這裡以h為例)的機率不為零時，便
1.乘上目前步數 2.加到期望值 3.然後再將i 歸零。
事實上在3x3或5x5的例子中，零與非零輪流出現，因此這些操作每兩次就得進行一次。
例如第一次是取 (Ａ^2)Ｓ 結果中的 h = 1/12
[POINT] 只把h歸零而其他機率不變的方法是乘上矩陣Ｅ (E for Elimination)
Ｅ=
0 1/3 0 1/3 0 0 0 0 0 a
1/2 0 1/2 0 1/4 0 0 0 0
0 1/3 0 0 0 1/3 0 0 0 .
1/2 0 0 0 1/4 0 1/2 0 0 .
0 1/3 0 1/3 0 1/3 0 1/3 0 .
0 0 1/2 0 1/4 0 0 0 1/2
0 0 0 1/3 0 0 0 1/3 0
0 0 0 0 0 0 0 0 0 h
0 0 0 0 0 1/3 0 1/3 0 i
跳結論，b→i的期望值
= 2 (Ａ^2)Ｓ + 4 (ＡＥ)(Ａ^2)Ｓ + 6 (ＡＥ)^2 (Ａ^2)Ｓ + ... 即
＿＿∞
╲
／ (2n+2) (ＡＥ)^n (Ａ^2)Ｓ 的i那一項
￣￣n=0
然後這是個無窮級數 令原式=EXP, ＡＥ= Ｐ, (Ａ^2)Ｓ = Ｓ'
EXP /2 = (Σ n P^n + Σ P^n) (Ａ^2)Ｓ
_1 2 _1
=[ ((I-P) ) P + (I-P) P ] (Ａ^2)Ｓ 媽呀，我竟然瘋到在PTT打數學式。
我們要的答案還是i那一項
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
這樣應該就可以直接算每種狀態的期望值(精確，還一定是有理數)，然後isoneval大
的125X ......管他多少種，只要能有效列舉就一定能算出來。
不過我手邊沒有矩陣運算的工具XD WOW 25階方陣耶，我連四階以上反矩陣怎麼算都忘了
先在這裡掉隊啦。不知道utomaya大有沒有進展~~~
--
All Comments