## Random Walks- Wald's Lemma

Consider a random walk Ym on S ={0, 1, 2, ..., N } with periodic boundaries at 0 and N ,
that is

P(Ym+1 = i + 1 | Ym = i) = p,
P(Ym+1 = i − 1 | Ym = i) = q = 1 − p

when i ∈ {1, 2, ..., N − 1} and

P(Ym+1 = 1 | Ym = 0) = p, P(Ym+1 = N | Ym = 0) = q,
P(Ym+1 = 0 | Ym = N ) = p, P(Ym+1 = N − 1 | Ym = N ) = q.

(a) (10 marks) Prove that when p = q
P(Ym = 0, Yi ∉ {0, N } for i = 1, 2, . . . , m − 1 and for some m ≥ 1 | Y0 =k)
= [(q/p)^k − (q/p)^N] /1 −(q/p)^ N

for k = 1, 2, . . . , N − 1

(c) (10 marks) Give the definition of a stopping time and state Wald’s lemma. Suppose
Y0 = k and let τ = inf {m : Ym = 0} be the time at which the random walk hits state 0.
Find E(τ) as a function of p, q, N , and k when p≠q.