A Novel Method for Decoding Any High-Order Hidden Markov Model

Definition 1 (see [18], [20].)A high-order hidden Markov model is a doubly stochastic process with an underlying state process that is not directly observable but can be observed only through another stochastic process that is called the observation process. The observation process is governed by the hidden state process and produces the observation sequence. The state process and observation process, respectively, satisfy the following conditions.

• (a)

  The hidden state process $$ is a homogeneous Markov chain of order n, that is, a stochastic process that satisfies

  $$ ()

• (b)

  The observation process {o_t} is governed by the hidden state process according to a set of probability distributions that satisfy

  $$ ()

Definition 2 (see [18].)Let

be the mapping of any base N number to its decimal value; that is, if $$, then

Definition 3 (see [17].)Any two models λ₁ and λ₂ are defined as equivalent if

for any arbitrary observation sequence O. In other words, two models are only considered equivalent if they yield the same likelihood, regardless of the specific observation sequence.

Remark 4. The function f is a one to one correspondence between the set $$ and the set S = {0,1, …, N^r − 1}.

Proposition 5 (see [18].)Let a_ij = P(q_t+1 = j∣q_t = i) for any i, j ∈ S. If ⌊i/N⌋≠j − ⌊j/N^r−1⌋N^r−1, then a_ij = 0; that is, a transition from q_t = i to q_t+1 = j is impossible.

Lemma 6. Let $$; then the process {q_t} forms the first-order homogeneous Markov chain.

Proof. Without loss of generality, we may assume that q_t = i and q_t+1 = j, where i, j ∈ S.

First, we consider the case that ⌊i/N⌋≠j − ⌊j/N^r−1⌋N^r−1. By Proposition 5, it is easy to see that

Next, we consider the case that ⌊i/N⌋ = j − ⌊j/N^r−1⌋N^r−1. Since q_t = i and q_t+1 = j, it follows from (10) that

where $$. Moreover, we have

Through the above analysis, we derive that

Analogously, it is easy to see that

Therefore, the process {q_t} forms the first-order homogeneous Markov chain.

Lemma 7. The two processes {q_t} and {o_t} form the first-order hidden Markov model.

Proof. Without loss of generality, we may assume that $$ and q_t = i, where $$ and i ∈ S. Since q_t = i, it follows from (10) that

where $$. Moreover, we have

Analogously, it is easy to see that

Combining these with Lemma 6, we prove that the two processes {q_t} and {o_t} form the first-order hidden Markov model.

Remark 8. Hadar and Messer [18] had also mentioned the fact that the two processes {q_t} and {o_t} form the first-order hidden Markov model, but they did not discuss and prove it in detail.

Proposition 9 (see [18].)Let i = f([i₁, …, i_r]) and j = f([i₀, …, i_r−1]) for any $$; then

Lemma 10. Let O = o₁ ⋯ o_T be any arbitrary observation sequence; then

That is, the high-order hidden Markov model $$ is equivalent to the first-order hidden Markov model {q_t, o_t}.

Proof. For any $$, let

By Proposition 9, we have

Remark 11. Hadar and Messer [18] had also mentioned the fact that the high-order hidden Markov model $$ is equivalent to the first-order hidden Markov model {q_t, o_t}, but they did not discuss and prove it in detail.

Theorem 12. Let O = o₁ ⋯ o_T be any given observation sequence, and assume that $$; then

Proof. Without loss of generality, let $$, where $$. According to Proposition 9, we have

where j_t = f([i_t, …, i_t−(r−1)]) for 1 ≤ t ≤ T.

On the other hand, it is easy to see that

Hence, by Lemma 10, we have

Theorem 13. Let O = o₁ ⋯ o_T be any given observation sequence, and assume that the state sequence $$ satisfies

that is, the state sequence $$ is some optimal state sequence of the high-order hidden Markov model $$. Let $$  (1 ≤ t ≤ T); then the state sequence $$ satisfies That is, the state sequence $$ is some optimal state sequence of the first hidden Markov model {q_t, o_t}.

Proof. By Theorem 12, it is easy to see that

Meanwhile, we have the equation Hence, we drive that

Theorem 14. Let O = o₁ ⋯ o_T be any given observation sequence, and assume that the state sequence $$ satisfies

that is, the state sequence $$ is some optimal state sequence of the first-order hidden Markov model {q_t, o_t}. For 1 ≤ t ≤ T, let then the state sequence $$ satisfies That is, the state sequence $$ is some optimal state sequence of the high-order hidden Markov model $$.

Remark 15. Combining Theorem 13 with Theorem 14, it is known that there exists a one to one correspondence between the optimal state sequence of the high-order hidden Markov model $$ and the optimal state sequence of the first-order hidden Markov model {q_t, o_t}.

Step 1. Determine some optimal state sequence $$ of the first-order hidden Markov model {q_t, o_t} by using the Viterbi algorithm. Without loss of generality, let

where j₁, j₂, …, j_T ∈ S.

Step 2. For $$, using the transformations

we have

Step 3. For $$, $$, using the transformation

we have