Markov chains & Gibbs sampling

This lecture builds Markov chains from the Markov property and the restaurant state model. It then builds samplers from accept-reject to MCMC and Gibbs. After this page you can compute mu1 equals mu0 T, check a stationary distribution, apply the accept-reject ratio, and trace Gibbs conditional steps.

Markov Stationary Distributionritvikmath · Steady state transition matrix

Markov Chains StationaryEntangled Worlds · Markov property stationary distribution

MCMC ExplainedDataMListic · MCMC burn-in stationary sampling

Gibbs Sampling ExplainedDataMListic · Conditional sampling MCMC chains

Markov property Search on YouTube

A stochastic process $\{X_t\}$ has the Markov property when the future depends only on the present. Past states give no extra information once the current state is known. The process has no memory beyond the current state.

P(X_{t+1} = j \vert X_t = i, X_{t-1}, \ldots, X_0) = P(X_{t+1} = j \vert X_t = i)

$X_t$ is the state at time $t$ . $i$ is the current state. $j$ is the next state. The left side conditions on the full history. The right side uses only $X_t$ .

Tomorrow depends only on today. Last week does not matter once today is known.

Markov chain Search on YouTube

A Markov chain is a sequence of random variables $\{X_t\}$ that satisfies the Markov property. Its state set $S$ is finite or countable. The slides write $S = \{1, 2, 3, \ldots\}$ .

The chain moves by transition probabilities. The value $T_{ij}$ is the chance to move from state $i$ to state $j$ . Each row of the transition matrix sums to 1.

T_{ij} = P(X_{t+1} = j \vert X_t = i), \qquad \sum_j T_{ij} = 1

$T$ is the transition matrix. $T_{ij}$ is the entry in row $i$ and column $j$ . A homogeneous chain keeps the same $T$ at every time step.

Markov chain versus hidden Markov model Search on YouTube

A Markov chain assumes direct access to the state. A hidden Markov model assumes hidden states plus visible outputs. The hidden states follow a Markov chain. Each hidden state emits an observation with an emission probability.

Model	State	Observation
Markov chain	Future state depends only on current state	State itself is visible
Hidden Markov model	Hidden states follow a Markov chain	Only emissions are visible, states stay hidden

The slides name parts of speech as hidden states and words as observations. Transition probabilities link the hidden states. Emission probabilities link each hidden state to its words.

Types of Markov models Search on YouTube

The slides list four extensions of the discrete-time base model. The base model is a plain Markov chain. Each extension adds one component.

Base model: discrete-time Markov chain.
Base model plus rewards plus actions: decision process with control.
Base model plus rewards: evaluation of long-run return.
Base model plus hidden states plus observations: hidden Markov model.

Restaurant example Search on YouTube

The slides model a restaurant with $n$ seats. Each seat is vacant ( $0$ ) or occupied ( $1$ ). The state on one day is an $n$ -dimensional binary vector. One example is $[1, 0, 1]$ for three seats.

The number of seating patterns grows fast. Each seat has 2 options. The full state count is therefore $2^n$ .

N_{\text{states}} = 2^n

$n$ is the number of seats. Each seat takes value $0$ or $1$ . The transition matrix $T$ has size $2^n \times 2^n$ .

Under the Markov assumption, tomorrow depends only on today. Regulars may reuse the same seats. Last week adds nothing once today is known. For each current pattern, the model stores transition probabilities to every next pattern.

Two seats give four states. T stores the move chance between every pair.

State distribution over time Search on YouTube

The initial distribution $\mu_0$ stores the chance of each state on day 0. The distribution after one step is $\mu_1$ . The update is a row-vector times matrix product.

\mu_{t+1} = \mu_t T

$\mu_t$ is the row distribution at time $t$ . $T$ is the transition matrix. Entry $j$ of $\mu_{t+1}$ equals $\sum_i \mu_t(i) T_{ij}$ .

After many days, the distribution may stop changing. That limit is the stationary distribution $\mu^*$ . It satisfies its own fixed-point equation. It gives the long-run share of each seating pattern.

\mu^* = \mu^* T

$\mu^*$ is the stationary distribution. It reproduces itself through $T$ . The slides illustrate the idea as full on 70 percent of days, half-full on 20 percent, and empty on 10 percent.

