圓環內隨機遊走 遍歷所有節點需要的步數的期望?
01-25
一個有n個節點的圓環,從某節點出發隨機遊走,向左向右的概率均為0.5,最終遍歷所有節點需要的步數的期望(expectation)是多少?
PS:答案我知道,而且是個很簡潔的結果,但是我不知道怎麼求解,或者如何理解能等價於另一個簡單的數學問題。
長i+2的串02111...120從2每次隨機左或右挪一格,問平均幾步走到0列個方程發現是i步
那麼等到i=n的時候就走完了,所以答案就是1到n-1求和.
之前回答得不對,仔細思考了一下過程和那個問題不一樣。這個問題要簡單得多。
定義第i個階段為已經染色的節點數等於i的情況。
已染色的節點一定是連續的;在第i個階段開始,當前位置一定在被染色的節點串的邊界。求從第i階段進入第i+1階段期望步數:等價於把所有沒被染色的節點看成一個節點,有i+1個節點形成的環,從某個節點出發,到達該節點右側節點需要的期望步數;等價於從i+1個節點形成的環中的某個節點出發,回到自身的期望步數減一。(因為第一步一定會到達一個相鄰節點,由於對稱性,接下來的期望步數和上一個問題等價)而最後一個問題的期望步數就是i+1。
因為隨機過程里有個定理保證,馬爾可夫鏈某個狀態的平均返回時間等於穩態概率的倒數。
這個定理可以這麼理解。假設我們把上面最後一個等價問題模擬N步,N非常大趨近於無窮。那麼某個節點被訪問的次數大約是N/k次(有k=i+1個節點),那麼相鄰兩次訪問的平均間隔等於所有的平均間隔求和(約等於N),除以訪問間隔數(約等於N/k),結果約等於k,在取極限後等於k。倒推回去,第i階段到i+1階段需要i步,總共就需要1加到n-1步。
首先你要知道如何計算簡單隨機遊走從1出發,碰到0或k的時間的期望E_k。(這個直接列方程或者用鞅都很好算)
然後把這個問題按照第k次到達新的節點的時刻T_k分成n段。從第k個新到達的節點到第k+1個新到的節點所需的時間和第一段的問題等價。(詳細解釋見評論)這個問題有個標準的名字,叫cover time。應該足夠你尋找參考文獻了。
接著@張雨萌 的答案繼續。 假設n個節點的圓環,最終遍歷所有節點需要的步數的期望是。
即
。
推薦閱讀: