Question

A man can take a step forward, backward, left or right with equal probability. Find the probability that after nine steps he will be just one step away from his initial position.

• A. \frac{21347}{4^9}
• B. \frac{3865}{4^7}
• C. \frac{12345}{4^9}
• D. \frac{3969}{4^7}

Answer 1

Answer: (D)

\frac{3969}{4^7}

Answer 2

We want the walker to end at one of the four neighbors: (1,0), (–1,0), (0,1), or (0,–1) after 9 steps. Consider the case ending at (1,0). Let the number of right, left, up, and down steps be r, l, u, and d respectively. Then:   • r − l = 1  (so r = l + 1)
  • u − d = 0  (so u = d)
  • r + l + 2u = 9

Set l = t and u = k so that
  ( t+1 ) + t + 2k = 9  ⟹ 2t + 2k = 8  ⟹ t + k = 4.

Thus for each nonnegative integer t with k = 4 – t, the numbers are:
  r = t+1, l = t, u = d = 4 – t.

The number of ways for a given (t, k) is:
  N(t) = 9!/( (t+1)! · t! · (4–t)! · (4–t)! ).

Calculating for t = 0, 1, 2, 3, 4 we find:

• t = 0: N(0) = 9!/(1!·0!·4!·4!) = 126
• t = 1: N(1) = 9!/(2!·1!·3!·3!) = 2520
• t = 2: N(2) = 9!/(3!·2!·2!·2!) = 7560
• t = 3: N(3) = 9!/(4!·3!·1!·1!) = 5040
• t = 4: N(4) = 9!/(5!·4!·0!·0!) = 126

Total for (1,0) is: 126 + 2520 + 7560 + 5040 + 126 = 15876.

By symmetry there are 4 such cases (for (1,0), (–1,0), (0,1), and (0,–1)), so the total favorable number is
  4 × 15876 = 63504.

Since the total number of possible walks is $4^9$, the probability is
  $\frac{63504}{4^9}$.

Noting that $4^9 = 4^7 \times 16$ and $63504 \div 16 = 3969$, we can write the probability as
  $\frac{3969}{4^7}$.