Seyed Masoud Hosseini · Overview · Study log · Weekly summaries · Ideas · Search · Transcript · RSS feed

Probability · Lecture 10 of 76 · 5:51

A Random Walker

Study guide

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

Why is the probability of the sequence "forward then backward" equal to p(1-p)?
Why are there exactly two ways to return to the origin after two steps, and how does that lead to probability 2p(1-p)?
Why does ending one step ahead after three steps require exactly two forward steps and one backward step?
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?

Vocabulary

random walk (noun): A sequence of random steps, each moving forward or backward by chance.
The random walk moves forward with probability p at each step.
sequence (noun): An ordered list of steps or outcomes, one after another.
Several sequences can lead to the walker ending in the same position.
path (noun): One specific series of steps taken through an experiment.
Each path to the same outcome must be counted separately.
return to origin (phrase): Coming back to the same starting position after some steps.
A return to origin after two steps needs one forward and one backward step.
walker (noun): The imaginary person or object taking steps in a random walk.
The walker moves one step forward or backward each time.
forward step (noun): A single move in the positive direction along the line.
A forward step happens with probability p.
backward step (noun): A single move in the negative direction along the line.
A backward step happens with probability 1 minus p.
final position (noun): The location a walker ends up at after all its steps.
Several paths can lead to the same final position.
order (of steps) (noun): The specific sequence in which events happen.
Three forward-backward orders all lead to the same position.
compact application (noun): A short exercise that applies an idea concisely.
This is a compact application of independence and conditional probability.
reappear (verb): To come up again in a later or different context.
The random walk model reappears often in later probability topics.
ahead (position) (adjective): Further forward than the starting point.
The walker ends up one step ahead after three steps.
count (sequences) (verb): To determine the total number of sequences meeting a condition.
You count the favorable sequences to find the conditional probability.
distinct (adjective): Clearly different from one another.
There are three distinct orders that lead to the same result.
conditioning (noun): The process of updating a probability given known information.
Conditioning on the final outcome changes the probability of the first step.
on a line (phrase): Restricted to move only along one straight path.
The random walk here moves on a line, not in two dimensions.
at each time step (phrase): During every single stage of a repeated process.
The walker moves at each time step by chance.
reappear (a model) (verb): To show up again as a useful pattern in later material.
This model reappears often in later probability applications.
step direction (noun): Whether a single move goes forward or backward.
The step direction is independent of all previous steps.
introduce (a model) (verb): To present a new concept for the first time.
This problem introduces the random walk model.

From the YouTube description

MIT 6.041SC Probabilistic Systems Analysis and Applied Probability, Fall 2013
View the complete course: http://ocw.mit.edu/6-041SCF13
Instructor: Kuang Xu

License: Creative Commons BY-NC-SA
More information at http://ocw.mit.edu/terms
More courses at http://ocw.mit.edu

← Lecture 3: Independence · Communication over a Noisy Channel →