Deriving the Backward Algorithm

Why Work Backward?

In a hidden Markov model, the likelihood of an observation sequence can be computed by summing over all possible hidden-state paths. Forward messages organize that sum from the beginning of the sequence. Backward messages organize it from the end: for each possible current hidden state, they record the likelihood of all observations still to come. This reverses the direction of the calculation, not the direction of the hidden chain.

Backward messages are useful on their own for evaluating a sequence likelihood, and they provide the other half of the forward-backward computation. The key step is conditioning on the next hidden state. Once that state is specified, the transition probability, the next observation's emission likelihood, and the likelihood of the observations after it multiply together.

Model and Backward Messages

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $(X_t)_{t=1,\ldots,T}$ be a hidden Markov chain on a finite state space $S=\{1,\ldots,K\}$, with initial distribution $\pi$ as a row vector and transition matrix $P=(p_{ij})$, where $p_{ij}=\mathbb{P}(X_{t+1}=j\mid X_t=i)$. Thus each row of $P$ sums to $1$. Let $Y_1,\ldots,Y_T$ be observations. Conditional on the hidden states, the observations are independent, and the emission likelihood at time $t$ in state $j$ is $b_t(j)=\mathbb{P}(Y_t=y_t\mid X_t=j)$. The emission law may depend on time; the calculations below use the likelihood of the observed value $y_t$.

Let $\mathcal{F}_t=\sigma(X_1,\ldots,X_t,Y_1,\ldots,Y_t)$. For a fixed observed sequence $y_{1:T}=(y_1,\ldots,y_T)$, define $\beta_t(i)$ to be the likelihood of the observations after time $t$, when the hidden state at time $t$ is $i$. Equivalently, it is the probability of $Y_{t+1}=y_{t+1},\ldots,Y_T=y_T$ in the model initialized at state $i$ at time $t$. This model-based definition also covers a state that has zero probability under the original initial distribution.

Definition (Backward messages): The terminal message is $\beta_T(i)=1$ for every $i\in S$, because there are no observations after time $T$. For $t=T-1,\ldots,1$, the backward recursion is $$ \beta_t(i)=\sum_{j\in S}p_{ij}\,b_{t+1}(j)\,\beta_{t+1}(j). $$ Each $\beta_t(i)$ is a likelihood for observations strictly after time $t$; it does not include the emission at time $t$.

The indexing matters. Starting from state $i$ at time $t$, the next transition is to $j$, the observation at time $t+1$ contributes $b_{t+1}(j)$, and the remaining observations contribute $\beta_{t+1}(j)$. The transition matrix acts on the next-state values through the sum over $j$.

Theorem (Backward recursion and likelihood): Under the finite-state hidden Markov model just specified, the backward messages satisfy the terminal and recursive equations above. The likelihood of the full observation sequence is $$ \mathbb{P}(Y_1=y_1,\ldots,Y_T=y_T)=\sum_{i\in S}\pi_i b_1(i)\beta_1(i). $$ This formula remains valid when the likelihood is zero.

Proof. At time $T$, the event consisting of observations strictly after $T$ is the whole sample space, so its probability is $1$, giving $\beta_T(i)=1$. Fix $t<T$ and a starting state $i$ at time $t$. Partition the possible future paths according to the next state $X_{t+1}=j$. The probability of that transition is $p_{ij}$. Given $X_{t+1}=j$, the probability of the next observation is $b_{t+1}(j)$; given that state and observation, the remaining observation likelihood is $\beta_{t+1}(j)$. The Markov property and conditional independence of emissions make the product of these three factors the contribution from state $j$. Summing the disjoint contributions over all $j\in S$ gives the recursion. For the full sequence, partition by $X_1=i$. The initial state has probability $\pi_i$, its first emission contributes $b_1(i)$, and the remaining likelihood is $\beta_1(i)$. Summing these disjoint contributions gives the stated likelihood formula. No division by the sequence likelihood was used, so the identity also holds when that likelihood is zero. $\square$

