随机游走停在 0 或 3

与上一题相同。

$$\boxed{\mathbb{E}[\text{步数}]=2},\\qquad \boxed{\mathbb{P}(\text{终止于 }3)=\frac13}.$$

---

英文解析

Denote by $X_{n}^{\ell}$ the position of the random walk at time $n$ , where the superscript refers to the starting position of the walk; for example, $X_{0}^{\ell} = \ell$ . In this question, we are concerned with $X_{n}^{1}$ . For a random walk starting at $\ell \in \{0,1,2,3\}$ , denote by $T_{\ell}$ the number of steps taken by the random walk in order to reach either 0 or 3 for the first time, and by $t_{\ell} = E\left[T_{\ell}\right]$ the expected number of steps.

(i) We are looking to find $t_1$ . We derive a recurrence relation among the $t_{\ell}$ 's as follows: for $\ell = 1,2$

$$\begin{array}{r l} & {t_{\ell} = E\left[T_{\ell}\right]}\\ & {\quad = E\left[T_{\ell}\mid X_{1}^{\ell} = \ell -1\right]\cdot P\left(X_{1}^{\ell} = \ell -1\right)}\\ & {\qquad +E\left[T_{\ell}\mid X_{1}^{\ell} = \ell +1\right]\cdot P\left(X_{1}^{\ell} = \ell +1\right)}\\ & {= E\left[1 + T_{\ell -1}\right]\cdot P\left(X_{1}^{\ell} = \ell -1\right)}\\ & {\qquad +E\left[1 + T_{\ell +1}\right]\cdot P\left(X_{1}^{\ell} = \ell +1\right)}\\ & {= (1 + t_{\ell -1})\cdot \frac{1}{2} +(1 + t_{\ell +1})\cdot \frac{1}{2}} \end{array}$$

where the following identities were used to derive (3.224) and (3.225):

$$\begin{array}{l}{{E\left[T_{\ell}\mid X_{1}^{\ell}=\ell-1\right]=E\left[1+T_{\ell-1}\right]}}\\ {{E\left[T_{\ell}\mid X_{1}^{\ell}=\ell+1\right]=E\left[1+T_{\ell+1}\right].}}\end{array}$$

Note that (3.227) and (3.228) follow from the fact that, starting at $\ell$ , once the random walk took its first step to $\ell - 1$ (or $\ell +1$ ), it becomes equivalent to a random walk starting afresh at $\ell - 1$ (or $\ell +1$ ). The plus 1 term on the right hand side of (3.227) and (3.228) accounts for the first step.

Since $t_0 = t_3 = 0$ , by letting $l = 1$ and then $l = 2$ in (3.226), we obtain the

following linear system for $t_1$ and $t_2$ :

$$\begin{array}{c}t_1 = \frac{1 + t_0}{2} + \frac{1 + t_2}{2} \\ = \frac{1}{2} + \frac{1 + t_2}{2} \end{array}$$ $$\begin{array}{c}t_2 = \frac{1 + t_1}{2} + \frac{1 + t_3}{2} \\ = \frac{1 + t_1}{2} + \frac{1}{2}. \end{array}$$

Thus, $t_1 = 2$ and $t_2 = 2$ .

We conclude that the expected number of steps before stopping is 2.

(ii) Denote by $p_\ell$ the probability that the random walk reaches 3 before it reaches 0 when its position is at $\ell$ , for $\ell \in \{0,1,2,3\}$ . We need to find $p_1$ . Denote by $\tau_0^\ell$ the first time the walk reaches O when starting at $\ell$ , and by $\tau_{3}^{\ell}$ the first time the walk reaches 3 when starting at $\ell$ . We derive a recurrence relation for the $p_\ell$ 's as follows: for $\ell = 1,2$

$$\begin{array}{r l} & {p_{\ell} = P\left(\tau_{3}^{\ell}< \tau_{0}^{\ell}\right)}\\ & {\quad = P\left(\tau_{3}^{\ell}< \tau_{0}^{\ell}\mid X_{1}^{\ell} = \ell +1\right)P\left(X_{1}^{\ell} = \ell +1\right)}\\ & {\quad \quad +P\left(\tau_{3}^{\ell}< \tau_{0}^{\ell}\mid X_{1}^{\ell} = \ell -1\right)P\left(X_{1}^{\ell} = \ell -1\right)}\\ & {\quad = P\left(\tau_{3}^{\ell +1}< \tau_{0}^{\ell +1}\right)P\left(X_{1}^{\ell} = \ell +1\right)}\\ & {\quad \quad +P\left(\tau_{3}^{\ell -1}< \tau_{0}^{\ell -1}\right)P\left(X_{1}^{\ell} = \ell -1\right)}\\ & {\quad = \frac{1}{2}\cdot p_{\ell +1} + \frac{1}{2}\cdot p_{\ell -1},} \end{array}$$

because the random walk is equally likely to move to the left or to the right and, once it moved, the random walk starts afresh.

Since $p_0 = 0$ and $p_3 = 1$ , by letting $l = 1$ and then $l = 2$ in (3.229), we obtain the following linear system for $p_1$ and $p_2$ :

$$\begin{array}{l} p_1 = \frac{p_0}{2} + \frac{p_2}{2} = \frac{p_2}{2} \\ p_2 = \frac{p_1}{2} + \frac{p_3}{2} = \frac{p_1}{2} + \frac{1}{2}. \end{array}$$

Thus, $p_1 = \frac{1}{3}$ and $p_2 = \frac{2}{3}$ .

We conclude that the probability of the random walk ending at 3 rather than at 0 is $\frac{1}{3}$ .