MLE for the given MDP and Observation Sequence (RGB Color Cycler)

Question

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

Emission probabilities:  

R --> 1 (p=0.4), 2, (p=0.5), 3 (p-0.1)

G --> 1 (p=0.3), 2 (p=0.3), 3 (p=0.4) 

B --> 1 (p=0.4), 2 (p=0.1), 3 (p=0.1), 4 (p=0.4). 

Transition Matrix: R -> G (p = 1.0), G -> B (p = 1.0), B -> R (p = 1.0). 

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

What is the most likely explanation for this observation sequence?
Initial state is not known and is equally likely from all states.

Answer 1

Hello everyone!

As it is understandable, the problem has deterministic transitions (R-G-B-R-...) while asking for Maximum Likelihood Estimation, so considering the three possible starting phases, there are only three possible state sequences:

1. R G B R G B R G B
2. G B R G B R G B R
3. B R G B R G B R G

Using emission probabilities, we compare every sequence with observations and compute its likelihood.

Emission probabilities:

R → (1: 0.4, 2: 0.5, 3: 0.1)
G → (1: 0.3, 2: 0.3, 3: 0.4)
B → (1: 0.4, 2: 0.1, 3: 0.1, 4: 0.4)

Initial probability for each state = 1/3

Observations: 1, 2, 3, 4, 1, 3, 1, 2, 3

Starting with R:

R -> 1 (0.4)
G -> 2 (0.3)
B -> 3 (0.1)
R -> 4 (0) 

Sequence becomes invalid (probability = 0)

Starting with G:

G -> 1 (0.3)
B ->2 (0.1)
R -> 3 (0.1)
G -> 4 (0) 

Sequence becomes invalid (probability = 0)

Starting with B:

B → 1 (0.4)
R → 2 (0.5)
G → 3 (0.4)
B → 4 (0.4)
R → 1 (0.4)
G → 3 (0.4)
B → 1 (0.4)
R → 2 (0.5)
G → 3 (0.4)

All observations are valid, so we compute the total likelihood (non-zero)

After comparing all cases, only the sequence starting with B has a non-zero probability and thus gives the maximum likelihood.

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

Answer 2

Hello Professor!

From given question, we can observe that movement is fixed: R -> G -> B -> ....
So, the only issue here is to determine which color starts first?

From the emission probabilities, we can extract important detail: 

• P(4 | Red) = 0
• P(4 | Green) = 0
• P(4 | Blue) = 0.4

Thus, only Blue can produce observation 4, while Red and Green cannot. So in observation sequence the 4th position is Blue. 

Then by looking at transition matrix, 5th position will be Red, and 3th position will be Green, and so on. Following the transition matrix, the final sequence is going to be:

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

Answer 3

Hello, first of all I want to notice that transition probabilities are deterministic. Once we choose first hidden state the rest are known. Each state is equally likely to be initial so we can consider each.

1) R,G,B,R,G,B,R,G,B

2) G,B,R,G,B,R,G,B,R

3) B,R,G,B,R,G,B,R,G

R can not be in time step 4, so it is invalid. G can't be in 4 so it is also invalid. Third one is a valid explanation as all hidden states can omit corresponding time steps.

Answer 4

We are given an HMM with three states (R, G, B) and deterministic transitions:

R -> G, 

G -> B, 

B -> R

This means once a state is fixed at any time step, the entire sequence of states is determined.

The observation sequence is: 1, 2, 3, 4, 1, 3, 1, 2, 3

The key step is to look at observation 4. From the emission probabilities, only state B (Blue) can produce observation 4 (probability 0.4). Therefore, the hidden state at time step 4 must be B.

Using the deterministic transitions, we reconstruct the full sequence:

Since state4 = B, then state3 = G and state2 = R and state1 = B (going backward)

Going forward: state5 = R, state6 = G, state7 = B, state8 = R, state9 = G

So the most likely hidden state sequence is:

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

This is the most likely sequence because all other possible starting states would place either R or G at time step 4 but only B can emit observation 4

 

Answer 5

Looking at the observation - 1, 2, 3, 4, 1, 3, 1, 2, 3 - we can see the value of 4 at position 4. According to the emission probabilities, this is only possible if the hidden state at that position is B. Now, given the transition matrix, we can construct the following hidden sequence:
B, R, G, B, R, G, B, R, G

Answer 6

Hi, everyone,

Because transitions are deterministic, only 3 possible hidden-state sequences exist:

1. R G B R G B R G B
2. G B R G B R G B R
3. B R G B R G B R G

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

Compute emission likelihood for each:

1. R G B R G B R G B

(1/3) * (0.4) * (0.3) * (0.1) * (0) * (0.3) * (0.1) * (0.4) * (0.3) * (0.1) = 0

because R cannot emit 4.