Worked Calculations

Worked Example: Recursing from the Terminal Time

Consider states $S=\{1,2\}$, three observations, and $$ P=\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac13&\tfrac23\end{bmatrix}. $$ The first row sums to $\tfrac34+\tfrac14=1$, and the second sums to $\tfrac13+\tfrac23=1$. Suppose the observed emission likelihoods at times $2$ and $3$ are $b_2=(\tfrac12,\tfrac14)$ and $b_3=(\tfrac13,\tfrac23)$, with coordinates indexed by states $1,2$. Each listed value is a probability, and the complementary outcome probabilities are respectively $(\tfrac12,\tfrac34)$ and $(\tfrac23,\tfrac13)$.

At the terminal time, $\beta_3(1)=\beta_3(2)=1$. At time $2$, the recursion uses the time-$3$ emission likelihoods:

\begin{aligned} \beta_2(1)&=\tfrac34\cdot\tfrac13\cdot1+\tfrac14\cdot\tfrac23\cdot1 =\tfrac14+\tfrac16=\tfrac5{12},\\ \beta_2(2)&=\tfrac13\cdot\tfrac13\cdot1+\tfrac23\cdot\tfrac23\cdot1 =\tfrac19+\tfrac49=\tfrac59. \end{aligned}

At time $1$, use the time-$2$ emissions and the messages just computed: $$ \begin{aligned} \beta_1(1) &=\tfrac34\cdot\tfrac12\cdot\tfrac5{12} +\tfrac14\cdot\tfrac14\cdot\tfrac59 =\tfrac{15}{96}+\tfrac5{144} =\tfrac{55}{288},\\ \beta_1(2) &=\tfrac13\cdot\tfrac12\cdot\tfrac5{12} +\tfrac23\cdot\tfrac14\cdot\tfrac59 =\tfrac5{72}+\tfrac5{54} =\tfrac{35}{216}. \end{aligned} $$ For the first sum, the common denominator $288$ gives $45/288+10/288=55/288$. For the second, denominator $216$ gives $15/216+20/216=35/216$.

Check: Substituting $\beta_2=(\tfrac5{12},\tfrac59)$ into the time-$1$ recursion gives $\beta_1(1)=\tfrac{55}{288}$ and $\beta_1(2)=\tfrac{35}{216}$, exactly the displayed values. The terminal values are $1$, not the emission likelihoods at time $3$, because $\beta_3$ excludes the emission at time $3$.

Worked Example: Checking the Likelihood Against Forward Weights

Use the transition matrix from the previous example, whose rows sum to $1$. Let the initial distribution be $\pi=(\tfrac12,\tfrac12)$. Use time-specific binary emission distributions: at time $1$, the observed outcome $y_1$ has probabilities $(\tfrac12,\tfrac12)$; at time $2$, $y_2$ has probabilities $(\tfrac{11}{26},\tfrac{21}{44})$; and at time $3$, $y_3$ has probabilities $(\tfrac12,\tfrac14)$. Each probability is in $[0,1]$, with complementary probabilities $ (\tfrac12,\tfrac12)$, $(\tfrac{15}{26},\tfrac{23}{44})$, and $(\tfrac12,\tfrac34)$, respectively.

The forward weights after the first observation are $\alpha_1=(\tfrac12\cdot\tfrac12,\tfrac12\cdot\tfrac12)=(\tfrac14,\tfrac14)$. Before the time-$2$ emissions, transition gives $$ (\tfrac14,\tfrac14)P =\left(\tfrac14\cdot\tfrac34+\tfrac14\cdot\tfrac13,\ \tfrac14\cdot\tfrac14+\tfrac14\cdot\tfrac23\right) =(\tfrac{13}{48},\tfrac{11}{48}). $$

