Help solving Bigram Model with the following probabilities I came across the following problem involving bigram models which I am struggling to solve. Following this tutorial I have a basic understanding of how bigram possibilities are calculated.

Problem:

Let's consider sequences of length 6 made out of characters ['i', 'p', 'e', 'a', 'n', 'o']. There are 6^6 such sequences.

We consider bigram model with the following probabilities:



For the first character in the sequence:

$p( 'o' ) = 0.05;$ $p( 'p' ) = 0.00;$ $p( 'e' ) = 0.03;$ $p( 'n' ) = 0.76;$ $p( 'a' ) = 0.07;$ $p( 'i' ) = 0.09;$ 

in short: $[0.05, 0, 0.03, 0.76, 0.07, 0.09]$

For the transitions:

$p( 'o' | 'o' ) = 0.73;$ $p( 'p' | 'o' ) = 0.02;$ $p( 'e' | 'o' ) = 0.04;$ $p( 'n' | 'o' ) = 0.07;$ $p( 'a' | 'o' ) = 0.06;$ $p( 'i' | 'o' ) = 0.08;$ 

in short: $[0.73, 0.02, 0.04, 0.07, 0.06, 0.08]$

$p( 'o' | 'p' ) = 0.01;$ $p( 'p' | 'p' ) = 0.06;$ $p( 'e' | 'p' ) = 0.07;$ $p( 'n' | 'p' ) = 0.07;$ $p( 'a' | 'p' ) = 0.08;$ $p( 'i' | 'p' ) = 0.71;$ 

in short: $[0.01, 0.06, 0.07, 0.07, 0.08, 0.71]$

$( 'o' | 'e' ) = 0.09;$ $p( 'p' | 'e' ) = 0.08;$ $p( 'e' | 'e' ) = 0.09;$ $p( 'n' | 'e' ) = 0.71;$ $p( 'a' | 'e' ) = 0.03;$ $p( 'i' | 'e' ) = 0.00;$

in short: $[0.09, 0.08, 0.09, 0.71, 0.03, 0]$

$p( 'o' | 'n' ) = 0.05;$ $p( 'p' | 'n' ) = 0.00;$ $p( 'e' | 'n' ) = 0.02;$ $p( 'n' | 'n' ) = 0.84;$ $p( 'a' | 'n' ) = 0.08;$ $p( 'i' | 'n' ) = 0.01;$ 

in short: $[0.05, 0, 0.02, 0.84, 0.08, 0.01]$

$p( 'o' | 'a' ) = 0.03;$ $p( 'p' | 'a' ) = 0.80;$ $p( 'e' | 'a' ) = 0.07;$ $p( 'n' | 'a' ) = 0.00;$ $p( 'a' | 'a' ) = 0.01;$ $p( 'i' | 'a' ) = 0.09;$ 

in short: $[0.03, 0.8, 0.07, 0, 0.01, 0.09]$

$p( 'o' | 'i' ) = 0.00;$ $p( 'p' | 'i' ) = 0.04;$ $p( 'e' | 'i' ) = 0.07;$ $p( 'n' | 'i' ) = 0.03;$ $p( 'a' | 'i' ) = 0.79;$ $p( 'i' | 'i' ) = 0.07;$

in short: $[0, 0.04, 0.07, 0.03, 0.79, 0.07]$



Find the most probable sequence in this model and write the answer here:

I am a complete beginner in this field so please bear with me.

So far:


The first character is $'n'$ with the highest probability of $0.76$.
Next I need to find the probability of which letter follows $'n'$. This is the 4th transition. 
$p( 'n' | 'n' ) = 0.84$ seems to have the highest probability, so $'n'$ is followed by 'n' and so on.
$'n', 'n', 'n', 'n', 'n', 'n'$


How would one go about computing the 6^6 possibilities?
I think brute force is the only method. There might be some complicated reductions but that would be outside the scope of the tutorial.

Brute force isn't unreasonable here since there are only 46656 possible combinations. Even python should iterate through it in a couple of seconds.

This is straight forward tree-search problem, where each node's values is a conditional probability. The hardest part of it is having to manually type all the conditional probabilities in.