Two-seat worked example Search on YouTube

Two seats give $2^2 = 4$ states. Order them as $00$ , $01$ , $10$ , $11$ . Use a homogeneous $T$ with rows and columns that each sum to 1.

Setup. Initial distribution and transition matrix.

\begin{aligned} \mu_0 &= \begin{bmatrix} 0.10 & 0.20 & 0.30 & 0.40 \end{bmatrix}\\ T &= \begin{bmatrix} 0.40 & 0.30 & 0.20 & 0.10\\ 0.30 & 0.40 & 0.10 & 0.20\\ 0.20 & 0.10 & 0.40 & 0.30\\ 0.10 & 0.20 & 0.30 & 0.40 \end{bmatrix} \end{aligned}

Step 1. Multiply $\mu_0 T$ . Each entry sums one column weighted by $\mu_0$ .

\begin{aligned} \mu_1(00) &= 0.10(0.40) + 0.20(0.30) + 0.30(0.20) + 0.40(0.10) = 0.20\\ \mu_1(01) &= 0.10(0.30) + 0.20(0.40) + 0.30(0.10) + 0.40(0.20) = 0.22\\ \mu_1(10) &= 0.10(0.20) + 0.20(0.10) + 0.30(0.40) + 0.40(0.30) = 0.28\\ \mu_1(11) &= 0.10(0.10) + 0.20(0.20) + 0.30(0.30) + 0.40(0.40) = 0.30 \end{aligned}

Step 2. Check the sum.

\begin{aligned} 0.20 + 0.22 + 0.28 + 0.30 &= \mathbf{1.00}\\ \mu_1 &= \mathbf{\begin{bmatrix} 0.20 & 0.22 & 0.28 & 0.30 \end{bmatrix}} \end{aligned}

The mass moves toward the centre. State $11$ drops from 0.40 to 0.30 after one day.

Stationary check Search on YouTube

The same $T$ has uniform column sums. Each column adds to 1. The uniform distribution must therefore reproduce itself.

Claim. The uniform row is stationary.

\begin{aligned} \mu^* &= \begin{bmatrix} 0.25 & 0.25 & 0.25 & 0.25 \end{bmatrix} \end{aligned}

Step 1. Multiply $\mu^* T$ . Factor out 0.25 from each column sum.

\begin{aligned} \mu^*(00) &= 0.25(0.40 + 0.30 + 0.20 + 0.10) = 0.25(1.00) = 0.25\\ \mu^*(01) &= 0.25(0.30 + 0.40 + 0.10 + 0.20) = 0.25(1.00) = 0.25\\ \mu^*(10) &= 0.25(0.20 + 0.10 + 0.40 + 0.30) = 0.25(1.00) = 0.25\\ \mu^*(11) &= 0.25(0.10 + 0.20 + 0.30 + 0.40) = 0.25(1.00) = 0.25 \end{aligned}

Step 2. Compare.

\begin{aligned} \mu^* T &= \mathbf{\begin{bmatrix} 0.25 & 0.25 & 0.25 & 0.25 \end{bmatrix}} = \mu^* \end{aligned}

The check passes. A further step changes nothing. In the long run each of the four patterns occurs on one quarter of days.

Exam check: verify each row of $T$ sums to 1 before you multiply. Then verify $\mu_1$ sums to 1. For a stationary check, show all four entries of $\mu^* T$ and state the equality.

Sampling techniques Search on YouTube

Sampling selects a small subset from a population. A sound method makes the subset represent the whole. Conclusions from the subset then carry over. Sampling also speeds up work when full measurement is infeasible.

Method	Idea	When to use it
Deterministic	Rule-based or systematic choice	The rule covers the population well
Random	Draws follow a uniform probability law	Direct draws from the target are feasible
Monte Carlo	Draws approximate a complex or high-dimensional distribution	Bayesian inference and generative models
Accept-reject	Propose from an easy law, keep some draws	A bound $c$ exists and proposals are cheap
Markov chain Monte Carlo	Build a chain whose limit is the target	Direct sampling is infeasible

Monte Carlo sampling splits into accept-reject and Markov chain Monte Carlo. Gibbs sampling is one Markov chain Monte Carlo method.

D R M A G: Draws Run Many And Gather

