Markov Chain Practice 1

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?