2. G B R G B R G B R

(1/3) * (0.3) * (0.1) * (0.1) * (0) * (0.4) * (0.1) * (0.3) * (0.1) * (0.1) = 0

because G cannot emit 4.

3. B R G B R G B R G

(1/3) * (0.4) * (0.5) * (0.4) * (0.4) * (0.4) * (0.4) * (0.4) * (0.5) * (0.4)

= (1/3) * 0.001024
= 0.0003413

So the most likely explanation is:

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

Because only this sequence allows observation 4, which can only be emitted by Blue.

Answer 7

Because the transitions are deterministic (R → G → B → R → ...), once we pick a starting state, the entire sequence is fixed. So we only need to check the three possible starting points.

The key observation is that the value “4” appears at position 4. From the emission probabilities, only the Blue state can produce 4 with non-zero probability. This means the hidden state at time step 4 must be Blue.

Using the deterministic transitions, we reconstruct the full sequence. Going backward and forward from position 4, we get:

B → R → G → B → R → G → B → R → G

The other two possible sequences are invalid because they would require Red or Green to emit 4, which has probability 0.

Therefore, the sequence is:

B R G B R G B R G

Answer 8

Hello,

We have 3 hidden states:

R, G, B

Transitions are deterministic:

R -> G

G -> B

B -> R

So once the starting state is chosen, the whole state sequence is fixed.

Initial state is equally likely, so we only need to test the 3 possible starting points.

Observation sequence:

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

Possible hidden-state sequences:

1. Start from R:

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

Now check emissions:

R emits 1 with 0.4

G emits 2 with 0.3

B emits 3 with 0.1

R emits 4 with 0

Since R cannot emit 4, this path has probability 0.

2. Start from G:

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

Now check emissions:

G emits 1 with 0.3

B emits 2 with 0.1

R emits 3 with 0.1

G emits 4 with 0

Since G cannot emit 4, this path also has probability 0.

3. Start from B:

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

Now check emissions one by one:

B emits 1 with 0.4

R emits 2 with 0.5

G emits 3 with 0.4

B emits 4 with 0.4

R emits 1 with 0.4

G emits 3 with 0.4

B emits 1 with 0.4

R emits 2 with 0.5

G emits 3 with 0.4

So this path has probability:

0.4 * 0.5 * 0.4 * 0.4 * 0.4 * 0.4 * 0.4 * 0.5 * 0.4

= 0.0004096

If we include the initial probability:

P(start in B) = 1/3

then total probability is:

(1/3) * 0.0004096 = 0.000136533...

Since the other two paths have probability 0, this is the most likely explanation.

Final answer:

The most likely hidden-state sequence is:

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

So the observation sequence

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

is most likely generated by starting in Blue.

Answer 9

Hello Professor,

The transitions are deterministic:

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

This means that once the first hidden state is chosen, the rest of the hidden-state sequence is already fixed.

The observation sequence is:

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

Since the initial state is equally likely to be R, G, or B, we only need to check the three possible starting sequences.

If we start with R, the hidden-state sequence is:

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

But at time step 4, the hidden state would be R. This is impossible because R cannot emit observation 4. So this sequence has probability 0.

If we start with G, the hidden-state sequence is:

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

At time step 4, the hidden state would be G. This is also impossible because G cannot emit observation 4. So this sequence also has probability 0.

If we start with B, the hidden-state sequence is:

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

Now check the observations:

B emits 1 with probability 0.4
R emits 2 with probability 0.5
G emits 3 with probability 0.4
B emits 4 with probability 0.4
R emits 1 with probability 0.4
G emits 3 with probability 0.4
B emits 1 with probability 0.4
R emits 2 with probability 0.5
G emits 3 with probability 0.4

This is the only sequence where every observation has nonzero probability.

The likelihood is:

(1/3)(0.4)(0.5)(0.4)(0.4)(0.4)(0.4)(0.4)(0.5)(0.4)

First multiply the emission probabilities:

0.4 * 0.5 * 0.4 * 0.4 * 0.4 * 0.4 * 0.4 * 0.5 * 0.4 = 0.0004096

Including the initial probability:

(1/3) * 0.0004096 = 0.0001365

Since the other two possible sequences have probability 0, this one is the maximum likelihood explanation.

Final answer:

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

So the observation sequence was most likely generated by starting in Blue

Answer 10

Because the transitions are fixed (R→G→B→R…), the states must follow that cycle no matter what. So we just try possible starting states and see which one can actually produce the observations with nonzero probability.

Starting from Red or Green quickly fails because you hit an observation that those states cannot emit (like 4, which only Blue can produce).

Starting from Blue works for every observation in the sequence.

So the most likely explanation is the state sequence:

Blue → Red → Green → Blue → Red → Green → Blue → Red → Green