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 professor, To find the most likely sequence of states, we evaluate the possible paths based on the deterministic Transition Matrix. Because each state has only one possible next state (R to G, G to B, B to R), the entire sequence is locked once the starting state is chosen. There are three potential paths for the 9 observations: Path A: Red, Green, Blue, Red, Green, Blue, Red, Green, Blue Path B: Green, Blue, Red, Green, Blue, Red, Green, Blue, Red Path C: Blue, Red, Green, Blue, Red, Green, Blue, Red, Green By looking at the 4th observation, which is "4", we can immediately identify the correct path: Red cannot emit a 4 (p=0). Green cannot emit a 4 (p=0). Blue is the only state that can emit a 4 (p=0.4). In Path A and B, the 4th state is Red and Green respectively, making those paths impossible. In Path C, the 4th state is Blue, which is consistent with the data. Conclusion: The most likely explanation is Path C: Blue -> Red -> Green -> Blue -> Red -> Green -> Blue -> Red -> Green Probability: (1/3) * (0.4 * 0.5 * 0.4 * 0.4 * 0.4 * 0.1 * 0.4 * 0.5 * 0.4) = 0.00003413

Answer 2

Given the deterministic cycle (R > G > B > R), there are only three possible paths. We can identify the correct one by looking at the 4th observation, "4".

Only the Blue state can emit a 4. Since Path 1 (starting with R) and Path 2 (starting with G) place Red and Green at the 4th position respectively, they are impossible (p=0).

Most likely sequence (Path 3):

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

Total Probability:

(1/3) * (0.4 * 0.5 * 0.4 * 0.4 * 0.4 * 0.1 * 0.4 * 0.5 * 0.4) = 0.00003413

Answer 3

Hello,

Given the deterministic cycle (R > G > B > R), there are only three possible paths. We can identify the correct one by looking at the 4th observation, "4".

Only the Blue state can emit a 4. Since Path 1 (starting with R) and Path 2 (starting with G) place Red and Green at the 4th position respectively, they are impossible (p=0).

Most likely sequence (Path 3):

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

Total Probability:

(1/3) * (0.4 * 0.5 * 0.4 * 0.4 * 0.4 * 0.1 * 0.4 * 0.5 * 0.4) = 0.00003413

Answer 4

Hi professor,

The first thing I noticed is that the transition probabilities are fully deterministic, meaning once we fix the initial state, the entire sequence of hidden states is determined. Since the initial state is equally likely to be any of the three, we just need to check all three possible sequences:

Starting at R: R, G, B, R, G, B, R, G, B

Starting at G: G, B, R, G, B, R, G, B, R

Starting at B: B, R, G, B, R, G, B, R, G

Now we check which sequences are valid given the observations 1, 2, 3, 4, 1, 3, 1, 2, 3. The key constraint is that observation 4 appears at time step 4, and only state B can emit observation 4. So whichever hidden state sits at position 4 must be B.

In sequence 1, position 4 is R, which cannot emit 4, so this is invalid. In sequence 2, position 4 is G, which also cannot emit 4, so this is also invalid. In sequence 3, position 4 is B, which can emit 4 with probability 0.4, so this sequence remains valid.

Therefore the most likely explanation is starting at B and following the sequence B, R, G, B, R, G, B, R, G, since it is the only one consistent.

Answer 5

Most likely explanation: Green -> Blue ->Red->Green -> Blue -> Red -> Green ->Blue->Red

Once we choose the starting state, the whole hidden state sequence is fixed.

Because the initial state is equally likely, we test all 3 possible starting states.

Case 1: Start with Red

State sequence:

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

Observation probabilities:

P(1 | R) = 0.4

P(2 | G) = 0.3

P(3 | B) = 0.1

P(4 | R) = 0

P(1 | G) = 0.3

P(3 | B) = 0.1

P(1 | R) = 0.4

P(2 | G) = 0.3

P(3 | B) = 0.1

Since Red cannot emit observation 4, this whole probability becomes 0.

So:

P(sequence | start R) = 0

Case 2: Start with Green

