Filtering as an Online Update
In a hidden Markov model, the state is not observed directly. Instead, each observation supplies evidence about the current state, while the transition matrix describes how the state changes over time. Filtering combines these two pieces of information in sequence: first update the probabilities of the state just observed, then propagate those probabilities to predict the next state. This makes it possible to process a growing data stream without recomputing the full distribution over every hidden-state path.
Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \((X_n)_{n\ge0}\) be a hidden Markov chain with finite state space \(S=\{1,\ldots,K\}\), initial distribution \(\mu\) as a row vector, and transition matrix \(P=(p_{ij})\). Thus \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\), and every row of \(P\) sums to one. Let \(Y_n\) be the observation at time \(n\), taking values in a discrete observation space. Given the hidden states, observations are conditionally independent, and the distribution of \(Y_n\) depends only on \(X_n\). Write \(b_j(y)=\mathbb{P}(Y_n=y\mid X_n=j)\) for the emission probability.
For a realized observation sequence \(y_0,\ldots,y_n\), let \(\mathcal{G}_n=\sigma(Y_0,\ldots,Y_n)\) be the observation information through time \(n\). When the conditioning event has positive probability, define the filtering distribution \(f_n\) by \(f_n(j)=\mathbb{P}(X_n=j\mid Y_0=y_0,\ldots,Y_n=y_n)\). It is a row vector. The predictive distribution for \(X_n\) before observing \(Y_n\) is denoted \(q_n\); for \(n\ge1\), it is obtained from \(f_{n-1}\) and \(P\).
The order of these operations matters. The transition step \(f_{n-1}P\) predicts the state at time \(n\) using information only through time \(n-1\). The observation \(y_n\) then reweights that prediction. Once that update is complete, multiplying \(f_nP\) predicts the state at time \(n+1\).
Proof. Assume first that \(n\ge1\), and that the preceding observations have positive probability, so \(f_{n-1}\) is defined. By the Markov property and the definition of \(f_{n-1}\), the conditional probability of \(X_n=j\) given the observations through time \(n-1\) is \(\sum_i f_{n-1}(i)p_{ij}=q_n(j)\). Given \(X_n=j\), the emission model gives probability \(b_j(y_n)\) to the observation \(y_n\), independently of earlier observations conditional on the states. Therefore the joint conditional probability of \(X_n=j\) and \(Y_n=y_n\), given the earlier observations, is \(q_n(j)b_j(y_n)\). Summing this expression over the finite state space gives the conditional probability of \(Y_n=y_n\), namely \(c_n\). If \(c_n>0\), Bayes’ rule gives \(f_n(j)=q_n(j)b_j(y_n)/c_n\). The same Bayes calculation at time \(0\) uses the prior \(\mu(j)\) in place of \(q_n(j)\). Finally, conditional on observations through \(n\), the state distribution at \(n\) is \(f_n\); applying the Markov transition probabilities gives \(\mathbb{P}(X_{n+1}=j\mid Y_0=y_0,\ldots,Y_n=y_n)=\sum_i f_n(i)p_{ij}\), which is the \(j\)th component of \(f_nP\). \(\square\)
The normalization is essential: the observation update turns the unnormalized weights \(q_n(j)b_j(y_n)\) into probabilities. Prediction needs no additional normalization, because a probability row vector multiplied by a row-stochastic matrix remains a probability row vector. Indeed, its entries are nonnegative, and \(\sum_j\sum_i f_n(i)p_{ij}=\sum_i f_n(i)\sum_jp_{ij}=\sum_i f_n(i)=1\).
Worked Filtering Calculations
Worked Example: Update, Then Predict
Consider two states, \(S=\{1,2\}\), with initial distribution \(\mu=(\tfrac12,\tfrac12)\) and transition matrix \(P=\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac13&\tfrac23\end{bmatrix}\). The first row sums to \(\tfrac34+\tfrac14=1\); the second sums to \(\tfrac13+\tfrac23=1\). The observation \(Y_0\) is binary, and the probability of observing \(a\) is \(b_1(a)=\tfrac34\) in state 1 and \(b_2(a)=\tfrac18\) in state 2. Given \(Y_0=a\), find the filtered distribution of \(X_0\), then predict \(X_1\).
The unnormalized weights for \(X_0\) are \(\mu(1)b_1(a)=\tfrac12\cdot\tfrac34=\tfrac38\) and \(\mu(2)b_2(a)=\tfrac12\cdot\tfrac18=\tfrac1{16}\). Their sum, the probability of \(Y_0=a\), is \(\tfrac38+\tfrac1{16}=\tfrac6{16}+\tfrac1{16}=\tfrac7{16}\). Thus \(f_0(1)=(\tfrac38)/(\tfrac7{16})=\tfrac67\) and \(f_0(2)=(\tfrac1{16})/(\tfrac7{16})=\tfrac17\). These entries sum to \(\tfrac67+\tfrac17=1\).
To predict \(X_1\), multiply this row vector by \(P\). The probability of state 1 is \((f_0P)(1)=\tfrac67\cdot\tfrac34+\tfrac17\cdot\tfrac13=\tfrac{18}{28}+\tfrac1{21}=\tfrac9{14}+\tfrac1{21}=\tfrac{27}{42}+\tfrac2{42}=\tfrac{29}{42}\). The probability of state 2 is \((f_0P)(2)=\tfrac67\cdot\tfrac14+\tfrac17\cdot\tfrac23=\tfrac3{14}+\tfrac2{21}=\tfrac9{42}+\tfrac4{42}=\tfrac{13}{42}\). Check: \(\tfrac{29}{42}+\tfrac{13}{42}=\tfrac{42}{42}=1\), and the first component agrees with its direct transition contributions from both states.
Worked Example: Two Observations in Sequence
Let \(S=\{1,2\}\), \(\mu=(\tfrac12,\tfrac12)\), and \(P=\begin{bmatrix}\tfrac23&\tfrac13\\[2pt]\tfrac14&\tfrac34\end{bmatrix}\). The row sums are \(\tfrac23+\tfrac13=1\) and \(\tfrac14+\tfrac34=1\). Suppose observations are \(a\) or \(b\), with \(b_1(a)=\tfrac34\) and \(b_2(a)=\tfrac14\); hence \(b_1(b)=\tfrac14\) and \(b_2(b)=\tfrac34\). For the observed sequence \(Y_0=a,Y_1=b\), compute both filtering distributions and the prediction of \(X_2\).
At time 0, the unnormalized weights for \(a\) are \(\tfrac12\cdot\tfrac34=\tfrac38\) and \(\tfrac12\cdot\tfrac14=\tfrac18\), with sum \(\tfrac12\). Therefore \(f_0=(\tfrac34,\tfrac14)\). Predicting \(X_1\) gives \(q_1(1)=\tfrac34\cdot\tfrac23+\tfrac14\cdot\tfrac14=\tfrac12+\tfrac1{16}=\tfrac9{16}\), and \(q_1(2)=\tfrac34\cdot\tfrac13+\tfrac14\cdot\tfrac34=\tfrac14+\tfrac3{16}=\tfrac7{16}\). The entries sum to \(\tfrac{16}{16}=1\).
Now use the observation \(b\). Its unnormalized weights are \(\tfrac9{16}\cdot\tfrac14=\tfrac9{64}\) and \(\tfrac7{16}\cdot\tfrac34=\tfrac{21}{64}\). Their sum is \(\tfrac{30}{64}=\tfrac{15}{32}>0\), so \(f_1(1)=\tfrac9{30}=\tfrac3{10}\) and \(f_1(2)=\tfrac{21}{30}=\tfrac7{10}\). Finally, \((f_1P)(1)=\tfrac3{10}\cdot\tfrac23+\tfrac7{10}\cdot\tfrac14=\tfrac15+\tfrac7{40}=\tfrac8{40}+\tfrac7{40}=\tfrac38\), and \((f_1P)(2)=\tfrac3{10}\cdot\tfrac13+\tfrac7{10}\cdot\tfrac34=\tfrac1{10}+\tfrac{21}{40}=\tfrac4{40}+\tfrac{21}{40}=\tfrac58\). Check: the final prediction sums to \(\tfrac38+\tfrac58=1\), and the posterior \(f_1\) sums to \(\tfrac3{10}+\tfrac7{10}=1\).
Worked Example: Predicting a State and the Next Observation
Suppose the current filtered distribution on \(S=\{1,2,3\}\) is \(f_n=(\tfrac12,\tfrac13,\tfrac16)\), and \(P=\begin{bmatrix}\tfrac12&\tfrac12&0\\0&\tfrac12&\tfrac12\\\tfrac14&0&\tfrac34\end{bmatrix}\). The row sums are \(\tfrac12+\tfrac12+0=1\), \(0+\tfrac12+\tfrac12=1\), and \(\tfrac14+0+\tfrac34=1\). For a possible next observation \(c\), let the emission probabilities be \(b_1(c)=\tfrac13\), \(b_2(c)=\tfrac23\), \(b_3(c)=\tfrac14\). Find the prediction of \(X_{n+1}\), the probability of observing \(c\) next, and the filtered distribution after \(c\).
First propagate the current distribution. The three components of \(q_{n+1}=f_nP\) are \(q_{n+1}(1)=\tfrac12\cdot\tfrac12+\tfrac13\cdot0+\tfrac16\cdot\tfrac14=\tfrac14+\tfrac1{24}=\tfrac7{24}\), \(q_{n+1}(2)=\tfrac12\cdot\tfrac12+\tfrac13\cdot\tfrac12+\tfrac16\cdot0=\tfrac14+\tfrac16=\tfrac{10}{24}=\tfrac5{12}\), and \(q_{n+1}(3)=\tfrac12\cdot0+\tfrac13\cdot\tfrac12+\tfrac16\cdot\tfrac34=\tfrac16+\tfrac18=\tfrac7{24}\). Their sum is \(\tfrac7{24}+\tfrac{10}{24}+\tfrac7{24}=1\).
The probability of the next observation being \(c\) is the sum of its state-specific contributions: \(c_{n+1}=\tfrac7{24}\cdot\tfrac13+\tfrac5{12}\cdot\tfrac23+\tfrac7{24}\cdot\tfrac14=\tfrac7{72}+\tfrac{20}{72}+\tfrac7{96}=\tfrac{28}{288}+\tfrac{80}{288}+\tfrac{21}{288}=\tfrac{129}{288}=\tfrac{43}{96}\). The unnormalized posterior weights, on the common denominator \(288\), are \(28/288,80/288,21/288\). Dividing by their sum gives \(f_{n+1}=(\tfrac{28}{129},\tfrac{80}{129},\tfrac{21}{129})\). Check: the entries sum to \(\tfrac{28+80+21}{129}=1\), and multiplying each posterior entry by \(\tfrac{43}{96}=\tfrac{129}{288}\) recovers its corresponding unnormalized weight.
Why the Two Distributions Are Different
The filtered distribution \(f_n\) answers a question about the current hidden state after using the observation at time \(n\). The predictive distribution \(f_nP\) answers a different question: what probabilities should be assigned to the next hidden state before observing \(Y_{n+1}\)? The next observation will change that prediction by the Bayes update. In applications, the predictive distribution can be used to anticipate state occupancy, while the filtering distribution summarizes current state uncertainty using all data observed so far.
Filtering is an online calculation because each step needs only the preceding filtering vector, the transition matrix, and the new observation’s emission probabilities. It does not require storing every possible hidden path. This distinction is useful whenever data arrive sequentially, including monitoring systems and longitudinal measurements. The recursion presumes that the transition and emission probabilities are specified and that the realized observation has positive conditional probability. If the normalizing constant \(c_n\) is zero, the observed history has probability zero under the model, and the conditional distribution is not defined by this Bayes formula.
Common pitfall: using a row-stochastic matrix as though it acted on column distributions. With \(f=(\tfrac67,\tfrac17)\) and the matrix in the first example, the correct prediction is the row-vector product \(fP=(\tfrac{29}{42},\tfrac{13}{42})\). A mistaken column-vector calculation \(Pf^\mathsf{T}\) gives first component \(\tfrac34\cdot\tfrac67+\tfrac14\cdot\tfrac17=\tfrac{19}{28}\) and second component \(\tfrac13\cdot\tfrac67+\tfrac23\cdot\tfrac17=\tfrac8{21}\). These sum to \(\tfrac{57}{84}+\tfrac{32}{84}=\tfrac{89}{84}\ne1\), so they cannot be a probability distribution. The correction is to keep distributions as row vectors and compute \((fP)(j)=\sum_i f(i)p_{ij}\).
Check Your Understanding
For each question, keep the distinction between the pre-observation prediction and the post-observation filtering distribution explicit.
- Given a filtering row vector \(f_n\), write the component formula for the predicted probability of state \(j\) at time \(n+1\).
- Why must the normalizing constant for an observation update be positive for the posterior formula to apply?
- If \(q=(\tfrac23,\tfrac13)\), and the likelihoods of an observed symbol are \((\tfrac12,\tfrac14)\), compute the evidence and the updated posterior.
- Explain why multiplying a probability row vector by a row-stochastic transition matrix preserves the sum of its entries.
- In what order do the transition step and observation update occur when processing \(Y_n\) after data through time \(n-1\)?