Factorizing Sequence Likelihoods by Hidden Paths

Observation Likelihoods as Sums over Paths

In a hidden Markov model, an observed sequence can be compatible with many different sequences of hidden states. Its likelihood must account for all of them: a path contributes according to its probability under the hidden-state model and the probability of producing the observations along that path. This direct calculation makes the model’s joint structure concrete, and it also exposes a computational limitation: the number of possible hidden paths grows rapidly with sequence length.

Consider a probability space $(\Omega,\mathcal{F},\mathbb{P})$, a finite hidden state space $S=\{1,\ldots,K\}$, and a categorical observation alphabet $\mathcal{Y}$. For a sequence of length $T\ge1$, the hidden process is $(X_n)_{1\le n\le T}$ and the observations are $(Y_n)_{1\le n\le T}$. The hidden states form a Markov chain with initial distribution $\mu$, written as a row vector, and row-stochastic transition matrix $P=(p_{ij})$. Thus $\sum_{j\in S}p_{ij}=1$ for every $i$. In a categorical-emission model, define $b_i(y)=\mathbb{P}(Y_n=y\mid X_n=i)$, with $\sum_{y\in\mathcal{Y}}b_i(y)=1$ for every state $i$.

The HMM joint-probability model says that, given the hidden states, the observations are conditionally independent, and the distribution of $Y_n$ depends on the hidden path only through $X_n$. For a fixed observed sequence $y_{1:T}=(y_1,\ldots,y_T)$, its likelihood is the probability of the event $Y_1=y_1,\ldots,Y_T=y_T$, viewed as a function of the model parameters.

Definition (Hidden-path contribution): For a hidden path $x_{1:T}=(x_1,\ldots,x_T)\in S^T$, its contribution to the likelihood of $y_{1:T}$ is $$ c(x_{1:T};y_{1:T}) =\mu_{x_1}\left(\prod_{n=1}^{T-1}p_{x_nx_{n+1}}\right) \left(\prod_{n=1}^{T}b_{x_n}(y_n)\right). $$ An empty transition product, as occurs when $T=1$, is defined to be $1$. The observation-sequence likelihood is the sum of these contributions over all hidden paths.

Why the Path Factorization Holds

The formula separates three ingredients: the initial probability of the first hidden state, the probabilities of the successive hidden-state transitions, and the emission probabilities for the observations. The distinction between a joint probability and a conditional probability matters here. Conditioning on a specified hidden path is only legitimate when that path has positive probability.

Theorem (Path-sum factorization): Under the HMM joint-probability model just described, for every $x_{1:T}\in S^T$ and $y_{1:T}\in\mathcal{Y}^T$, $$ \mathbb{P}(X_{1:T}=x_{1:T},Y_{1:T}=y_{1:T}) =c(x_{1:T};y_{1:T}). $$ Consequently, $$ \mathbb{P}(Y_{1:T}=y_{1:T}) =\sum_{x_{1:T}\in S^T}c(x_{1:T};y_{1:T}). $$

Proof. First suppose the hidden path has positive probability. By conditional probability and the HMM conditional-independence assumption, $\mathbb{P}(Y_{1:T}=y_{1:T}\mid X_{1:T}=x_{1:T})=\prod_{n=1}^{T}b_{x_n}(y_n)$. The Markov property gives $\mathbb{P}(X_{1:T}=x_{1:T})=\mu_{x_1}\prod_{n=1}^{T-1}p_{x_nx_{n+1}}$. Multiplying these expressions gives the asserted joint probability. Now suppose the hidden path has probability zero. Its joint probability with the observations is zero because the joint event is a subset of the hidden-path event. The hidden-path probability is the product of the initial and transition factors, so that product is zero; multiplying it by the emission factors still gives zero. Thus the joint-probability identity holds in both cases, without conditioning on a probability-zero path. Finally, the events $\{X_{1:T}=x_{1:T}\}$, as $x_{1:T}$ ranges over $S^T$, are disjoint and together exhaust the sample space. Intersecting them with $\{Y_{1:T}=y_{1:T}\}$ partitions that observation event, so finite additivity gives the stated sum. $\square$

This is a sum of probabilities, not a choice of one “best” hidden path. Even a path with a small contribution belongs in the likelihood, and paths with zero contribution are harmless terms. Also, the likelihood is the probability of the observed event; it does not require conditioning on that event. If the observed event has probability zero, a conditional distribution given those observations is not defined, but the likelihood identity remains valid.

Worked Example: Summing Four Contributions

