作者Desperato (Farewell)
看板Math
標題Re: [機統] 時間期望值
時間Fri Jan 25 02:15:49 2019
※ 引述《altecgp125 (Wheat_Black_Tea)》之銘言:
: 題目:
: 給定一個正三角形S,其頂點A1,A4,A6以及其邊長中點A2,A3,A5。現有一螞蟻從A1節點出
: 發,欲從每個節點往相鄰節點(不包含起點節點)之機率均等,且時間皆會花費一分鐘,
: 過程中每個節點可能會重複被螞蟻經過,試問:螞蟻從A1走到A6就停止的時間期望值?
: Q:本身想用基本土方法以時間2、3、4......分鐘分類求各別機率,但苦於找不到規律!
: 先謝謝高手指點迷津
(1) 假設圖長以下這個樣子
A1
/ \
A2-A3
/ \/ \
A4-A5-A6
(2) 假設螞蟻不走回頭路
例如從 A1 走到 A3 後只會在 A2, A5, A6 三選一
若他選了 A2 接下來也只會在 A1, A4, A5 三選一
由於螞蟻走路需要考慮方向問題,本題的 state 會非常多
我原本的作法是打算拆階段減少 state
但做到一半卡住懶了XD 決定硬幹全 state
考慮以下 8 個 state
G: A3->A6, A5->A6
L: A3->A5, A5->A3
A: A1->A3, A4->A5
B: A3->A2, A5->A2
C: A2->A1, A2->A4
D: A2->A3, A2->A5
E: A3->A1, A5->A4
F: A1->A2, A4->A2
由於對稱,我把一些 state 算在一起,不然就 16 個 state 了
設 a = 1/3, b = 2/3, 則機率的轉移矩陣為 (G 那行會是 0,因為沒有下一步)
G L A B C D E F
G [ a a a ]
L [ a a ]
A [ 1 ]
T = B [ a a ]
C [ b a ]
D [ a b ]
E [ a a ]
F [ 1 ]
或者重新寫一個的話
G C A D L B E F
G [ a a a ]
C [ b a ]
A [ 1 ]
T = D [ a b ]
L [ a a ]
B [ a a ]
E [ a a ]
F [ 1 ]
好吧,沒救了,就這樣。設 c = 1/2
初始向量即第一步為 v = v_1 = [ 0 0 c 0 0 0 0 c ]^t
第 n 步為 v_n = T^(n-1) v_1
以下假設 lim(n->inf) T^n = O
且 lim(n->inf) nT^n = O
期望值 E = v + 2Tv + 3TTv + 4TTTv + ...
TE = Tv + 2TTv + 3TTTv + ...
(I-T)E = v + Tv + TTv + TTTv + ...
T(I-T)E = Tv + TTv + TTTv + ...
(I-T)(I-T)E = v
E = CCv, C = (I-T)^(-1)
於是我找到變態計算機啦ow o
[ 1 1 1 1 1 1 1 1 ] d 27/16 j 13/16
[ 0 d e f g n m m ] e 11/16 k 7/16
[ 0 d d f g n m m ] f 9/16
C = [ 0 f f d g m n n ]
[ 0 g g g h g g g ] g 3/4 m 15/16
[ 0 j j k g d f f ] h 3/2 n 21/16
[ 0 k k j g f d e ]
[ 0 k k j g f d d ]
提示:Matrix Reshish 已加入我的最愛!
https://matrix.reshish.com/inverse.php
選項有 100x100 的 matrix,不過 25x25 就佔滿了其實,開太大會lag
比 WolframAlpha 好用一百倍啊XD
因此 Cv = [ 1 j n m g e f p ] p 17/16
CCv 的第一項 = (16+13+21+15+12+11+9+17)/16 = 57/8
所以答案是 57/8 分鐘
概念上是這樣啦,根本搞不清楚有沒有算錯XD
--
嗯嗯ow o
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.41
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1548353755.A.4A1.html
推 Vulpix : 答案好像差不多是10,拿六個點算馬可夫鏈。 01/25 03:22
→ Desperato : 問題是我的假設無法用6點來算 01/25 03:43
推 Vulpix : 是那個"不包含起點"嗎?那真的是會比較煩沒錯。 01/25 03:56
推 altecgp125 : 若A1-A2允許重複來回是不是好算很多 01/25 13:05
→ Desperato : 是 因為那樣就只有6個state 事實上可能連markov c 01/25 14:00
→ Desperato : hain都不用 幾條高中列式就解決了 01/25 14:00
→ Desperato : 啊 對稱後只有4個 扣掉終點後只有3個 這已經是可以 01/25 14:01
→ Desperato : 手算反矩陣的等級了 01/25 14:01