Multiplying coordinatewise by the time-$2$ emission likelihoods gives $$ \alpha_2=\left(\tfrac{13}{48}\cdot\tfrac{11}{26},\ \tfrac{11}{48}\cdot\tfrac{21}{44}\right) =(\tfrac{11}{96},\tfrac7{64}). $$ For the final backward step, $\beta_3=(1,1)$, and hence $$ \beta_2(1)=\tfrac34\cdot\tfrac12+\tfrac14\cdot\tfrac14=\tfrac7{16}, \qquad \beta_2(2)=\tfrac13\cdot\tfrac12+\tfrac23\cdot\tfrac14=\tfrac13. $$ The likelihood from the forward weights and backward messages is therefore $$ \alpha_2(1)\beta_2(1)+\alpha_2(2)\beta_2(2) =\tfrac{11}{96}\cdot\tfrac7{16}+\tfrac7{64}\cdot\tfrac13 =\tfrac{77}{1536}+\tfrac{56}{1536} =\tfrac{133}{1536}. $$

Check by advancing the forward weights through the last transition. Before the time-$3$ emission the weights are $$ \begin{aligned} (\tfrac{11}{96},\tfrac7{64})P &=\left(\tfrac{11}{96}\cdot\tfrac34+\tfrac7{64}\cdot\tfrac13,\ \tfrac{11}{96}\cdot\tfrac14+\tfrac7{64}\cdot\tfrac23\right)\\ &=\left(\tfrac{11}{128}+\tfrac7{192},\ \tfrac{11}{384}+\tfrac{28}{384}\right) =(\tfrac{47}{384},\tfrac{39}{384}). \end{aligned} $$ Multiplying by the time-$3$ emissions gives total likelihood $$ \tfrac{47}{384}\cdot\tfrac12+\tfrac{39}{384}\cdot\tfrac14 =\tfrac{47}{768}+\tfrac{39}{1536} =\tfrac{94}{1536}+\tfrac{39}{1536} =\tfrac{133}{1536}. $$ The two computations agree.

Worked Example: A Two-Observation Likelihood

Let $S=\{1,2\}$, $\pi=(\tfrac13,\tfrac23)$, and $$ P=\begin{bmatrix}\tfrac12&\tfrac12\\[2pt]\tfrac14&\tfrac34\end{bmatrix}. $$ The row sums are $\tfrac12+\tfrac12=1$ and $\tfrac14+\tfrac34=1$. Suppose $b_1=(\tfrac12,\tfrac14)$ and $b_2=(\tfrac13,\tfrac23)$; the complementary emission probabilities are $(\tfrac12,\tfrac34)$ and $(\tfrac23,\tfrac13)$.

Because $T=2$, $\beta_2=(1,1)$. The one backward step gives $$ \beta_1(1)=\tfrac12\cdot\tfrac13+\tfrac12\cdot\tfrac23=\tfrac12, \qquad \beta_1(2)=\tfrac14\cdot\tfrac13+\tfrac34\cdot\tfrac23 =\tfrac1{12}+\tfrac12=\tfrac7{12}. $$ The likelihood is $$ \sum_i\pi_i b_1(i)\beta_1(i) =\tfrac13\cdot\tfrac12\cdot\tfrac12 +\tfrac23\cdot\tfrac14\cdot\tfrac7{12} =\tfrac1{12}+\tfrac7{72} =\tfrac{13}{72}. $$

Check by the forward calculation: $\alpha_1=(\tfrac16,\tfrac16)$. Transitioning gives $(\tfrac18,\tfrac5{24})$, since the first coordinate is $\tfrac16\cdot\tfrac12+\tfrac16\cdot\tfrac14=\tfrac18$, and the second is $\tfrac16\cdot\tfrac12+\tfrac16\cdot\tfrac34=\tfrac5{24}$. After the time-$2$ emissions, $\alpha_2=(\tfrac1{24},\tfrac5{36})$, whose entries sum to $\tfrac3{72}+\tfrac{10}{72}=\tfrac{13}{72}$, as required.