Let $S=\{1,2\}$, $\mathcal{Y}=\{a,b\}$, and $\mu=(\tfrac12,\tfrac12)$. Take $P=\begin{bmatrix}\tfrac14&\tfrac34\\[2pt]\tfrac12&\tfrac12\end{bmatrix}$. Its first row sums to $\tfrac14+\tfrac34=1$, and its second row sums to $\tfrac12+\tfrac12=1$. Let $b_1(a)=\tfrac34,\ b_1(b)=\tfrac14,\ b_2(a)=\tfrac14,\ b_2(b)=\tfrac34$; each state’s emission probabilities sum to $1$. Find the likelihood of the sequence $aa$.

There are $2^2=4$ hidden paths. Substituting the initial, transition, and emission probabilities into the path formula gives

\begin{aligned} c(11;aa)&=\tfrac12\cdot\tfrac14\cdot\tfrac34\cdot\tfrac34=\tfrac9{128},\\ c(12;aa)&=\tfrac12\cdot\tfrac34\cdot\tfrac34\cdot\tfrac14=\tfrac9{128},\\ c(21;aa)&=\tfrac12\cdot\tfrac12\cdot\tfrac14\cdot\tfrac34=\tfrac3{64},\\ c(22;aa)&=\tfrac12\cdot\tfrac12\cdot\tfrac14\cdot\tfrac14=\tfrac1{64}. \end{aligned}

Adding the four terms, with a common denominator of $128$, gives $\mathbb{P}(Y_1=a,Y_2=a)=\tfrac9{128}+\tfrac9{128}+\tfrac6{128}+\tfrac2{128}=\tfrac{26}{128}=\tfrac{13}{64}$. The largest individual contribution is $\tfrac9{128}$, attained by paths $11$ and $12$; neither path alone is the sequence likelihood.

Check by grouping on the first state. The terms beginning with state $1$ sum to $\tfrac9{128}+\tfrac9{128}=\tfrac{18}{128}=\tfrac9{64}$. Those beginning with state $2$ sum to $\tfrac6{128}+\tfrac2{128}=\tfrac8{128}=\tfrac1{16}$. Their sum is $\tfrac9{64}+\tfrac1{16}=\tfrac9{64}+\tfrac4{64}=\tfrac{13}{64}$, as before.

Zero Contributions and Support Restrictions

A path contributes zero if its initial probability, one of its transition probabilities, or one of its emission probabilities is zero. This does not change the path-sum identity. It can, however, make a model’s possible paths easier to identify. The next example explicitly lists the paths so that zero terms are not confused with undefined conditional probabilities.

Worked Example: A Deterministic Emission Sequence

Let $S=\{1,2\}$, $\mathcal{Y}=\{A,B\}$, and $\mu=(\tfrac13,\tfrac23)$. Use $P=\begin{bmatrix}\tfrac12&\tfrac12\\[2pt]\tfrac14&\tfrac34\end{bmatrix}$. The row sums are $\tfrac12+\tfrac12=1$ and $\tfrac14+\tfrac34=1$. State $1$ emits $A$ with probability $1$, while state $2$ emits $B$ with probability $1$; these are categorical distributions because the other symbol has probability zero in each state. Find the likelihood of $ABA$.

There are $2^3=8$ paths. The observation at each time forces the corresponding state: $A$ requires state $1$, $B$ requires state $2$, and $A$ requires state $1$. Thus path $121$ has emission product $1$, while every other path has at least one zero emission factor. For the compatible path,

c(121;ABA) =\tfrac13\cdot\tfrac12\cdot\tfrac14\cdot1\cdot1\cdot1 =\tfrac1{24}.

Each of the other seven contributions is zero, so $\mathbb{P}(Y_1=A,Y_2=B,Y_3=A)=\tfrac1{24}$. The hidden path $121$ itself has probability $\tfrac13\cdot\tfrac12\cdot\tfrac14=\tfrac1{24}$, which checks the answer: whenever this path occurs, it produces $ABA$ with probability $1$.

How Direct Enumeration Grows

With $K$ hidden states and $T$ observations, each of the $T$ positions in a hidden path can take $K$ values. Therefore there are $K^T$ possible paths. Evaluating each contribution separately requires a number of factors proportional to $T$; the direct path-by-path calculation consequently takes on the order of $T K^T$ arithmetic operations in a straightforward implementation. This describes direct enumeration, not a lower bound on every possible method of computing the likelihood.

Proposition (Path count and direct-enumeration cost): For a finite hidden state space with $K\ge1$ states and a sequence of length $T\ge1$, the sum over hidden paths has exactly $K^T$ indexed terms. A direct method that evaluates each term separately uses work proportional to $T K^T$. For fixed $K\ge2$, this work grows exponentially in $T$; when $K=1$, there is only one path.

