Consider the random walk W = Wn Wo + X + ... + Xn = where X, X,... are independent, identically distributed random variables with 3 P(Xn P(X = 2) = 1 (a) For k 0, let T be the probability that the random walk ever visits the origin given that it starts at position k, that is, k=Pk (hit 0) = P(W = 0 for some n 0 | Wo= k). = -1) = 8 (Wn)n20 with state space Z such that = P(Xn = 1) i. By splitting according to the first move, show that 1 3 3 x = + x2 + x3. 8 X1 8 4 = and explain why k = (x) for k 1. ii. Show that P (hit 0) = (1/2)* for k 0. Yk = 3 8' (b) For k-1, let y be the probability that the random walk ever visits k given that it starts at 0, that is, Yk Po(hit k) = P(W = k for some n 0| Wo= 0). i. Write down the values of y-1 and yo. ii. For k 1, briefly explain why 3 3 Yk+1+Yk-1+Yk-2. [5] [5] 1 [2] [3] iii. Find all solutions to (*) of the form yk x mk and write down the general solution of the recurrence relation (*). Deduce Po(hit k) for k> -1. [*3] iv. If the random walk starts at the origin and n > 0 is a very large inte- ger, deduce the approximate probability that position n is never visited. Deduce the approximate probability that n is visited exactly k times. [*2]