Deterministic · Random · Monte Carlo · Accept-reject · Gibbs (an MCMC method). MCMC then warns T C S C: Trapped modes, Correlated draws, Slow mixing, Complex conditionals.

Accept-reject sampling Search on YouTube

Accept-reject generates draws from a hard target $f(x)$ . It uses an easy proposal $g(x)$ . A constant $c$ scales $g$ so it covers $f$ at every $x$ . Candidates come from $g$ . Each candidate survives with a ratio chance.

f(x) \le c \cdot g(x) \quad \text{for all } x

$f$ is the target distribution. $g$ is the easy proposal distribution. $c$ is a constant that lifts $g$ above $f$ .

P(\text{accept} \vert x) = \frac{f(x)}{c \cdot g(x)}

Draw $u$ from Uniform $[0,1]$ . Accept $x$ when $u \le f(x)/(c \cdot g(x))$ . Else reject $x$ and draw again.

The method treats each candidate alone. It ignores past accepted draws. Regions with high $f$ likely hold more good points nearby, but accept-reject does not use that fact. The next candidate starts afresh from $g$ .

Setup. Target $f(x) = 3x^2$ on $[0,1]$ . Proposal $g(x) = 1$ on $[0,1]$ . Bound $c = 3$ .

\begin{aligned} c \cdot g(x) &= 3 \ge 3x^2 = f(x)\\ P(\text{accept} \vert x) &= \frac{3x^2}{3} = x^2 \end{aligned}

Candidate $x = 0.70$ .

\begin{aligned} f(0.70) &= 3(0.70)^2 = 3(0.49) = 1.47\\ P(\text{accept}) &= 1.47/3 = \mathbf{0.49} \end{aligned}

Draw $u = 0.23$ . Since $0.23 \lt 0.49$ , accept $0.70$ .

Candidate $x = 0.20$ .

\begin{aligned} f(0.20) &= 3(0.04) = 0.12\\ P(\text{accept}) &= 0.12/3 = \mathbf{0.04} \end{aligned}

Draw $u = 0.81$ . Since $0.81 \gt 0.04$ , reject $0.20$ .

Small $x$ values rarely survive. Many proposals go to waste near 0. That waste motivates MCMC.

Do not pick $c$ too small. The bound $f(x) \le c \cdot g(x)$ must hold at every $x$ . A violated bound gives a wrong sampled distribution.

Markov chain Monte Carlo Search on YouTube

MCMC fixes the waste of accept-reject. It exploits a simple fact: high-density regions sit near other high-density regions. A draw near an accepted point has a strong chance of acceptance. So MCMC builds a chain of dependent draws instead of fresh independent draws.

The chain has transition law $T(X_{i+1} \vert X_i)$ . It moves toward denser points of $p(x)$ . Its equilibrium equals the target $f(x)$ . More steps bring the sample histogram closer to the target.

X_0 \to X_1 \to X_2 \to \cdots \to X_m \to X_{m+1} \to \cdots

$X_i$ is the $i$ -th sample in the chain. $T(X_{i+1} \vert X_i)$ is the move chance. The chain limit matches the target distribution.

The chain starts at X0. Early draws form burn-in. Samples from Xm onward match the target.

Burn-in phase Search on YouTube

Sampling starts at $X_0$ . Early draws $X_1$ through $X_{m-1}$ do not yet match the target. That early stretch is burn-in. The chain reaches the target near $X_m$ . Keep $X_m, X_{m+1}, \ldots$ as samples. Discard the burn-in draws.

Gibbs sampling Search on YouTube

Gibbs sampling draws from a joint law of two or more variables. It is an MCMC method, so its draws are dependent. It replaces one hard joint draw with easy conditional draws. For fixed $y$ , $P(y)$ acts as a constant. The sampler needs only relative chances, not the full normalizer $Z$ .

P(x \vert y) = \frac{P(x, y)}{P(y)}

$P(x, y)$ is the joint chance. $P(y)$ sums the joint over $x$ . No full joint normalizer $Z$ is needed for the conditional step.

P(y \vert x) = \frac{P(x, y)}{P(x)}

Fix $x$ and sample $y$ from this law. Then fix $y$ and sample $x$ . Alternate the two steps to form the chain.

The chain stationary state equals the joint target. Samples before that state count as burn-in. Discard them for the same reason as in MCMC.

