MLE for given HMM and Observation Sequence (Needs Computation)

Question

We are given an MDP with 3 states: Red, Green, Blue (RGB). 

Emission probabilities:  

R --> 1 (p=1/2), 2 (p=1/4), 3 (p=1/4)

G --> 1 (p=1/4), 2 (p=1/2), 3 (p=1/4)

B --> 1 (p=1/6), 2 (p=1/6), 3 (p=1/6), 4 (p=1/2)

Transition Matrix

R --> R (p=1/3), G (p=1/3), B (p=1/3)

G --> G (p=1/2), B (p=1/2)

B --> B (p=1)

These are the observations: 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 1

What is the most likely explanation for this observation sequence?
Initial state is R.

Answer 1

Hello professor,

I would treat this as a Viterbi decoding problem. The model parameters are already given, so we are not really estimating the HMM parameters. Instead, we are finding the most likely hidden state sequence that could have produced the observations.

The observations are: 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 1

The initial state is fixed as R, so under the usual HMM convention, the first observation is emitted from R.

The most likely hidden state sequence is: R, G, B, B, B, B, B, B, B, B, B

So the best explanation is: The system starts in Red, moves to Green for the second observation, then moves to Blue on the third observation, and stays in Blue for the rest of the sequence.

Here is the Viterbi computation. Each entry is the probability of the best path ending in that state after seeing the observation at that time.

Time	Obs	Best Ending in R	Best Ending in G	Best Ending in B
1	1	1/2	0	0
2	2	1/24	1/12	1/36
3	3	1/288	1/96	1/144
4	1	1/1728	1/768	1/864
5	1	1/10368	1/6144	1/5184
6	2	1/124416	1/24576	1/31104
7	1	1/746496	1/196608	1/186624
8	2	1/8957952	1/786432	1/1119744
9	3	1/107495424	1/6291456	1/6718464
10	1	1/644972544	1/50331648	1/40310784
11	1	1/3869835264	1/402653184	1/241864704

At the final observation, the largest value is for state B is 1/241864704, which is approximately 4.13e-9.

Backtracking through the Viterbi choices gives R, G, B, B, B, B, B, B, B, B, B

We can also directly compute the probability of that path:

R emits 1: 1/2

R to G, G emits 2: (1/3)(1/2)

G to B, B emits 3: (1/2)(1/6)

After that, Blue stays in Blue with probability 1, and each remaining observation is 1, 2, or 3, each of which Blue emits with probability 1/6.

So the total probability is (1/2)(1/3)(1/2)(1/2)(1/6)(1/6)^8. This simplifies to 1/241864704 or about 4.13e-9.

Even though Blue is not especially likely to emit 1, 2, or 3, it is an absorbing state. Once the model reaches Blue, it stays there with probability 1. For a long observation sequence, avoiding repeated transition penalties becomes very important, which is why the best path moves into Blue and remains there.

Final answer: R, G, B, B, B, B, B, B, B, B, B

Answer 2

Hello,

Initial state is fixed:

Start = R

Observations:

1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 1

Emission probabilities:

R:
1 -> 1/2, 2 -> 1/4, 3 -> 1/4

G:
1 -> 1/4, 2 -> 1/2, 3 -> 1/4

B:
1 -> 1/6, 2 -> 1/6, 3 -> 1/6, 4 -> 1/2

Transition probabilities:

R -> R, G, B each = 1/3

G -> G, B each = 1/2

B -> B = 1

Since this is a most likely explanation question, we compare paths by multiplying:

transition probability x emission probability at each step

Step 1:

Initial state is R, and first observation is 1.

So:

P = P(1|R) = 1/2

Now for observation 2:

From R we can go to R, G, or B.

R -> R:
(1/2)(1/3)(1/4) = 1/24

R -> G:
(1/2)(1/3)(1/2) = 1/12

R -> B:
(1/2)(1/3)(1/6) = 1/36

Best one is:

R, G

Now observation 3:

From G we can go to G or B.

R,G,G:
(1/12)(1/2)(1/4) = 1/96

R,G,B:
(1/12)(1/2)(1/6) = 1/144

But we should also compare with paths that ended in R and B at previous step.

