Fig. 10.1. Polytopes of two-state toric Viterbi sequences.
The vertices share the labels listed in Table 10.1. Black vertices represent Viterbi sequences, and white vertices represent pseudo-Viterbi sequences. The third and sixth columns of Table 10.1 represent the coordinates of each vertex. These coordinates represent the frequencies of the transitions 00, 01, 10, and 11. Since (01)m0 has 0 instances of 00 and 11, m instances of 01, and m instances of 10, that sequence is represented by the vertex (0, m,m, 0). Although the points occupy a 4-dimensional space, the polytope itself is only 3-dimensional.
When l = 3 states, the number of toric Viterbi sequences that start with state 0 is 93 for even n and 95 for odd n, when n > 12. These sequences are enumerated in [Kuo, 2005]. Of these sequences, only four are pseudo-Viterbi. All four pseudo-Viterbi sequences on 3 states can end in 11210 or some symmetric variant such as 00102.
Proposition 10.4 A Viterbi sequence (or an equivalent sequence) on three states cannot end with 11210, or equivalently, 12110.
Proof Suppose that a Viterbi sequence could end with 11210. Since the sequence ends with 10, we must have 01o > 0n. Since 110 is a Viterbi subsequence with higher probability than 100, we also have 0n > 0oo. Thus 01o > #00. Moreover, since p110 > p101, we must have 0n01o > 01o0o1, which means 0n > 0o1. Finally, 112 has higher probability than 102, so 011012 > 010002. Then
where we use the fact that 0io > 0n. Thus
1 = 0io + 0ii + 012 > 0oo + 0oi + 002 = 1 which is a contradiction.
However, 0212110 is a toric Viterbi sequence for the toric Markov chain with the following transition matrix:
Was this article helpful?