Gibbs conditional trace Search on YouTube

Use a binary pair $(X, Y)$ with a known joint table. The trace below derives the conditionals and then runs three Gibbs steps.

Joint table. Rows are $X$ , columns are $Y$ .

	Y=0	Y=1
X=0	0.10	0.20
X=1	0.30	0.40

Margins. Sum rows and columns.

\begin{aligned} P(Y=0) &= 0.10 + 0.30 = 0.40\\ P(Y=1) &= 0.20 + 0.40 = 0.60\\ P(X=0) &= 0.10 + 0.20 = 0.30\\ P(X=1) &= 0.30 + 0.40 = 0.70 \end{aligned}

Conditionals for $X$ given $Y$ .

\begin{aligned} P(X=0 \vert Y=0) &= 0.10/0.40 = 0.25\\ P(X=1 \vert Y=0) &= 0.30/0.40 = 0.75\\ P(X=0 \vert Y=1) &= 0.20/0.60 = 0.333\\ P(X=1 \vert Y=1) &= 0.40/0.60 = 0.667 \end{aligned}

Conditionals for $Y$ given $X$ .

\begin{aligned} P(Y=0 \vert X=0) &= 0.10/0.30 = 0.333\\ P(Y=1 \vert X=0) &= 0.20/0.30 = 0.667\\ P(Y=0 \vert X=1) &= 0.30/0.70 = 0.429\\ P(Y=1 \vert X=1) &= 0.40/0.70 = 0.571 \end{aligned}

Trace from $(0,0)$ . Use uniform draws $u$ and $v$ at each half-step.

\begin{aligned} X_1 \vert Y_0{=}0 &: u_1 = 0.62 \gt 0.25 \Rightarrow \mathbf{X_1 = 1}\\ Y_1 \vert X_1{=}1 &: v_1 = 0.30 \lt 0.429 \Rightarrow \mathbf{Y_1 = 0}\\ X_2 \vert Y_1{=}0 &: u_2 = 0.10 \lt 0.25 \Rightarrow \mathbf{X_2 = 0}\\ Y_2 \vert X_2{=}0 &: v_2 = 0.75 \gt 0.333 \Rightarrow \mathbf{Y_2 = 1}\\ X_3 \vert Y_2{=}1 &: u_3 = 0.50 \gt 0.333 \Rightarrow \mathbf{X_3 = 1}\\ Y_3 \vert X_3{=}1 &: v_3 = 0.90 \gt 0.429 \Rightarrow \mathbf{Y_3 = 1} \end{aligned}

The chain visits $(1,0)$ , then $(0,1)$ , then $(1,1)$ . Treat the first visits as burn-in. Keep the later states for estimates.

Limits of Gibbs sampling Search on YouTube

Gibbs sampling handles high-dimensional targets that defeat direct sampling. Its dependence is also its weakness. The slides list five linked failure modes.

Trapping: the chain sticks in one local high-probability region.
Bias: poor exploration misrepresents the full distribution.
Slow convergence: high correlation between variables slows mixing.
Complex conditionals: irregular shapes make each $P(x \vert y)$ hard to derive.
High dimensions: many dependent conditionals reduce accuracy.

Do not keep burn-in draws. Early samples reflect the start point, not the target. Also check mixing when variables show strong correlation. A chain trapped in one mode gives biased estimates.

Quick self-test Search on YouTube

1. State the Markov property in one formula and one sentence.

$P(X_{t+1}=j \vert X_t=i, X_{t-1}, \ldots)=P(X_{t+1}=j \vert X_t=i)$ . The future depends only on the present state.

2. Differentiate a Markov chain and a hidden Markov model.

A Markov chain shows its state directly. A hidden Markov model hides the Markov states and shows only emissions. Transitions link hidden states, emissions link hidden states to observations.

3. A restaurant has 3 seats. How many states exist, and what is the size of T?

$2^3=8$ states. $T$ has size $8 \times 8$ , with 64 entries. Each of the 8 rows sums to 1.

4. With mu0 equals [0.10 0.20 0.30 0.40] and the lecture T, compute mu1 for state 01.

$\mu_1(01)=0.10(0.30)+0.20(0.40)+0.30(0.10)+0.40(0.20)=0.03+0.08+0.03+0.08=0.22$ . Full $\mu_1=[0.20, 0.22, 0.28, 0.30]$ .