State sequence:

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

Observation probabilities:

P(1 | G) = 0.3

P(2 | B) = 0.1

P(3 | R) = 0.1

P(4 | G) = 0

P(1 | B) = 0.4

P(3 | R) = 0.1

P(1 | G) = 0.3

P(2 | B) = 0.1

P(3 | R) = 0.1

Since Green cannot emit observation 4, this whole probability becomes 0.

So:

P(sequence | start G) = 0

Case 3: Start with Blue

State sequence:

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

Observation probabilities:

P(1 | B) = 0.4

P(2 | R) = 0.5

P(3 | G) = 0.4

P(4 | B) = 0.4

P(1 | R) = 0.4

P(3 | G) = 0.4

P(1 | B) = 0.4

P(2 | R) = 0.5

P(3 | G) = 0.4

Now multiply them:

0.4 × 0.5 × 0.4 × 0.4 × 0.4 × 0.4 × 0.4 × 0.5 × 0.4

= 0.0004096

The initial state probability is 1/3, so the full probability is:

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

However, since all initial states are equally likely, we can compare only the emission products.

The only possible nonzero explanation is:

Blue ->Red -> Green-> Blue-> Red-> Green -> Blue -> Red->Green

Therefore, the most likely hidden state sequence is:

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

Answer 6

Hello,

Explanation:

1.  Deterministic Transitions: The states follow a strict cycle: R -> G -> B -> R -> G. You cannot stay in a state or skip one.

2.  Observation Check:

    *   Observation 4 appears at index 4. Only state Blue can emit 4 (probability 0.4). Therefore, the state at step 4 must be Blue.

    *   Working backward and forward from Step 4 (Blue) using the cycle R -> G -> B:

        *   Step 4: Blue

        *   Step 3: Red (precedes Blue)

        *   Step 2: Green (precedes Red)

        *   Step 1: Blue (precedes Green)? Let's check the start.

    

    Let's test the three possible starting positions for the cycle against the observations:

    *   Case 1: Start with Red (Sequence: R, G, B, R, G, B, R, G, B)

        *   Obs 1 (State R): P(1|R) = 0.4

        *   Obs 2 (State G): P(2|G) = 0.3

        *   Obs 3 (State B): P(3|B) = 0.1

        *   Obs 4 (State R): P(4|R) = 0 (Impossible)

    *   Case 2: Start with Green (Sequence: G, B, R, G, B, R, G, B, R)

        *   Obs 1 (State G): P(1|G) = 0.3

        *   Obs 2 (State B): P(2|B) = 0.1

        *   Obs 3 (State R): P(3|R) = 0.1

        *   Obs 4 (State G): P(4|G) = 0 (Impossible)

    *   Case 3: Start with Blue (Sequence: B, R, G, B, R, G, B, R, G)

        *   Obs 1 (State B): P(1|B) = 0.4

        *   Obs 2 (State R): P(2|R) = 0.5

        *   Obs 3 (State G): P(3|G) = 0.4

        *   Obs 4 (State B): P(4|B) = 0.4

        *   Obs 5 (State R): P(1|R) = 0.4

        *   Obs 6 (State G): P(3|G) = 0.4

        *   Obs 7 (State B): P(1|B) = 0.4

        *   Obs 8 (State R): P(2|R) = 0.5

        *   Obs 9 (State G): P(3|G) = 0.4        

    Only Case 3 is possible because it is the only one that allows Observation 4 to be emitted (by Blue) and Observation 4 to be emitted again? No, Obs 4 is only at index 4. But wait, in Case 1 and 2, the state at index 4 was R and G respectively, neither of which can emit 4. Only Blue emits 4. In the cycle $R \to G \to B$, Blue appears at positions 3, 6, 9 if starting at R; positions 2, 5, 8 if starting at G; and positions 1, 4, 7 if starting at B.

    Since Observation 4 is at index 4, the state at index 4 MUST be Blue. This aligns perfectly with Case 3 (Start with Blue).

The sequence is Blue, Red, Green, Blue, Red, Green, Blue, Red, Green.