Suppose X1, X2, X3, . . . is a sequence of independent, {1, 1}-valued random variables which satisfy pXi (1) = p, pXi (1) = 1 p. Let S1, S2, S3, . . . be a random walk on the integers Z starting at a Z, so that Sn = a + Xn i=1 Xi . Prove the Markov property of the random walk (Sn)n1: for any real numbers a1, a2, . . . , an for which the conditional expectation is defined, we have P(Sn+1 = b|Sn = an, Sn1 = an1, . . . , S1 = a1, S0 = a) = P(Sn+1 = b|Sn = an). (Hint: use the fact that Xn+1 is independent of Sn, Sn1, . . . , S1.)