Consider the random walk W = (Wn)nzo on Z where Wn Wo + X₁ + ··· + Xn and X₁, X2,... are independent, identically distributed random variables with 3 3 1 P(Xn 1) P(Xn = 1) P(Xn = 2) 8' 4 We define the hitting times T := = inf{n 20: W₁ = k}, where infØ):= +[infinity]. For k, m≥ 0, let x(m) be the probability that the random walk visits the origin by time m given that it starts at position k, that is, (m) := Xk = P(To ≤ m | Wo = k). (0) (a) Give x for k≥ 0. For m≥ 1, by splitting according to the first move, show that (m) 3 (m-1) 3 (m-1) 1 Ik + l 8 k-1 (m-1) = + X k+2 (Vk > 1) 8 4 (m) and co = 1. [5 marks] For k0, let x be the probability that the random walk ever visits the origin given that it starts at position k, that is, x= P(To <[infinity]| W₁ = k) (m) (b) Prove that x) ↑ xk as m → [infinity]. Deduce that 1 3 3 X1 = + x₂ + X3. 4 [4 marks] (c) By splitting according to the value of Tk-1, show that, for k≥ 2, [infinity] P(To <[infinity] | Wo = k) = P(Tk-1 = i| Wo = k) P(To < [infinity] | Wo = k ; Tk-1 = = i). i=1 Deduce that P(To <[infinity]| Wo= k) = P(To <[infinity] | Wo = 1) P(To <[infinity] | W₁ = k − 1) and hence x = (x₁)k for all k ≥ 0. [4 marks] (d) Show that either x₁ = 1 or x₁ = 1/2. [2 marks] (m) <2-k for all k ≥ 0. *(e) Use induction to show that, for every m≥ 0, we have Deduce that P(To <[infinity]| Wo = k) = 2-k for k ≥ 0. [*5 marks] = + =