Re: [機統] 馬可夫鏈有一例題看不懂呢

[microball (無華之果)]

※ 引述《playmypig (玩我豬)》之銘言：
: 先說聲不好意思,例題在下面的連結:
: http://i.na.cx/YrMaZ.png
: 我不明白的地方用紅筆間了出來.
: 他說 P^(n)_aa>0 for all n, and state a 是aperiodic我是同意的.
: 但是我不明白為什麼因此也可以推論其他的states也是aperiodic.

假設是 irreducible 的馬可夫鏈，又 state a 是 aperiodic，
能證明其他 state (例如b) 也是 aperiodic 如下：

因為 state a 是 aperiodic，可以找到兩種回到 a 的路徑 (a->...->a)
(假設各有 A1, A2 步) 使得 gcd(A1,A2) = 1
又因為是 irreducible 的，存在一條從 b->a->b 的循環路徑，假設有 B 步

那麼，用以上三個路徑，可以做出另外兩個從 b-> a->...->a ->b 的循環路徑，
分別有 A1+B, A2+B 步
只要證明 gcd(A1+B, A2+B) =1 ，就代表 state b 也是 aperiodic。

用反證法，假設 gcd(A1+B, A2+B) >1，會跟 gcd(A1,A2)=1 矛盾。

: 簡單說,state c的下一步一定是state a啊, 那要回到state c那裡,
: 是起碼要2 steps...那它的period又怎可能是1呢?
: 是我對period的理解有錯嗎?
: 謝謝版友的指教.

--
這是你嗎  你要這樣的過嗎
      這是你嗎  你錯過了自己吧
            就這樣嗎  把你自己信仰  來換別人所謂的天堂
                  這是你嗎  是誰給了你框框
                      這是你嗎  把你自己都遺忘
                             你的心   畢竟是你自己的地方

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 216.165.95.79
推 playmypig   :先謝謝你的回答,我看懂了你的推論了.但我另外想問一
→ playmypig   :下就是,若說某一個state是aperiodic,有什麼快方法呢?
→ playmypig   :因為定義是P^(n)_aa>0,但我不知要算多少之n,才足夠大
→ microball   :考慮所有從 a->...->a 的路徑 (中間不經過a)
→ microball   :計算這些路徑步數的 gcd 就夠了
推 playmypig   :明白了,謝謝m大和c大的熱心指導 ^_^