随机游走停在 0 或 3：期望步数与到 3 的概率

Random walk starting at 1

Consider a random walk starting at 1 and with equal probability of moving to the left or to the right by one unit, and stopping either at 0 or at 3.

(i) What is the expected number of steps to do so?

(ii) What is the probability of the random walk ending at 3 rather than at 0?

解析

设从位置 $\ell\in\{0,1,2,3\}$ 出发，到首次到达 $\{0,3\}$ 的步数为 $T_\ell$ ，其期望为 $t_\ell=\mathbb{E}[T_\ell]$ 。

对 $\ell=1,2$ 有递推

t_\ell=1+\frac{t_{\ell-1}+t_{\ell+1}}{2},\qquad t_0=t_3=0.

解得 $t_1=t_2=2$ ，因此

\boxed{\mathbb{E}[\text{步数}]=2}.

到达 3 的概率 $p_\ell$ 满足

p_\ell=\frac{p_{\ell-1}+p_{\ell+1}}{2},\qquad p_0=0,p_3=1.

解得 $p_1=1/3,p_2=2/3$ ，故

\boxed{\mathbb{P}(\text{终止于 }3)=\frac13}.