Will a random walk reach +3 in eight steps?

Question

A symmetric \pm 1 random walk starts at 0 and takes 8 steps, each +1 or -1 with probability 	frac12. What is the probability the walk reaches level +3 at some point during the 8 steps?

Accepted Answer

Let M = \max{0 \le j \le 8} Sj be the highest level reached. The reflection principle says that for a \ge 1, P(M \ge a) = P(Sn \ge a) + P(Sn \ge a + 1). The idea: paths ending at or above a already reached a; for each path that reaches a but ends below it at k, reflect the segment after the first hit of a to pair it with a path ending at 2a - k a. Summing over endpoints collapses to the two-term formula. Here n = 8, a = 3. Because 8 steps give an even endpoint, S8 is always even, so P(S8 \ge 3) = P(S8 \ge 4) and P(S8 \ge 4) = P(S8 \ge 4). Both terms equal P(S8 \ge 4). Write S8 = 2u - 8 where …

Will a random walk reach +3 in eight steps?

Your answer

More Probability questions