# Markov chains: read a transition table and multiply a path

Subject: Natural Language Processing

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/nlp/#tee/formulas/f-hmm/markov-chain

Canonical: https://deep-learning-study-room.vercel.app/read/nlp/tee/formulas/f-hmm--markov-chain/

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})
$$





$$
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 → next | Rain | Dry |
| --- | --- | --- |
| Rain | 0.3 | 0.7 |
| Dry | 0.2 | 0.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 → next | Rain | Dry |
| --- | --- | --- |
| Rain | 0.3 | 0.7 |
| Dry | 0.2 | 0.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)
$$



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.6
$$



##### Step 2. Move Dry to Dry



$$
0.6\times0.8=0.48
$$



##### Step 3. Move Dry to Rain



$$
0.48\times0.2=0.096
$$



##### Step 4. Move Rain to Rain



$$
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 → next | Rain | Dry |
| --- | --- | --- |
| Rain | 0.3 | 0.7 |
| Dry | 0.2 | 0.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)
$$



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

#### Solution

##### Step 1. Initial Rain



$$
P(R)=0.4
$$



##### Step 2. First transition



$$
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.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 → next | Rain | Dry |
| --- | --- | --- |
| Rain | 0.3 | 0.7 |
| Dry | 0.2 | 0.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)
$$



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.8
$$



##### Step 2. Include the initial state for the joint path



$$
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.