Proof. At the first position there are $K$ choices. For each choice at the first position there are $K$ choices at the second, giving $K^2$ paths of length two. Repeating this multiplication for all $T$ positions gives $K^T$ paths. Each contribution uses one initial factor, $T-1$ transition factors, and $T$ emission factors, a total of $2T$ factors; evaluating it separately therefore takes work proportional to $T$. Repeating that evaluation for $K^T$ paths gives work proportional to $TK^T$. If $K\ge2$, then increasing $T$ by one multiplies the number of paths by $K$, so the path count is exponential in $T$. If $K=1$, $1^T=1$, and there is exactly one path. $\square$

Worked Example: Counting the Terms for Three States

Let $K=3$ and $T=4$. A path is a four-entry sequence, with three choices at each position, so the direct sum has $3^4=3\cdot3\cdot3\cdot3=81$ terms. Increasing the length to $T=5$ gives $3^5=3\cdot81=243$ terms: the extra time position triples the number of paths.

For a concrete likelihood at length one, let $\mu=(\tfrac12,\tfrac13,\tfrac16)$, and let the observation alphabet be $\{u,v\}$. Set $b_1(u)=\tfrac12,\ b_2(u)=\tfrac14,\ b_3(u)=\tfrac34$, with $b_i(v)=1-b_i(u)$ in each state. These give valid emission distributions: the probabilities of $u,v$ are $(\tfrac12,\tfrac12)$, $(\tfrac14,\tfrac34)$, and $(\tfrac34,\tfrac14)$ in states $1,2,3$, respectively. The initial probabilities sum to $\tfrac12+\tfrac13+\tfrac16=1$. For completeness, take $P=\begin{bmatrix}\tfrac12&\tfrac13&\tfrac16\\[2pt]\tfrac14&\tfrac12&\tfrac14\\[2pt]\tfrac13&\tfrac13&\tfrac13\end{bmatrix}$. Its rows sum to $\tfrac12+\tfrac13+\tfrac16=1$, $\tfrac14+\tfrac12+\tfrac14=1$, and $\tfrac13+\tfrac13+\tfrac13=1$. Since $T=1$, no transition factor enters the likelihood of $u$.

The three paths of length one contribute $\tfrac12\cdot\tfrac12=\tfrac14$, $\tfrac13\cdot\tfrac14=\tfrac1{12}$, and $\tfrac16\cdot\tfrac34=\tfrac18$. Thus $\mathbb{P}(Y_1=u)=\tfrac14+\tfrac1{12}+\tfrac18=\tfrac6{24}+\tfrac2{24}+\tfrac3{24}=\tfrac{11}{24}$.

Check: For $v$, the three path contributions are $\tfrac12\cdot\tfrac12=\tfrac14$, $\tfrac13\cdot\tfrac34=\tfrac14$, and $\tfrac16\cdot\tfrac14=\tfrac1{24}$. They sum to $\tfrac6{24}+\tfrac6{24}+\tfrac1{24}=\tfrac{13}{24}$, and $\tfrac{11}{24}+\tfrac{13}{24}=1$, as required for the two possible observations.

Interpretation and a Common Mistake

Each path contribution is a nonnegative part of the observation probability. The sum accounts for uncertainty about which hidden path occurred; it does not assert that the observations determine a unique path, nor does it select the path with the largest contribution. The path with the largest contribution can be useful for a different question, but its contribution alone is not the observation likelihood.

Common mistake: reporting one path contribution as the likelihood. In the first example, path $11$ contributes $\tfrac9{128}$. Reporting $\tfrac9{128}$ as the likelihood drops paths $12$, $21$, and $22$. The correction is to add all four contributions: $\tfrac9{128}+\tfrac9{128}+\tfrac6{128}+\tfrac2{128}=\tfrac{26}{128}=\tfrac{13}{64}$. A second error is to use a conditional probability given a zero-probability path. The safe calculation is always the joint path-and-observation contribution; when the path probability is zero, that joint contribution is zero by the factorization already proved.

For short sequences, direct enumeration is a transparent way to audit a model and its likelihood. For longer sequences, the $K^T$ path count explains why listing every path becomes impractical. The path-sum formula remains the starting point, but computing that sum without separately enumerating every path requires a different organization of the calculation.

Check Your Understanding

Use the path contribution formula and distinguish the number of paths from the probability assigned to any one path.

For $K=4$ hidden states and sequence length $T=3$, how many hidden paths occur in the direct sum?
Why must the joint-probability factorization be stated separately for a zero-probability hidden path?
In the first worked example, which paths attain the largest individual contribution, and what is the full likelihood?
For a model with one hidden state, how many hidden paths are there for an observation sequence of length $T$?
Explain why the most probable hidden path’s contribution is generally not the observation-sequence likelihood.