Intelligent Systems II · TEE · papers

Q1(d) Markov chain diagram and path probability [5]

Final examination · 17 Apr 2024

Actual historical paper ·100 marks attempted /140 offered · Q1 compulsory + any four of Q2–Q7. Source defects and solution assumptions are explicitly identified.

Question. Q1(d) [5 marks · 2024-04-17]

Consider the Markov chain with S={1,2,3} and transition matrix below. (a) Draw the state transition diagram. (b) The scan prints “P(X₁=1)=(X₂=2)=1/4”; calculate P(X₁=3, X₂=2, X₃=1).

P=\begin{bmatrix}1/2&1/4&1/4\\1/3&0&2/3\\1/2&1/2&0\end{bmatrix}LaTeX: P=\begin{bmatrix}1/2&1/4&1/4\\1/3&0&2/3\\1/2&1/2&0\end{bmatrix}

Answer

Given

The printed matrix; ambiguous condition reproduced above.

To find

All nonzero transitions and the joint probability of the path 3→2→1.

Formula and why it applies

Rows are current states and columns are next states. A specified path probability is initial-state probability multiplied by each transition along that path.

P(X_1=3,X_2=2,X_3=1)=P(X_1=3)P_{32}P_{21}LaTeX: P(X_1=3,X_2=2,X_3=1)=P(X_1=3)P_{32}P_{21}

Solution

Step 1. Draw the matrix as arrows
Swipe across the diagram to read its labels ↔
Redrawn transition diagram. Each arrow goes from the current state to the next state; labels are probabilities.
Diagram: Redrawn transition diagram. Each arrow goes from the current state to the next state; labels are probabilities.. Labels: legacy24-three-state | 0.5 | 0.25 | 0.25 | 0.333333 | 0.666667 | 0.5 | 0.5 | 1 | 2 | 3
Redrawn transition diagram. Each arrow goes from the current state to the next state; labels are probabilities.
FromOutgoing destinations
11 with 1/2; 2 with 1/4; 3 with 1/4
21 with 1/3; 3 with 2/3
31 with 1/2; 2 with 1/2
Step 2. Solve the literal reading

Let p₁=P(X₁=1)=1/4 and p₃=P(X₁=3). To be in state 2 at time 2, arrive from state 1 or state 3; transition 2→2 is zero.

\frac14=p_1P_{12}+p_2P_{22}+p_3P_{32}=\frac14\frac14+0+\frac12p_3LaTeX: \frac14=p_1P_{12}+p_2P_{22}+p_3P_{32}=\frac14\frac14+0+\frac12p_3
\frac12p_3=\frac14-\frac1{16}=\frac3{16}\quad\Rightarrow\quad p_3=\frac38LaTeX: \frac12p_3=\frac14-\frac1{16}=\frac3{16}\quad\Rightarrow\quad p_3=\frac38
P(3,2,1)=\frac38\cdot\frac12\cdot\frac13=\frac1{16}=0.0625LaTeX: P(3,2,1)=\frac38\cdot\frac12\cdot\frac13=\frac1{16}=0.0625
Step 3. Show the alternative if the second subscript was a typo

If the intended statement was P(X₁=1)=P(X₁=2)=1/4, then P(X₁=3)=1−1/4−1/4=1/2.

P(3,2,1)=\frac12\cdot\frac12\cdot\frac13=\frac1{12}\approx0.0833333LaTeX: P(3,2,1)=\frac12\cdot\frac12\cdot\frac13=\frac1{12}\approx0.0833333
Final answer. Literal time-2 condition gives 1/16. Corrected initial-state condition gives 1/12; the source wording must be clarified.