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

Probability · Lecture 58 of 76 · 11:41

Markov Chain Practice 1

Markov Chain Practice 1 on YouTube

Study guide

What this lecture covers

This worked problem uses a fixed six-state Markov chain, always starting at state S0, to practice several standard question types. It computes the probability of first entering a state at a given trial, the probability of never reaching a state, the probability of entering and immediately leaving a state, and the probability of being in a state exactly n trials in.

You should already know basic Markov chain notation, transition probabilities, and conditional probability before watching. Afterward, you'll be able to compute first-passage probabilities and n-step occupancy probabilities on a small chain by tracing out the specific paths that satisfy each event.

Key ideas

  • Chain structure: from S0 the process moves to S1, S3, or S5, each with probability 1/3; S1 and S5 are absorbing, while S3 connects to a left and right branch of the chain.
  • First-passage probability: the probability of first entering a state at trial k is built from the probability of the specific path (transition then possible self-loops) that reaches it exactly at that trial.
  • Never-reaching probability: computed by summing the probabilities of all disjoint paths that permanently avoid the target state.
  • Conditional transition probabilities: when a state has multiple possible next states, conditioning on "a state change occurred" renormalizes the probabilities of just those transitions.
  • Enter-then-leave probability: written as a product of the probability of entering a state and the probability of leaving it on the next trial, using the Markov property to treat them as independent given the current state.
  • n-step probability via a single deterministic path: when only one path leads to a state, the probability of being there after n trials is that path's probability raised to the appropriate power.

Before you watch

  • Review Markov chain transition probability notation (p_ij).
  • Know how to compute the probability of a fixed sequence of transitions using the Markov property.
  • Be comfortable conditioning on "a transition occurred" to renormalize probabilities among a subset of outcomes.

Check your understanding

  1. Why is the probability of first entering S2 at trial 1 automatically zero?
  2. How does conditioning on "a state change from S3 has happened" change the probability assigned to the S3-to-S2 transition?
  3. Why can the probability of entering S2 and then leaving it be written as a simple product?
  4. What is it about this particular chain's structure that makes the probability of being in S3 after n trials depend on only one path?

Vocabulary

first-passage probability (phrase)
The chance that a process reaches a certain state for the first time at a specific step.
We compute the first-passage probability of reaching S2 at trial 3.
trace out (phrasal verb)
To follow and identify every step of a path in detail.
We trace out the specific paths that satisfy the event.
renormalize (verb)
To rescale probabilities so they add back up to 1 after removing some outcomes.
We renormalize the probabilities after conditioning on a state change.
branch (noun)
One separate path leading away from a point in a diagram.
S3 connects to a left and right branch of the chain.
deterministic path (phrase)
A single fixed sequence of steps with no other possibilities.
Only one deterministic path leads to S3 after n steps.
Markov chain (phrase)
A random process that moves between states, where the next state depends only on the current one.
The six-state Markov chain always starts at S0.
transition probability (phrase)
The chance of moving from one state to another in a single step.
Each transition probability out of S0 is 1/3.
absorbing (adjective)
Describing a state that, once reached, is never left.
S1 and S5 are absorbing states in this chain.
self-loop (phrase)
A transition that leads back to the same state.
A self-loop lets the chain stay in the same state for extra steps.
occupancy probability (phrase)
The chance that a process is in a specific state at a specific time.
We compute the occupancy probability of being in S3 after n trials.
path (noun)
A specific sequence of states a process moves through.
Only one path reaches S2 in exactly two steps.
condition on (phrasal verb)
To calculate something assuming a particular event has happened.
We condition on 'a state change occurred' to renormalize probabilities.
disjoint (adjective)
Not overlapping; having nothing in common.
We sum the probabilities of all disjoint paths that avoid the state.
permanently (adverb)
In a way that lasts forever, with no change back.
Never-reaching means the chain permanently avoids the target state.
product rule (phrase)
The rule that the probability of two independent steps happening together is their probabilities multiplied.
The enter-then-leave probability uses the product rule.
n-step (adjective)
Involving exactly n moves of a process.
We compute the n-step probability of being in a given state.
structure (noun)
The way parts of something are organized and related.
The chain's structure makes only one path lead to S3.
subset (noun)
A smaller group taken from a larger group.
Renormalizing focuses on a subset of the original outcomes.
outcome (noun)
A specific result of a random experiment.
Each possible next state is one outcome after a transition.
satisfy (verb)
To fully meet the conditions of an event or requirement.
We look for every path that satisfies the given event.
standard question (phrase)
A common type of exercise that appears again and again in a subject.
This problem practices several standard question types on Markov chains.
immediately (adverb)
Right away, with no delay.
One question asks about entering a state and immediately leaving it.
occur (verb)
To happen.
We condition on the fact that a state change occurred.
target (noun)
The specific state or outcome a calculation is aimed at.
S2 is the target state in the first-passage question.
avoid (verb)
To stay away from something, or prevent it from happening.
The never-reaching probability covers paths that always avoid the target.

Chapters

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: Qing He

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

← Setting Up a Markov Chain · Lecture 17: Markov Chains II →