標籤：

數學概率論隨機過程

圓環內隨機遊走遍歷所有節點需要的步數的期望？

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個節點的圓環,最終遍歷所有節點需要的步數的期望是 $E_n$ 。

方法一：

假設簡單隨機遊走從0出發，碰到-1或k的時間的期望為 $S_k$ ,碰到-1的概率為 $p_k$ ,碰到k的概率為 $q_k=1-p_k$ 。如果碰到-1的話，需要時間的條件期望是 $l_k$ ；如果碰到k的話需要時間的條件期望是 $r_k$ ，則 $S_k=p_k*l_k+q_k*r_k$ ， $E_n=sum_{k=1}^{n-1}{S_k}$ 。用鞅的理論可以算出

$p_k=frac{k}{k+1} ,q_k=1-p_k=frac{1}{k+1}$

我們還可以得到遞推公式以及初始條件如下：

$l_1=1$

$l_{k+1}=frac{frac{1}{2}*1+frac{1}{2}*p_k*p_{k+1}*(1+l_k+l_{k+1})}{p_{k+1}}$

$r_1=1$

$r_{k+1}=frac{frac{1}{2}*q_k*(1+r_k)+frac{1}{2}*p_k*q_{k+1}*(1+l_k+r_{k+1})}{q_{k+1}}$

先說這麼多，具體計算結果有時間接著說。

方法二：

同樣假設簡單隨機遊走 $X_n$ 從0開始，碰到-1或k為停止時刻 $au_k$ ， $E[ au_k] = S_k$ 。則

1. $X_0$ =0；

2. $P(X_{n+1}=X_n+1|X_n) = frac{1}{2}$ , $P(X_{n+1}=X_n-1|X_n) = frac{1}{2}$

顯然隨機過程 $X_n$ 為鞅過程且 $E[ au_k]<+infty$ 。

所以得出 $E[X_{ au_k}] = X_0 = 0$

即 $P(X_{ au_k}=-1)*(-1)+P(X_{ au_k}=k)*k = 0$

再由 $P(X_{ au_k}=-1)+P(X_{ au_k}=k) = 1$ 可得

$P(X_{ au_k}=-1) = frac{k}{k+1},P(X_{ au_k}=k) = frac{1}{k+1}$

容易證明 $Y_n = X_n^2-n$ 同樣為鞅過程，

所以 $E[Y_{ au_k}] = Y_0 = 0$

即 $E[X_{ au_k}^2- au_k]=0$

所以 $E[ au_k] = E[X_{ au_k}^2] = P(X_{ au_k} = -1)*(-1)^2+P(X_{ au_k} = k)*k^2 = frac{k}{k+1}*1+frac{1}{k+1}*k^2 =k$

即 $S_k = k$ 。

對於更一般的情況，假設簡單隨機遊走 $X_n$ 從0開始，碰到 $-a$ 或 $b$ 為停止時刻 $au$ ，則 $E[ au] = ab$ 。

綜上所述

$E_n=sum_{k=1}^{n-1}{S_k} = sum_{k=1}^{n-1}k = frac{n(n-1)}{2}$ 。

方法二應該是@張雨萌所說的鞅的方法。

推薦閱讀：

※布朗運動首次擊中a的時刻的期望？
※Redistribution Group

TAG:數學 | 概率論 | 隨機過程 |