How Forward and Backward Messages Fit Together

Define the forward message $\alpha_t(i)$ as the joint likelihood of the observations through time $t$ and the event $X_t=i$: $\alpha_t(i)=\mathbb{P}(Y_1=y_1,\ldots,Y_t=y_t,X_t=i)$. Its initialization and update are $\alpha_1(i)=\pi_i b_1(i)$ and $\alpha_{t+1}(j)=b_{t+1}(j)\sum_i\alpha_t(i)p_{ij}$. The forward recursion sums histories that arrive at $j$; the backward recursion sums futures that depart from $i$.

Identity (Forward-backward likelihood check): For every $t\in\{1,\ldots,T\}$, $$ \mathbb{P}(Y_1=y_1,\ldots,Y_T=y_T)=\sum_{i\in S}\alpha_t(i)\beta_t(i). $$

Proof. Partition the event of observing the full sequence according to the state $X_t=i$. For each $i$, the joint likelihood of the observations through $t$ and $X_t=i$ is $\alpha_t(i)$. Given $X_t=i$, the Markov property and conditional independence of emissions make the likelihood of the remaining observations equal to $\beta_t(i)$. Thus the contribution from paths with $X_t=i$ is $\alpha_t(i)\beta_t(i)$. The events $X_t=i$ are disjoint and exhaust all possibilities, so summing over $i$ gives the identity. This is a likelihood factorization; it does not require dividing by the sequence likelihood. $\square$

This identity is valuable as a computational check: a forward calculation and a backward calculation, joined at any time $t$, must give the same scalar likelihood. It does not itself give the conditional distribution of a hidden state given all observations; that requires an additional normalization and is a separate inference calculation.

Common Errors and Practical Checks

A frequent error is to use $p_{ji}$ rather than $p_{ij}$ in the backward update. The current state is the row index $i$, and the possible next state is the column index $j$. Another error is to include the time-$t$ emission in $\beta_t(i)$. By definition, that emission is already part of the observations through time $t$; the backward message begins at $t+1$. The terminal value is consequently $1$, not $b_T(i)$.

Common mistake, shown numerically. In the two-state model of the first example, the correct value is $\beta_2(1)=\tfrac34\cdot\tfrac13+\tfrac14\cdot\tfrac23=\tfrac5{12}$. Using the transposed transition entries incorrectly gives $\tfrac13\cdot\tfrac13+\tfrac23\cdot\tfrac23=\tfrac59$, which is actually $\beta_2(2)$, not $\beta_2(1)$. The correction is to fix the current state as the row and sum across its row: from state $1$, the transition probabilities are $\tfrac34$ to state $1$ and $\tfrac14$ to state $2$.

For a reliable computation, first check that every transition row sums to $1$, then write the terminal vector of ones, and at each backward step use the emission likelihood at the next time. Finally, compare the sequence likelihood with a forward calculation or with $\sum_i\alpha_t(i)\beta_t(i)$ at a chosen time. These checks catch most indexing and orientation mistakes before they propagate.

Check Your Understanding

Use the definitions and recursions above to answer each question. When calculating a likelihood, show the terms before combining them.

Why is $\beta_T(i)=1$ rather than $b_T(i)$ under the stated definition?
For a two-state chain with $P=\begin{bmatrix}\tfrac12&\tfrac12\\ \tfrac14&\tfrac34\end{bmatrix}$ and final emission likelihoods $(\tfrac13,\tfrac23)$, calculate $\beta_{T-1}(1)$. Verify the transition row sums first.
Explain why the recursion for $\beta_t(i)$ uses $b_{t+1}(j)$, not $b_t(i)$.
If $\alpha_t=(\tfrac16,\tfrac16)$ and $\beta_t=(\tfrac12,\tfrac7{12})$, calculate $\sum_i\alpha_t(i)\beta_t(i)$ exactly.
Describe the indexing error in replacing $p_{ij}$ by $p_{ji}$ in the backward recursion.