免费概率困难

Returning to the Origin

考察公司Hudson River TradingJane Street

A particle starts at $0$ on the number line. At each step it moves $+1$ or $-1$ , each with probability $\tfrac12$ .

Show that it is certain to come back to $0$ eventually.
Show that the expected time until it first comes back is infinite.
What changes if the walk moves on a 2-D or 3-D grid instead?

解析

先自己试一试，卡住了再打开提示。

提示 1

Part 1: after the first step the particle is at $1$ (or $-1$ ). Starting from $1$ , what is the chance it reaches $N$ before it reaches $0$ ? Let $N$ grow.

提示 2

Part 2: let $m$ be the expected time to get from $1$ down to $0$ . Getting from $2$ down to $0$ means doing that trip twice. Write an equation for $m$ .

查看解析

Part 1: It always comes back

After the first step the particle is at $1$ or $-1$ ; by symmetry, take $1$ .

Pick a large number $N$ and ask: starting from $k$ , what is the chance $h(k)$ of reaching $N$ before $0$ ? From any $k$ in between, the next step goes up or down with chance $\tfrac12$ each, so

h(k) = \tfrac12\, h(k-1) + \tfrac12\, h(k+1).

That says each value is the average of its neighbours, so the values lie on a straight line. With $h(0) = 0$ and $h(N) = 1$ , the line is

h(k) = \frac{k}{N}.

So from $1$ , the chance of reaching $N$ before getting back to $0$ is $\frac{1}{N}$ .

Never coming back to $0$ would mean climbing past every $N$ without first returning, and the chance of that is at most $\frac1N$ for every $N$ . So it is $0$ : the walk comes back with probability $1$ .

Part 2: But the expected wait is infinite

Let $m$ be the expected number of steps to get from $1$ down to $0$ .

Take one step from $1$ :

with chance $\tfrac12$ it lands on $0$ , and we are done;
with chance $\tfrac12$ it lands on $2$ . To get from $2$ down to $0$ it must first get down to $1$ (expected $m$ steps, the same trip shifted up by one) and then from $1$ to $0$ (another $m$ ).

m = 1 + \tfrac12 \cdot 0 + \tfrac12 \cdot 2m = 1 + m.

No finite number satisfies $m = 1 + m$ , so $m = \infty$ . The first return takes one step plus this trip, so its expected time is infinite too, even though Part 1 says the return is certain.

Intuition: most walks come back quickly, but a few wander very far and take a very long time, and those rare long trips make the average infinite.

Part 3: Two and three dimensions

On a grid, each step moves one unit in one of the $2d$ directions ( $4$ in 2-D, $6$ in 3-D), all equally likely.

Count the expected number of visits to the start. If each return happened with chance $q < 1$ , the number of returns would be like counting successes before the first failure, with average $\frac{q}{1-q}$ , which is finite. So:

\text{return is certain} \iff \text{the expected number of visits to the start is infinite.}

How likely is the walk to be at the start at step $2n$ ? After $2n$ steps the walk has drifted about $\sqrt{n}$ away along each axis (the spread of a sum of $\pm1$ steps grows like the square root of the number of steps). So in each direction it is spread over roughly $\sqrt n$ positions, and the chance of being exactly back at the start is roughly

\frac{1}{\sqrt n} \text{ in 1-D}, \qquad \frac{1}{n} \text{ in 2-D}, \qquad \frac{1}{n^{3/2}} \text{ in 3-D}.

Add these up over all $n$ to get the expected number of visits:

1-D: $1 + \frac{1}{\sqrt2} + \frac{1}{\sqrt3} + \dots$ grows without limit → certain to return.
2-D: $1 + \frac12 + \frac13 + \dots$ also grows without limit → certain to return.
3-D: $1 + \frac{1}{2^{3/2}} + \frac{1}{3^{3/2}} + \dots$ stays finite → not certain. The walk returns with probability only about $0.34$ ; otherwise it wanders off for good.

In 2-D the walk still comes back for sure, and the expected wait is still infinite, as in 1-D.

> A drunk man will find his way home, but a drunk bird may get lost forever. (Shizuo Kakutani)

题目

解析

Part 1: It always comes back

Part 2: But the expected wait is infinite

Part 3: Two and three dimensions