二维随机游走回原点的概率

二维对称随机游走是常返的（Pólya 定理）：以概率 1 会回到原点。

等价表述：回到原点的概率 $P$ 为 1。

$$\boxed{\mathbb{P}(\text{返回原点})=1}.$$

---

英文解析

Part of lattice of points traveled by particles in the two- dimensional random walk problem. At each move the particle goes one step northeast, northwest, southeast, or southwest from its current position, the directions being equally likely.

In the one- dimensional random walk, The Cliff- Hanger, Problem 35 (last paragraph of Solution), we found the probability that the particle returns to the origin to be unity when the probabilities of steps to the left and right were equally likely. But matters were most delicately balanced. Had either probability budged from $\frac{1}{2}$ , the particle would have walked off to infinity. In two dimensions one might suppose that the particle has plenty of space to wander off to infinity. Let us see. I plan to find the average number of times a particle returns to the origin, and from this to deduce the probability that the particle returns. First, how many times will a particle come back to the origin? If $P$ is the probability of a return, then $1 - P = Q$ is the probability of no return. The probability of exactly $x$ returns is $P^{x}Q$ , because after each return the

particle might as well be regarded as starting over. If $P$ were known, then the mean number of returns to the origin could be computed from this geometric series as

$$\mu = \sum_{x = 0}^{\infty}x P^{x}Q.$$

Looking back at Problem 4 on trials until first success, we find the mean number to be the reciprocal of the probability of success. In that problem the success terminated the series. Here a non- return to the origin terminates the series, and so the mean number of trials to first success is $1 / Q$ . Consequently, the mean number of successes is $1 / Q - 1$ . If $Q = 1$ , then the mean number of successes is 0, that is, with probability one a particle gets lost and never returns. On the other hand, the smaller $Q$ is, the larger the mean number of returns. Indeed, for every $Q$ there is a mean number of returns and for every mean there is a $Q$ . If the mean number of returns before final escape were infinite (unbounded), then $Q$ would have to vanish, and $P$ would equal 1. More formally, as $\mu$ tends to $\infty$ , $P$ tends to 1. Now to get the story on the two- dimensional random walk, all we need do is compute $\mu$ .

Starting from the origin, the particle can only get home to the origin in an even number of steps. Furthermore its path can be represented as the product of two independent one- dimensional random walks, each starting at zero, one stepping east or west on each move, the other stepping north or south on each. For example, toss a coin twice; the first toss decides the eastwest component, the second the north- south one. After the first two steps, the horizontal component, $X$ , has the distribution

$$\frac{x\mid -2\quad 0\quad 2}{P(x)\mid\frac{1}{4}\quad\frac{2}{4}\quad\frac{1}{4}}$$

The vertical component, $Y$ , is similarly distributed after two steps, and their joint probability is distributed over the 9 possible points as follows:

Joint distribution of $X$ and $Y$ after two moves.

The main information we $\nu :$ is $\frac{4}{16}$ and that it can be obtained by multiplying $P(X = 0)$ by $P(Y = 0)$ because of the independence of the component walks. Finally, we want to interpret this information. At the end of two moves $1^{\frac{4}{6}}$ of particles have returned to the origin. The contribution to the mean number of returns to the origin is then $\left(\frac{4}{16}\right)1 + \left(\frac{1}{16}\right)0 = \frac{4}{16}$ . We compute the probability of the particle's being at the origin after 2, 4, 6, ... trials and add these up to get the expected number of times the particle returns to the origin.

After $2n$ moves, $n = 1,2,\ldots$ , the probability of the particle's being at the origin is

$$P(\mathrm{particle~at~origin}) = P(X = 0)P(Y = 0) = \left[\left( \begin{array}{c}2n\\ n \end{array} \right)\left(\frac{1}{2}\right)^{2n}\right]^2,$$

because we must get equal numbers of east and west moves as well as equal numbers of north and south moves. (I ought really to put subscripts on $X$ and $Y$ , writing $X_{2n}$ , but it makes the page look horrible to me and frightening to some.) We plan to sum, approximately, these probabilities to get the expected number of returns. For large values of $n$ we can apply Stirling's approximation given in Problem 18 and get

$$\begin{array}{c}{{\left(\begin{array}{c}{{2n}}\\ {{n}}\end{array}\right)\left(\frac{1}{2}\right)^{2n}=\frac{(2n)!}{n!n!}\left(\frac{1}{2}\right)^{2n}\approx\frac{\sqrt{2\pi}(2n)^{2n+\frac{1}{2}}e^{-2n}}{\left(\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n}\right)^{2}2^{2n}}}}\\ {{\approx1/\sqrt{\pi n}.}}\end{array}$$

For good- sized $n$ then

$$P(\mathrm{particle~at~origin})\approx \frac{1}{\pi n}.$$

We need to sum over the values of $n$ . Recall from Problem 14 that $\sum_{n = 1}^{N} 1 / n \approx \log_{e} N$ is a number which is unbounded as $N$ grows. What we have computed is the probability that the particle is at the origin at the end of steps numbered 2, 4, 6, 8, ..., 2n. Each of these probabilities is also the mean number of times the particle is at the origin at the end of exactly 2n trials. To get the mean total number of times the particle is at the origin, we sum because the mean of the sum is the sum of the means. Therefore the mean number of returns to the origin is unbounded, and therefore the probability of return to the origin is $P = 1$ . And so each particle not only returns, but returns infinitely often. More carefully, I should say nearly every particle returns infinitely often, because there are paths such as the steady northeast course forever that allow some particles to drift off to infinity. But the fraction of such particles among all of them is zero.