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.
Previous Page Next Page