This question is about a simple random walk with S0 = 0 and p = q = 1 2 . Define T to be the first time the walk takes to return to 0; i.e. T = min{n > 0 : Sn = 0}. Also, for n even, define pin = P (S1 > 0, S2 > 0, . . . , Sn > 0}, Nn(0, v) the number of paths going from 0 to v in time n, N0n(0, v) the numer of paths from 0 to v in time n which go through 0 again, and N−0n (0, v) the number of paths which go from 0 to v in time n and do not go through 0 again. (i) Write pin as a sum of N −0 n (0, r) terms for suitable r values. (ii) Explain in detail why N−0n (0, r) = Nn−1(0, r − 1)−Nn−1(0, r + 1) for n > 1. (iii) Hence, show that pin = 1 2 n Nn−1(0, 1). (iv) Deduce that pin = 1 2 n ( n− 1 1 2 n ) ; i.e. show that Nn−1(0, 1) = ( n−1 1 2 n ) . (v) Using all the results so far, show that P (T0 ≤ n) = 1− 12 n−1 ( n− 1 1 2 n ) . 1