1. 3.28 A drunkard is wandering back and forth on a road. At each step he moves two units distance to the north with a probability of 1 2

, or one unit to the south with a probability 1 2

. Let ak denote the probability of the drunkard ever returning to his point of origin if the drunkard is k units distance away in the northwards direction.

Use the law of conditional probabilities to argue that ak = 1 2

ak+2 + 1 2

ak−1 for k ≥1.Next, show that ak = qk for all k, where q = 1 2

(√

5 −1). Could you give a probabilistic explanation of why ak must be of the form qk for some 0 < q < 1?

Use the result for the drunkard’s walk to prove that the probability of the number of heads ever exceeding twice the number of tails is 1 2

(√

5 −1) if a fair coin is tossed over and over.