Natural Language Processing · M2 · formulas

Markov chains: read a transition table and multiply a path

HMM & decoding

Formulas explained through full worked examples

A Markov chain is a probabilistic model of a sequence of states. Under the first-order Markov assumption, the next state's probability depends on the current state rather than the complete previous history. The initial probability tells us how likely each first state is. A transition probability tells us how likely a move from one state to another is.

P(s_t\mid s_1,\ldots,s_{t-1})=P(s_t\mid s_{t-1})LaTeX: P(s_t\mid s_1,\ldots,s_{t-1})=P(s_t\mid s_{t-1})
P(s_1,\ldots,s_T)=P(s_1)\prod_{t=2}^{T}P(s_t\mid s_{t-1})LaTeX: P(s_1,\ldots,s_T)=P(s_1)\prod_{t=2}^{T}P(s_t\mid s_{t-1})

For T states in a path, use one initial factor and T−1 transition factors. A row-oriented transition matrix must have each complete row sum to 1. Always read the row/column labels; some exam diagrams use a transposed arrangement.

Current → nextRainDry
Rain0.30.7
Dry0.20.8

Initial probabilities: P(Rain)=0.4, P(Dry)=0.6. Rows describe the current state; columns describe the next state.

Question. For the Rain/Dry Markov chain with initial P(Rain)=0.4 and P(Dry)=0.6, and transitions Rain→Rain=0.3, Rain→Dry=0.7, Dry→Rain=0.2, Dry→Dry=0.8, find the probability of Dry, Dry, Rain, Rain.

Given

Current → nextRainDry
Rain0.30.7
Dry0.20.8

Initial probabilities: P(Rain)=0.4, P(Dry)=0.6. Rows describe the current state; columns describe the next state.

To find

P(Dry,Dry,Rain,Rain).

Formula and why it applies

P(D,D,R,R)=P(D)P(D\mid D)P(R\mid D)P(R\mid R)LaTeX: P(D,D,R,R)=P(D)P(D\mid D)P(R\mid D)P(R\mid R)

Each step conditions on the immediately preceding state. The sequence contains four states, so it needs one initial plus three transition factors.

Solution

Step 1. Start in Dry
P(D)=0.6LaTeX: P(D)=0.6
Step 2. Move Dry to Dry
0.6\times0.8=0.48LaTeX: 0.6\times0.8=0.48
Step 3. Move Dry to Rain
0.48\times0.2=0.096LaTeX: 0.48\times0.2=0.096
Step 4. Move Rain to Rain
0.096\times0.3=0.0288LaTeX: 0.096\times0.3=0.0288
Final answer. Path probability = 0.0288.

Question. For initial probabilities Rain=0.4, Dry=0.6 and transition rows Rain=(0.3,0.7), Dry=(0.2,0.8) in column order Rain,Dry, find the probability of Rain, Dry, Rain.

Given

Current → nextRainDry
Rain0.30.7
Dry0.20.8

Initial probabilities: P(Rain)=0.4, P(Dry)=0.6. Rows describe the current state; columns describe the next state.

To find

P(Rain,Dry,Rain).

Formula and why it applies

P(R,D,R)=P(R)P(D\mid R)P(R\mid D)LaTeX: P(R,D,R)=P(R)P(D\mid R)P(R\mid D)

Do not replace Dry→Rain with Rain→Dry: the two directional probabilities differ.

Solution

Step 1. Initial Rain
P(R)=0.4LaTeX: P(R)=0.4
Step 2. First transition
P(D\mid R)=0.7,\quad0.4(0.7)=0.28LaTeX: P(D\mid R)=0.7,\quad0.4(0.7)=0.28
Step 3. Second transition
P(R\mid D)=0.2,\quad0.28(0.2)=0.056LaTeX: P(R\mid D)=0.2,\quad0.28(0.2)=0.056
Final answer. Path probability = 0.056.

Question. For the same fully specified chain—initial Rain=0.4, Dry=0.6; Rain→Rain=0.3, Rain→Dry=0.7, Dry→Rain=0.2, Dry→Dry=0.8—find P(Dry,Dry). Also find the conditional probability of next Dry given current Dry.

Given

Current → nextRainDry
Rain0.30.7
Dry0.20.8

Initial probabilities: P(Rain)=0.4, P(Dry)=0.6. Rows describe the current state; columns describe the next state.

To find

The two-state joint probability and the one-step conditional probability.

Formula and why it applies

P(D,D)=P(D)P(D\mid D)LaTeX: P(D,D)=P(D)P(D\mid D)

The joint path includes an uncertain initial state. The conditional transition assumes the current state is already Dry.

Solution

Step 1. Read the conditional transition
P(D\mid D)=0.8LaTeX: P(D\mid D)=0.8
Step 2. Include the initial state for the joint path
P(D,D)=0.6\times0.8=0.48LaTeX: P(D,D)=0.6\times0.8=0.48
Final answer. P(Dry,Dry)=0.48; P(next Dry|current Dry)=0.8. These answer different questions.

Yaad rakho: Path: pehle start probability, phir har arrow ki probability.