Show that (Yn : n ≥ 0) is also a simple, symmetric random walk.

Let Mn = max{Xi : 0 ≤ i ≤ n}. Explain why {Mn ≥ a} = {Ta ≤ n} for a ≥ 1. By using the process (Yn : n ≥ 0) constructed above, show that, for a ≥ 1, P

????

Mn ≥

a, Xn ≤ a − 1

= P(Xn ≥ a + 1), and thus, P(Mn ≥

a) = P(Xn ≥

a) + P(Xn ≥ a + 1).

Hence compute P(Mn = a), where a and n are positive integers with n ≥

a. [Hint: if n is even, then Xn must be even, and if n is odd, then Xn must be odd