From the full comparison, the largest value at step 3 is reached by:

R, G, B

with probability:

1/144

After this, B is very important because:

B -> B = 1

So once we move to B, there is no transition penalty anymore.

Now continue with the remaining observations:

1, 1, 2, 1, 2, 3, 1, 1

If we stay in B, each of these gives emission factor 1/6.

If we stay in G, transition gives extra factor 1/2 each time, and emissions are not always better enough to compensate.

So the best path remains in B from step 3 onward.

Thus the most likely hidden-state sequence is:

R, G, B, B, B, B, B, B, B, B, B

Check with observations:

Step 1: R emits 1 with 1/2

Step 2: G emits 2 with 1/2

Step 3: B emits 3 with 1/6

Step 4: B emits 1 with 1/6

Step 5: B emits 1 with 1/6

Step 6: B emits 2 with 1/6

Step 7: B emits 1 with 1/6

Step 8: B emits 2 with 1/6

Step 9: B emits 3 with 1/6

Step 10: B emits 1 with 1/6

Step 11: B emits 1 with 1/6

Total probability:

(1/2)(1/3)(1/2)(1/2)(1/6)(1)(1/6)(1)(1/6)(1)(1/6)(1)(1/6)(1)(1/6)(1)(1/6)(1)(1/6)(1)(1/6)

= 1 / 241864704

~= 4.13 x 10^-9

Final answer:

The most likely explanation is:

R, G, B, B, B, B, B, B, B, B, B

So the sequence starts in Red, moves to Green for the second observation, then moves to Blue and stays there until the end.

Answer 3

Hello,

The most likely state sequence is:

R, R, G, G, G, G, G, G, G, G, G

Reasoning:

1.  Trap State B: State Blue (B) is an absorbing state (B -> B with p=1). Once entered, the system never leaves. The emission probability of observation 1 from B is low (1/6), whereas from R or G it is higher (1/2 or 1/4). Since the sequence ends with multiple 1s and 2s, entering B early would result in a very low likelihood due to the poor fit of emissions and the inability to return to better-fitting states. Thus, the optimal path avoids B entirely.

2.  R vs G:

    * Observation 1: Emission prob is higher in R (1/2) than G (1/4).

    * Observation 2: Emission prob is higher in G (1/2) than R (1/4).

    * Observation 3: Equal for R and G (1/4).

