A Random Walker

What this lecture covers

This recitation problem introduces the random walk: a person on a line who steps forward with probability p and backward with probability 1 - p at each time step, independently of all past steps. The problem uses independence and the multiplication rule to compute probabilities about where the walker ends up after a few steps.

It's a compact application of ideas from independence and conditional probability to a model that reappears often in probability and its applications.

Key ideas

• Independent steps: each step's direction (forward or backward) is independent of every previous step.
• Multiplication rule for independent events: the probability of a specific sequence of steps is the product of each step's individual probability.
• Multiple paths to the same outcome: several different step sequences can lead to the same final position, so their probabilities must be added together.
• Returning to the start after two steps: happens via forward-then-backward or backward-then-forward, giving probability 2p(1-p).
• Ending one step ahead after three steps: requires exactly two forward steps and one backward step, in any of three orders, giving probability 3p²(1-p).
• Conditioning within a known outcome: given that the walker ends up one step ahead after three steps, the probability the first step was forward is 2/3, found by counting favorable sequences among all sequences leading to that outcome.

Before you watch

• Know the multiplication rule for independent events and the definition of conditional probability, covered in the first two lectures of this course.
• No further background is required.

Check your understanding

1. Why is the probability of the sequence "forward then backward" equal to p(1-p)?
2. Why are there exactly two ways to return to the origin after two steps, and how does that lead to probability 2p(1-p)?
3. Why does ending one step ahead after three steps require exactly two forward steps and one backward step?
4. How is the conditional probability that the first step was forward, given the walker ends one step ahead after three steps, computed from counting sequences?