1    Random walk on the circle

Let’s analyze problem 2 of homework 1. Recall that you have a circle with N + 1 vertices, labeled 0, 1, ..., N . You initiate a random walk at vertex 0, and you wait until the walk visits all the N + 1 points at least once.  The homework problem asked you essentially to numerically estimate the average time such a walk takes to visit all the vertices at least once.

1.1    Does it visit all the vertices?

The first question we should answer is, does the walk visit all the vertices? Or can there be some vertices it avoids?

To answer this, we again use a recurrence approach. Fix any i ∈ {0, 1, ..., N}. Let fi (k) be the probability that the walk misses vertex i when it is started at vertex k . Then, by the first step decomposition, we get, for any k  i, the recurrence

fi (k) =  (fi (k ⊕ 1) + fi (k ⊖ 1))

with the boundary condition fi (i) = 0. Here ⊕ and ⊖ denote respectively addition and subtraction modulo (N + 1).

We can now use the "maximum" argument we used before. Suppose fi (k∗ ) is the maximum among fi (0), ..., fi (N). Then fi (k∗ ⊖ 1) and fi (k∗ ⊕ 1) also have to be maximum as fi (k∗ ) is an average of those two. Continuing this argument, and using the fact that fi (i) = 0, one concludes that 0 is the maximum value, which implies that all of fi (0) = ... = fi (N) = 0.

Hence, the chance that the walk misses vertex i is 0. Let Ai  be the event that the walk misses vertex i. Then, we just got P(Ai ) = 0. This is true for every i = 0, 1, ..., N, so that

P(A0  n A1  n ... n AN ) = 0.

The event A0 nA1 n ... nAN is precisely the event that the walk misses at least one vertex. The above argument shows its probability is 0. Hence, almost surely, the walk visits all the vertices at least once.

1.2    Expected time of covering the circle

Now we answer the question: how long does the walk take on average to visit each point on the circle at least once?

Let Ti  denote the first time the walk covers i distinct points, for i = 1, ..., N + 1. Clearly, we are interested in E(TN+1). We will proceed in analogy with the famous coupon collector problem: we will compute the average time to visit each additional new point, and add them up.

First, note that T1  = 0, as the walk starts at a point which obviously is the first point the walk has visited. Then we decompose

TN+1  = TN+1  − T1  = (Ti+1  − Ti )

By linearity of expectation,

E(TN+1) = E(Ti+1  − Ti )

Observe that Ti+1 −Ti is the additional number of steps to visit the (i+1)’st new point after the

vertex visited by the walk. Then v must be one of the two end-points of a consecutive string of i

vertices visited by the walk by time Ti .

• If v is the left end point, then Ti+1  − Ti is the first time the walk visits either v ⊖ 1 or v ⊕ i.

• If v is the right end point, then Ti+1 − Ti is the first time the walk visits either v ⊕ 1 or v ⊖ i. In the first case, we can think of a random walk starting at 0 and we want the mean first time

the walk hits −1 or i. In the second case, we want the mean first time the walk starting at 0 hits 1 or

E(TN+1) = E(Ti+1  − Ti ) = i =  .

2    How often does the simple symmetric random walk return to the origin?

Suppose Sn  is a simple symmetric random walk starting at S0  = 0. Let N(0) = |{n ≥ 0 : Sn  = 0}|, the number of times the random walk is at 0. Let us compute E(N(0)). Since

N(0) = I(Sn  = 0),

it follows that

E(N(0)) = EI(Sn  = 0) = P(Sn  = 0) = P(S2n  = 0)

where the last equality is because Sn can hit 0 at only even time points starting from S0  = 0. Now, P(S2n  = 0) = (n(2n))2 −2n . Hence

E(N(0)) =  (n(2n))2 −2n

By Stirling’s approximation, we know that n! ∼ ^2πn(n/e)n  as n → ∞, where an  ∼ bn  means an /bn  → 1 as n → ∞. Using this, we can approximate the binomial coefficient and deduce that

( n(2n))2 −2n  ∼

and hence

E(N(0)) ∼   = ∞

and hence E(N(0)) = ∞. This implies that the simple symmetric random walk visits the origin infinitely many times, and we have a special name for such a random walk.

Definition 2.1.  A random walk on the integer lattice (in any dimension) is called recurrent if starting at the origin, the expected time it spends at the origin is infinite. Otherwise, the random walk is called transient.

So, the simple symmetric random walk in one dimensional integer lattice is recurrent.

3    Higher dimensions

We now define the simple symmetric random walk in any dimension d.  Let Xi  be iid random variables taking the 2d vectors 干e1 , ..., 干ed with equal probability: for each i,

P(Xi  = e1 ) = P(Xi  = −e1 ) = P(Xi  = e2 ) = P(Xi  = −e2 ) = ... = P(Xi  = ed ) = P(Xi  = −ed ) =

Here, ei denotes the i’th coordinate vector in Rd , with 1 in i’th coordinate and 0 elsewhere. Define Sn  = S0  + ∑ Xi where S0  ∈ Zd . Then, {Sn }n≥0 is a simple symmetric random walk in Zd .

Let Nd (0) denote the number of times the d −dimensional random walk hits 0, the origin (now,

E(N1 (0)) = ∞ implying that the simple symmetric random walk in one dimension is recurrent.

Now we study whether a d −dimensional random walk is recurrent or transient.

3.1    Dimension d = 2

We again compute E(N2 (0)). As before,

E(N2 (0)) = P(Sn  = (0, 0))

and so it suffices to find P(Sn  = (0, 0)). Note that the simple symmetric random walk in d = 2, starting at S0  = 0, reaches the origin (0, 0) in only even time steps. Hence, we only need to find P(S2n  = (0, 0)).

How must have the random walk moved so that it reached (0, 0) in time 2n? If it took j right

steps, it must have taken j left steps, n − j up steps and n − j down steps. Counting the number

step has probability 1/4, so the probability of any path of length 2n is (1/4)2n . Hence,

P(S2n  = (0, 0)) =  4−2n

= 4 −2n (n(2n))  (  )()

= 4 −2n (n(2n))2

Using Stirling’s approximation,

P(S2n  = (0, 0)) ∼ 

which implies that

E(N2 (0)) ∼   = ∞

Hence, the simple symmetric random walk in dimension 2 is again recurrent.

3.2    Dimension d = 3

By analogous argument as before, we only need to consider P(S2n   =  (0, 0, 0)).  If a path starts at (0, 0, 0) and ends in (0, 0, 0) in 2n steps, then it must have taken i, j, k steps in each of three directions, symmetrically, with i + j + k = n. Thus

P(S2n  = (0, 0, 0)) = i,j,k≥+k=n 6−2n  =  (n(2n)) i,j,k≥+k=n  (i,  k)2 6 −2n