10 1. Random Walk and Discrete Heat Equation

k consecutive heads followed by tails which is

2k+1.

Therefore, the expected

payoff in this game is

20

·

1

2

+

21

·

1

22

+

22

·

1

23

+ · · · =

1

2

+

1

2

+

1

2

+ · · · = ∞.

Since the expectation is infinite, one should be willing to spend any amount of

money in order to play this game once. However, this is clearly not true and

here lies the paradox.

Let q be the probability that the random walker ever returns to

the origin after time 0. We will show that q = 1 by first assuming

q 1 and deriving a contradiction. Suppose that q 1. Then we can

give the distribution for V . For example, P{V = 1} = (1 − q) since

V = 1 if and only if the walker never returns after time zero. More

generally,

P{V = k} =

qk−1

(1 − q), k = 1, 2,....

This tells us that

E[V ] =

∞

k=1

k P{V = k} =

∞

k=1

k

qk−1

(1 − q) =

1

1 − q

∞;

but we know that E[V ] = ∞. Hence, it must be the case that q = 1.

We have established the following.

Theorem 1.1. The probability that a (one-dimensional) simple ran-

dom walker returns to the origin infinitely often is one.

Note that this also implies that if the random walker starts at

x = 0, then the probability that it will get to the origin is one.

♦

Another way to compute E[V ] in terms of q is to argue that

E[V ] = 1 + q E[V ].

The 1 represents the first visit; q is the probability of returning to the origin;

and the key observation is that the expected number of visits after the first

visit, given that there is a second visit, is exactly the expected number of visits

starting at the origin. Solving this simple equation gives E[V ] = (1 −

q)−1.