5. Check whether [0.25 0.25 0.25 0.25] is stationary for the lecture T.

Yes. Each column of $T$ sums to 1, so each entry gives $0.25(1.00)=0.25$ . Hence $\mu^* T=\mu^*$ .

6. Target f(x) equals 3x squared on [0,1], proposal g(x) equals 1, c equals 3. Candidate x equals 0.5: find the accept chance. Draw u equals 0.10: accept or reject?

$f(0.5)=3(0.25)=0.75$ . Accept chance $=0.75/3=0.25$ . Since $0.10 \lt 0.25$ , accept $0.50$ .

7. Why does MCMC explore high-probability regions better than accept-reject?

Accept-reject draws each candidate afresh from $g$ and ignores past draws. MCMC chains the draws and proposes near the current point. A point near a good draw has high density and a strong accept chance.

8. In Gibbs sampling with variables X and Y, which two conditional steps alternate?

Sample $x$ from $P(x \vert y)$ with $y$ fixed. Then sample $y$ from $P(y \vert x)$ with $x$ fixed. Repeat until the chain reaches its stationary state.

9. Joint chances: P(0,0) equals 0.10, P(0,1) equals 0.20, P(1,0) equals 0.30, P(1,1) equals 0.40. Find P(X equals 1 given Y equals 0).

$P(Y=0)=0.10+0.30=0.40$ . $P(X=1 \vert Y=0)=0.30/0.40=0.75$ .

10. Name two Gibbs failure modes and the fix the slides advise.

Trapping in a local mode and slow mixing from correlated variables. Tune the sampler with care and run convergence and mixing checks. Discard burn-in draws.

The Markov property keeps only the present: the future given the full history equals the future given $X_t$ .
A Markov chain is a memoryless sequence with state set $S$ and transition matrix $T_{ij}=P(X_{t+1}=j \vert X_t=i)$ .
A hidden Markov model hides Markov states and shows only emissions through emission chances.
The restaurant with $n$ seats has $2^n$ binary states and a $2^n \times 2^n$ transition matrix.
Distributions evolve by $\mu_{t+1}=\mu_t T$ . The stationary limit obeys $\mu^*=\mu^* T$ .
Two-seat check: $\mu_0=[0.10,0.20,0.30,0.40]$ gives $\mu_1=[0.20,0.22,0.28,0.30]$ . Uniform $[0.25,0.25,0.25,0.25]$ is stationary.
Sampling ladder: deterministic, random, Monte Carlo, accept-reject, MCMC with Gibbs.
Accept-reject needs $f \le c \cdot g$ and keeps $x$ with chance $f(x)/(c \cdot g(x))$ . Example gives 0.49 at $x=0.70$ .
MCMC builds $X_0 \to X_1 \to \cdots$ with $T(X_{i+1} \vert X_i)$ . Its limit is the target. Discard burn-in before $X_m$ .
Gibbs sampling alternates $P(x \vert y)$ and $P(y \vert x)$ . It avoids the joint normalizer $Z$ .
Gibbs pitfalls: trapped modes, biased samples, slow mixing, complex conditionals, high dimensions.

Markov chains & Gibbs sampling

Markov propertySearch on YouTubeBookmarkSaved

Markov chainSearch on YouTubeBookmarkSaved

Markov chain versus hidden Markov modelSearch on YouTubeBookmarkSaved

Types of Markov modelsSearch on YouTubeBookmarkSaved

Restaurant exampleSearch on YouTubeBookmarkSaved

State distribution over timeSearch on YouTubeBookmarkSaved

Two-seat worked exampleSearch on YouTubeBookmarkSaved

Stationary checkSearch on YouTubeBookmarkSaved

Sampling techniquesSearch on YouTubeBookmarkSaved

Accept-reject samplingSearch on YouTubeBookmarkSaved

Markov chain Monte CarloSearch on YouTubeBookmarkSaved

Burn-in phaseSearch on YouTubeBookmarkSaved

Gibbs samplingSearch on YouTubeBookmarkSaved

Gibbs conditional traceSearch on YouTubeBookmarkSaved

Limits of Gibbs samplingSearch on YouTubeBookmarkSaved

Quick self-testSearch on YouTubeBookmarkSaved

On this page