3.  Path Analysis:

    * Start at R (given).

    * Observation 1: Stay in R (high emission 1/2, transition 1/3).

    * Observation 2: Switch to G (emission 1/2 vs R's 1/4). Transition R -> G is 1/3.

    * Observation 3: Stay in G (emission 1/4). Transition G -> G is 1/2.

    * Observation 1, 1, 2, 1, 2, 3, 1, 1: Remaining observations are best explained by staying in G. Although 1 is slightly better emitted by R, the cost of transitioning back to R (G -> R is impossible, must go G ->B -> ... which is bad, or just stay in G) makes staying in G optimal. Note: G -> R probability is 0. Only G -> G or G -> B can be gone. Since B is bad, stay in G is must.

Therefore, after the initial switch to G, the system remains in G for the rest of the sequence because there is no transition from G back to R.

Final Sequence:

t_1: R (Observation 1)

t_2: R (Observation 2) -> Wait, let's re-evaluate t_2.

At t_1, state is R. Observation is 1.

At t_2, Observation is 2.

Options from R:

- Go to R: P(O_2=2|R) P(R|R) = (1/4)*(1/3) = 1/12

- Go to G: P(O_2=2|G) P(G|R) = (1/2)*(1/3) = 1/6

- Go to B: P(O_2=2|B) P(B|R) = (1/6)*(1/3) = 1/18

Best is G. So t_2 is G? No, t_2 is the state generating observation 2.

Let's trace carefully:

State sequence S_1, S_2, ..., S_11.

S_1 = R.

O_1 = 1.

O_2 = 2.

Transition S_1 -> S_2.

If S_2=R: P(O_2|R)P(S_2|R) = (1/4)(1/3) = 1/12.

If S_2=G: P(O_2|G)P(S_2|R) = (1/2)(1/3) = 1/6.

If S_2=B: P(O_2|B)P(S_2|R) = (1/6)(1/3) = 1/18.

So S_2 = G is more likely than S_2=R.

However, check S_1's contribution. P(O_1|S_1=R) = 1/2.

Path so far: R -> G. Prob part: (1/2) * (1/3) * (1/2) = 1/12.

Alternative: R -> R. Prob part: (1/2) * (1/3) * (1/4) = 1/24.

So S_2=G is better.

From S_2=G, next is O_3=3.

G -> G: (1/4)(1/2) = 1/8.

G -> B: (1/4)(1/2) = 1/8.

Tie. But B is a trap. If it is gone to B, subsequent observation must be emitted by B.

O_4=1. P(1|B)=1/6. P(1|G)=1/4.

Since 1/4 > 1/6, staying in G is better for future observations.

So S_3=G.

Since G cannot transition to R, and B is suboptimal for the remaining mix of 1s, 2s, and 3s (especially 1s and 2s where G is strong), the system stays in G.

Corrected Sequence:

R, G, G, G, G, G, G, G, G, G, G

Answer 4

At each step, I choose the path with the highest probability.

Formula:

V(state) = previous probability x transition probability x emission probability

Observation sequence: 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 1

And the initial state is R.

Step 1: Observation 1:

Start at R. R emits 1 with probability 1/2. So, R = 1/2

Best state: R

Step 2: Observation = 2

From R:

R-> R: 1/2 x 1/3 x 1/4 = 1/24

R-> G: 1/2 x 1/3 x 1/2 = 1/12

R-> B: 1/2 x 1/3 x 1/6 = 1/36

Best stage: G

Step 3: Observation = 3

G-> G: 1/12 x 1/2 x q/4 = 1/96

G-> B: 1/12 x 1/2 x 1/6 =0,00694 1/144

Best state: G

Step 4: Observation = 1

From G:

G-> G 1/96 x 1/2 x 1/4 = 1/768

G-> B: 1/96 x 1/2 x 1/6 =0,000868 1/1152

But B can also continue later with probability 1. So the path changes to B after this point.

Step 5 onward:

Once the model reaches B, it stays in B because: B-> B = 1

So for the remaining observations, we only multiply by B emission probabilities. B emits:

1 with probability 1/6

2 with probability 1/6

3 with probability 1/6

Therefore the most likely path is:

R -> G -> B -> B -> B -> B -> B -> B -> B -> B -> B

Final answer: The most likely explanation is that the system starts in R moves to G then moves to B and stays in B until the end.

Answer 5

O=(1,2,3,1,1,2,1,2,3,1,1) Start: V1​(R)=1⋅P(1∣R)=1/2​, V1​(G)=0, V1​(B)=0

For observation 2: V2​(R)=1/4​⋅1/2​⋅1/3​=1/24​

 V2​(G)=1/2​⋅1/2​⋅1/3​=1/12​

V2​(B)=1/6​⋅1/2​⋅1/3​=1/36

For observation 3: 

V3​(R)=1/4​⋅1/24​⋅1/3​=1/288

V3​(G)=1/4​⋅max(1/24​⋅1/3​,1/12​⋅1/2​)=1/4​⋅1/24​=1/96​

V3​(B)=1/6​⋅max(1/24​⋅1/3​,1/12​⋅1/2​,1/36​⋅1)=1/6​⋅1/24​=1/144​

For observation 4

V4​(R)=1/2​⋅1/288​⋅1/3​=1/1728

V4​(G)=1/4​⋅max(1/288⋅1/3​,1/96​⋅1/2​)=1/4​⋅1/192​=1/768

V4​(B)=1/6​⋅max(1/288⋅1/3​,1/96​⋅1/2​,1/144⋅1)=1/864

At step 5 we will choose B. Because the best path enters B, and then: P(B→B)=1 so it stays in B until the end.After backtracking, the most likely sequence is: R, G, B, B, B, B, B, B, B, B, B

Answer 6

 Hello,

We are asked to find the most likely hidden state sequence that generated the observations:

1,2,3,1,1,2,1,2,3,1,1

The initial state is fixed:
q1​=R

This is a Hidden Markov Model problem, so we use the Viterbi algorithm. The goal is to maximize:
P(q1​,q2​,…,q11​,O1​,O2​,…,O11​)

where
qt​ are hidden states and Ot​ are observations.

Step 1: Model Information

States 
R = Red
G= Green 
B= Blue

Emission probabilities

P(1∣R)=1/2,P(2∣R)=1/4,P(3∣R)=1/4​

P(1∣G)=1/4,P(2∣G)=1/2,P(3∣G)=1/4​

P(1∣B)=1/6,P(2∣B)=1/6,P(3∣B)=1/6,P(4∣B)=1/2

Transition probabilities

From R:

P(R→R)=P(R→G)=P(R→B)=1/3

From G:

P(G→G)=1/2,

P(G→B)=1/2

From B:

P(B→B)=1 

P(B\to B)=1

Step 2: Important Observations

The sequence contains only symbols:

1,2,3

and never contains 4.

Since state B gives highest probability to observation 4, entering B is not favorable. Also, once we enter B, we cannot leave it because:

P(B→B)=1

So the optimal path is expected to avoid BB.

Also:

Observation 1 is most likely from R

Observation 2 is most likely from G 

Observation 3 gives equal probability for RRR and GGG

Step 3: Applying Viterbi Logic

We begin in RRR, so:

q1=R

For the first five observations:

1,2,3,1,11,2,3,1,1

remaining in
R gives a strong path because: 

many 1's favor R 

switching has transition cost

At observation 6 onward:

2,1,2,3,1,12,1,2,3,1,1

there are more 2's, making state G better overall. Since G can remain in itself with probability 1/2, switching once and staying there becomes optimal.

Step 4: Best State Sequence

The maximum-likelihood hidden path is:

R,R,R,R,R,G,G,G,G,G,GR,R,R,R,R,G,G,G,G,G,G

 

Answer 7

Hello,

I think the correct answer is:

R, G, B, B, B, B, B, B, B, B, B

Here is the reason.

Initial state is fixed:

S1 = R

The observation sequence is:

1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 1

We use the Viterbi idea:

previous probability × transition probability × emission probability

Step 1:

We start in R, and the first observation is 1.

P(1 | R) = 1/2

So:

V1(R) = 1/2

Step 2, observation is 2:

From R:

R -> R:

(1/2)(1/3)(1/4) = 1/24

R -> G:

(1/2)(1/3)(1/2) = 1/12

R -> B:

(1/2)(1/3)(1/6) = 1/36

The best state at step 2 is G.

Step 3, observation is 3:

For G:

(1/12)(1/2)(1/4) = 1/96

For B:

(1/12)(1/2)(1/6) = 1/144

At this step, G is still better than B.

But we should not ignore B, because B is an absorbing state:

B -> B = 1

This means once the path enters B, it stays in B and does not pay any more transition cost.

This is the key point.

If we stay in G, we keep multiplying by the transition probability:

G -> G = 1/2

But if we enter B, we multiply by:

B -> B = 1

So after a few more steps, the B path becomes more likely, even though B has weaker emission probabilities for 1, 2, and 3.

When we continue the Viterbi calculation until the end, the best final path is:

R, G, B, B, B, B, B, B, B, B, B

The probability of this path is:

(1/2)(1/3)(1/2)(1/2)(1/6)(1)(1/6)(1)(1/6)(1)(1/6)(1)(1/6)(1)(1/6)(1)(1/6)(1)(1/6)(1)(1/6)

= 1 / 241864704

≈ 4.13 × 10^-9

So the most likely explanation is that the system starts in Red, moves to Green for the second observation, then moves to Blue and stays there until the end.

Final answer:

R, G, B, B, B, B, B, B, B, B, B

Answer 8

Most likely hidden state sequence:

Hi, everyone,

R, G, B, B, B, B, B, B, B, B, B

Explanation: Start in Red → move to Green → move to Blue → stay in Blue forever.

This is because Blue is an absorbing state:
P(B → B) = 1

Best final Viterbi probability:

1 / 241864704 ≈ 4.13 × 10⁻⁹

Observations:

1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 1

Final answer:

R, G, B, B, B, B, B, B, B, B, B