Markov Models and Hidden Markov Models

A changing system needs a state for each moment and a rule for moving to the next moment. A discrete-time Markov chain records these states at evenly spaced steps. Choose the state and time step together: daily weather and a robot's location every second describe different processes.

What the current state must contain

The first-order Markov property is

Once the current state is known, earlier states add no information about the next one. This is conditional independence, not independence between consecutive states. Knowing yesterday's weather can help predict tomorrow's when today's weather is unknown.

A chain needs an initial distribution, $P(X_1)$, and a transition model. We use time-homogeneous transitions: the same probabilities apply at every step. Some AI texts call this a stationarity assumption. In probability theory, a stationary process has joint distributions unchanged by shifting time; fixed transitions alone do not ensure that. Starting a time-homogeneous chain in a stationary distribution does.

Read a transition matrix

For weather, let the states be Sunny (S) and Cloudy (C). Rows name the current state and columns the next state:

From Sunny, the next day is sunny with probability 0.8 and cloudy with probability 0.2. From Cloudy, those probabilities are 0.4 and 0.6. Every row sums to 1 because it lists every destination from one starting state. Columns need not sum to 1. A state diagram represents the same table with arrows, including arrows back to the same state.

Some books transpose this convention. Before calculating, read the definition of an entry: here $T_{ij}=P(X_{t+1}=j\mid X_t=i)$. A correct set of numbers used in the wrong orientation gives the wrong prediction.

Multiply along a path

A particular path uses its initial probability and one transition for each move:

If day 1 is certainly sunny, the path Sunny, Sunny, Cloudy, Cloudy has probability

The first move contributes 0.8, the switch contributes 0.2, and staying cloudy contributes 0.6. Multiplying separate daily frequencies would discard the links between days. In a Bayesian network, those links are the arrows in $X_1\to X_2\to X_3\to \cdots$.

Keep enough history in the state

A second-order model depends on the last two values. Turn it into a first-order model by defining the state as (yesterday, today). Two weather values then give four possible pairs. A transition from (Sunny, Cloudy) can lead only to a pair beginning with Cloudy, because adjacent pairs must overlap. For a process of order $k$, store the last $k$ values together; the algorithms stay first-order, while the number of combined states grows.

A chain occupies one state at each time, but you may not know which one. A state distribution stores that uncertainty as a row vector. Its entries give the probabilities of the possible states, not fractions of time within a single step.

Add every route into a destination

To predict Sunny tomorrow, consider both ways to get there: today may be Sunny or Cloudy. Weight each transition by the probability of its starting state:

For the complete vector, this is $p_{t+1}=p_{t}T$. After $k$ moves, $p_{t+k}=p_t{T}^k$. This update is sometimes called the mini-forward algorithm, the evidence-free version of HMM filtering.

Work through the weather chain

Use rows (0.8, 0.2) from Sunny and (0.4, 0.6) from Cloudy. Start with a certainly sunny day: $p_1=(1,0)$. One move gives $p_2=(0.8,0.2)$. For day 3, the sunny contribution is $0.8\times 0.8=0.64$ from Sunny and $0.2\times 0.4=0.08$ from Cloudy. Add them to get 0.72. The cloudy contributions are $0.8\times 0.2=0.16$ and $0.2\times 0.6=0.12$, giving 0.28.

Thus $p_3=(0.72,0.28)$. One further update gives $P(X_4=S)=0.72\times 0.8+0.28\times 0.4=0.688$ and $P(X_4=C)=0.312$. Carry unrounded values between steps and round displayed results at the end.

Check the meaning and orientation

Each result must be nonnegative and sum to 1. Under the row convention, put the distribution on the left. Using $T{p}_1^{𝖳}$ instead gives the column (0.8, 0.4), whose total is 1.2. That calculation selects the probabilities of reaching Sunny from two different starts; it does not distribute one starting belief among destinations.

The value 0.72 on day 3 means about 72% of many independent runs with a sunny day 1 will be sunny on day 3. It describes neither a fixed repeating weather pattern nor a day that is 72% sunny.

Why prediction stays manageable

A dense update over $S$ states costs $O(S^2)$ operations. It summarizes all past paths in the current vector, so the cost per move stays the same as time grows. Listing every path from a known start would instead require $S^{t-1}$ paths at time $t$.

For this weather chain, successive sunny probabilities approach $2\mathrm{/}3$. If $s_t=P(X_t=S)$, then $s_{t+1}=0.4+0.4s_t$. Subtracting $2\mathrm{/}3$ shows that the gap shrinks by a factor of 0.4 each step. Other chains can behave differently; convergence needs the conditions studied with stationary distributions.

You can also simulate a run. Draw the initial state, then draw from the transition row for the state currently occupied. From Sunny, a uniform random draw below 0.8 selects Sunny; a draw at least 0.8 selects Cloudy. Repeating many runs estimates the same predicted distribution and introduces the sampling idea used by particle filters.

A distribution can stay unchanged even while individual runs keep moving. A stationary distribution describes this balance. It is useful for long-run forecasts, but its existence alone does not tell you whether a chain approaches it from a particular start.

Solve the balance equations

A stationary row vector satisfies $\pi =\pi T$ together with ${\sum }_j{\pi }_j=1$ and nonnegative entries. For the weather chain, probability flowing from Sunny to Cloudy must balance probability flowing back:

The first equation gives ${\pi }_S=2{\pi }_C$. Substitution gives $3{\pi }_C=1$, so $\pi =(2\mathrm{/}3,1\mathrm{/}3)$. For a two-state chain with switching probabilities $a$ from state 1 to 2 and $b$ from 2 to 1, ${\pi }_1=b\mathrm{/}(a+b)$ when $a+b>0$.

For more states, write one incoming-flow equation per state. Replace one with the sum-to-1 equation and solve the linear system. The balance equations alone leave the scale undetermined. Finally multiply the proposed vector by the matrix to check it.

For bike-share stations A, B, C, take rows (0.6, 0.2, 0.2), (0.1, 0.8, 0.1), and (0.2, 0.2, 0.6). The solution is (0.25, 0.5, 0.25). For example, incoming probability at B is $0.25(0.2)+0.5(0.8)+0.25(0.2)=0.5$. Uniform probability would fail this check.

Separate three questions

Irreducible means every state can reach every other state, possibly through several moves. Aperiodic means returns are not locked into a fixed cycle longer than one step. The weather matrix has all entries positive, so both conditions hold. In a finite irreducible chain, stationary probabilities also give the long-run fractions of steps spent in each state, even when periodicity prevents convergence of the time-specific distribution.

Two revealing counterexamples

If two states always swap, the distribution from a certain first state alternates between (1, 0) and (0, 1). The unique stationary vector is (0.5, 0.5), but these predictions never approach it. Along a long run, each state still occupies half the steps.

If both states are absorbing, each stays where it is forever. Every vector (q, 1 − q) is stationary, so there is no unique equilibrium shared by all starts. These examples show why uniqueness, convergence, and time averages need separate checks.

The initial distribution describes the start; it equals a stationary distribution only when you start in equilibrium. Fixed transition probabilities describe the model's law, not its current distribution. PageRank uses stationary probabilities to rank pages in a random-surfer model. Markov chain Monte Carlo constructs a chain with a desired stationary distribution so its long run can supply samples.

A sensor reading gives evidence about a state without revealing it perfectly. In a hidden Markov model, or HMM, the state changes over time and each state produces an observation. A robot may know what its range sensor reported while remaining uncertain about its position.

Specify three probability models

An HMM needs an initial state distribution, a transition model, and a sensor model:

The hidden state is a discrete variable. The sensor model, also called the emission or observation model, tells you the likelihood of each observation in each state. We put a prior directly on $X_1$ and observe $E_1$ there. Texts that start with an unobserved $X_0$ perform a transition before the first observation instead.

The state has the first-order Markov property. The observation at a time depends only on that time's state: $P(E_t\mid X_{1:t},E_{1:t-1})=P(E_t\mid X_t)$. In a Bayesian network, draw a hidden-state chain and add an arrow from each state to its observation.

Build the solar-panel model

The hidden weather is Sunny or Cloudy, with transition rows (0.8, 0.2) and (0.4, 0.6). Both initial states have probability 0.5. Daily panel output is High or Low:

Each sensor row sums to 1. A cloudy day can still produce High output, so High does not identify Sunny with certainty. Likewise, $P(L\mid C)=0.7$ is a statement about output on cloudy days. Finding $P(C\mid L)$ also needs the prior and Bayes' rule.

Score states and evidence together

For a particular state path and observation sequence,

For Cloudy, Cloudy, Sunny with Low, Low, High, start at $0.5\times 0.7=0.35$. Staying cloudy and observing Low gives $0.35\times 0.6\times 0.7=0.147$. Switching to Sunny and observing High gives $0.147\times 0.4\times 0.8=0.04704$.

Observations can be dependent even though they have no direct arrows between them. Persistent cloudy weather makes successive Low readings tend to occur together. Conditioning on the hidden states removes that dependence. Evidence updates the observer's belief; observing Low does not itself make the weather change.

Choose the inference question

The same three models support all five tasks. What changes is which variables you retain, which you sum out, and whether you sum over paths or select the largest path score.

The state definition decides what the model can remember. A useful temporal model keeps the information needed to predict the next state, while keeping inference affordable. Its probabilities must also reflect the data and sensor failures it will encounter.

Choose enough state information

Position alone may be inadequate for an object with momentum: earlier positions reveal its direction. Adding velocity lets the current state explain that direction. Add season if the dynamics depend on it. These choices make the Markov approximation more reasonable; they are choices about what information travels forward.

A continuous quantity can be placed on a grid. Temperatures from 10 °C to 20 °C in 0.1 °C increments give 101 values, including both endpoints. Finer spacing increases the number of states. Combining several gridded quantities multiplies their counts, and dense exact inference costs $O(S^2)$ per step.

Count independent parameters

A categorical row with $r$ entries has $r-1$ free parameters because the last entry is fixed by their sum. With $S$ states and $O$ observation values, an unrestricted HMM therefore needs

free parameters: prior, transitions, and emissions. The two-state, two-output solar model needs $1+2+2=5$. Counting every table entry would count the row-sum constraints as additional choices.

Factor the state with a dynamic Bayesian network

A dynamic Bayesian network (DBN) keeps several state variables and gives each its own parents. It can express local dependencies without constructing a huge flat transition table. Twenty Boolean variables have $2^{20}=\mathrm{1,048,576}$ joint states; a flat transition table has $2^{40}$ entries. If each next-step Boolean variable has three Boolean parents, its table needs eight probabilities, so all 20 need $20\times 8=160$.

A discrete DBN can be flattened into an HMM by treating a complete assignment as one state. Factored storage is compact, but exact inference can still become costly when dependencies couple many variables. Particle methods can sample these assignments directly.

Estimate rows from data

When states are labeled, use conditional counts. Forty sunny successors out of 50 recorded transitions from Sunny give $P(S\to S)=40\mathrm{/}50=0.8$. The denominator counts transitions leaving Sunny, not every day in the record. A state at the end of a record has no observed successor.

Zero counts produce zero maximum-likelihood probabilities. Add-one correction gives each destination one pseudo-count and increases the row total accordingly. This avoids ruling out a transition solely because a small training record missed it. When states are hidden, Baum–Welch alternates smoothed expected counts with parameter re-estimation.

Give failures a place in the sensor model

If every possible state assigns zero likelihood to a reading, an update has zero total and cannot normalize. A small outlier component can give unusual readings some probability. A normalized mixture has the form $P(e\mid x)=0.99P_{\mathrm{r}\mathrm{e}\mathrm{g}\mathrm{u}\mathrm{l}\mathrm{a}\mathrm{r}}(e\mid x)+0.01P_{\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{i}\mathrm{e}\mathrm{r}}(e)$. Both component distributions must be normalized.

The effect of a reading depends on likelihood ratios across states. Equal likelihoods leave the predicted belief unchanged after normalization. A small likelihood under every state can still be informative if the likelihoods differ greatly in relative terms.

Filtering tracks the current hidden state using every observation available so far. Its output is a belief distribution, $f_t(x)=P(X_t=x\mid e_{1:t})$. You update this compact distribution when a new reading arrives, without retaining every possible earlier path.

Predict, weight, normalize

For a later step, first move the belief through the transition model:

Then weight each destination by the likelihood of the new observation and normalize:

The prediction describes where the state may have moved. The evidence update is Bayes' rule at the new time. With a prior on $X_1$, start by weighting that prior with the first observation; there is no move before it.

Day 1: observe Low

Use the solar-panel model: prior (0.5, 0.5), transition rows (0.8, 0.2) and (0.4, 0.6), and Low likelihoods (0.2, 0.7). Weighting gives $0.5(0.2)=0.10$ for Sunny and $0.5(0.7)=0.35$ for Cloudy. The total is 0.45. Divide each weight by it to get $f_1=(2\mathrm{/}9,7\mathrm{/}9)\approx (0.2222,0.7778)$.

Day 2: observe Low again

Prediction gives ${\bar{f}}_2(S)=(2\mathrm{/}9)(0.8)+(7\mathrm{/}9)(0.4)=22\mathrm{/}45\approx 0.4889$. Cloudy has probability $23\mathrm{/}45\approx 0.5111$. The new weights are $22\mathrm{/}225\approx 0.0978$ and $161\mathrm{/}450\approx 0.3578$. Their total is $41\mathrm{/}90\approx 0.4556$, producing $f_2=(44\mathrm{/}205,161\mathrm{/}205)\approx (0.2146,0.7854)$.

The second Low only slightly increases the cloudy belief. Motion toward the chain's sunny-heavy equilibrium competes with the new evidence favoring Cloudy. Applying Low directly to yesterday's belief would miss that movement.

Day 3: observe High

Predict ${\bar{f}}_3=(498\mathrm{/}1025,527\mathrm{/}1025)\approx (0.4859,0.5141)$. High has likelihoods (0.8, 0.3), so the weights are approximately (0.3887, 0.1542). Divide by their total, approximately 0.5429, to obtain $f_3\approx (0.7159,0.2841)$.

High is $0.8\mathrm{/}0.3\approx 2.67$ times as likely under Sunny as under Cloudy. That likelihood ratio shifts the odds toward Sunny. A large likelihood alone is less informative than its size relative to the competing state's likelihood.

Keep an online filter reliable

A dense step costs $O(S^2)$ time and stores $O(S)$ belief entries, independent of the length of the history. This is exact variable elimination: each past state is summed out as you advance.

Normalize at each observation. Without scaling, the vector stores joint state-and-evidence probabilities, which can shrink below floating-point range. Keep the discarded totals separately if you need evidence likelihood. A zero total requires model or particle-support recovery; division cannot repair it.

Our row-vector formula is $f_{t+1}\propto (f_{t}T)O_{t+1}$, where the diagonal matrix contains the new likelihoods. For column beliefs the equivalent is $f_{t+1}\propto O_{t+1}{T}^{𝖳}{f}_t$. Mixing these conventions is a frequent source of errors.

A filtered belief supports two useful questions: what might happen next, and how well did the model explain the readings already seen? Both use the same transition and sensor models, but the answers describe different random quantities.

Predict without future readings

For a forecast $k$ steps ahead, apply the transition matrix $k$ times to the latest filtered belief:

No observation update belongs to an unobserved future step. After the solar model sees Low, Low, High, the day-3 belief is approximately (0.7159, 0.2841). One prediction gives $P(X_4=S)\approx 0.7159(0.8)+0.2841(0.4)=0.6864$. Continuing from unrounded values gives sunny probabilities 0.6745, 0.6698, 0.6679, and 0.6672.

These approach $2\mathrm{/}3$. The chain gradually loses its dependence on the latest belief. Mixing time specifies how many steps are needed to come within a chosen distance of equilibrium from every starting state. A forecast close to equilibrium still retains a small influence from current evidence; it is not an exact reset.

Prediction need not increase uncertainty at every step. From (0.5, 0.5), this weather chain predicts (0.6, 0.4), a more concentrated distribution. Convergence concerns loss of dependence on the starting belief, not a rule that forecasts must become uniform.

Forecast an observation

An output forecast averages the sensor likelihood over predicted states:

For High on day 4, use the day-4 state prediction, not the day-3 filter: $0.6864(0.8)+0.3136(0.3)\approx 0.6432$. The sunny probability and High-output probability differ because both weather states can produce High output.

Retain the totals from filtering

Before each update normalizes, its total is the probability of that observation given earlier ones. Call it $c_t=P(e_t\mid e_{1:t-1})$. The chain rule gives

For Low, Low, High, the totals are approximately 0.45, 0.4556, and 0.5429. Their product, computed before rounding, is 0.1113. This is a sum over every hidden path compatible with the evidence. The best path alone contributes 0.04704, only part of the total.

An unnormalized forward pass gives the same likelihood by summing its final entries. A normalized pass is more stable, provided the totals are kept. In long sequences, store $\log P(e_{1:t})={\sum }_i\log c_i$ instead of multiplying tiny values. Here the natural log is about −2.196.

Compare models on matching evidence

A likelihood measures how well one model accounts for a particular observation sequence. To compare candidate word HMMs on the same recording, score that recording under each model and combine with word priors when finding posterior word probabilities. Longer sequences usually have smaller raw likelihoods, so a smaller number from a longer recording alone does not show a worse model.

A later observation can change what you believe about an earlier state. Smoothing estimates $P(X_k\mid e_{1:t})$ for $k<t$. It is useful when reconstructing a recorded trajectory or when an application can wait briefly before reporting a past estimate.

Divide the evidence at the target time

Filtering has already summarized evidence up to time $k$ as $f_k(x)=P(X_k=x\mid e_{1:k})$. A backward message summarizes the remaining observations as a likelihood, $b_k(x)=P(e_{k+1:t}\mid X_k=x)$. Combine them state by state:

Normalize the products across states. The later evidence is weighted according to how plausible it would be from each candidate state at time $k$.

Pass the future likelihood backward

At the last time, there are no later observations, so $b_t(x)=1$ for every state. Moving back one step gives

For each possible successor, multiply the chance of moving there, the likelihood of its observation, and the remaining future likelihood. Then add over successors. A backward message is a likelihood function over possible starting states, not a state distribution; its entries need not add to 1.

Smooth day 2 in the solar example

The observations are Low, Low, High. After the two Low readings, the filtered day-2 belief is approximately (0.2146, 0.7854). For the final High reading, the backward likelihood from a sunny day 2 is $0.8(0.8)+0.2(0.3)=0.70$. From a cloudy day 2 it is $0.4(0.8)+0.6(0.3)=0.50$.

Multiply: the products are approximately $0.2146(0.70)=0.1502$ and $0.7854(0.50)=0.3927$. Normalize their unrounded values to obtain a day-2 sunny probability of 0.2767. High on day 3 makes a sunny day 2 more plausible than the original filtered probability 0.2146 did.

Continue to day 1

The backward likelihood from Sunny on day 1 is $0.8(0.2)(0.70)+0.2(0.7)(0.50)=0.182$. From Cloudy it is $0.4(0.2)(0.70)+0.6(0.7)(0.50)=0.266$. Combine with $f_1=(2\mathrm{/}9,7\mathrm{/}9)$ and normalize. The smoothed sunny probability is approximately 0.1635, down from 0.2222: the full future includes another Low as well as the final High.

Later evidence need not move every past estimate in the same direction. At the final time, smoothing equals filtering because no later evidence exists.

Organize the computation

The forward–backward algorithm first stores all forward beliefs, then computes backward messages and normalized products. For $t$ steps and $S$ states, dense computation costs $O(S^{2}t)$ and stores $O(St)$ values. Fixed-lag smoothing reports the state a fixed number of steps behind the present, trading delay for more evidence.

Reversing the list of observations and running an ordinary filter is a different calculation. The backward recursion uses the original forward transitions and future likelihoods; it does not introduce a new initial prior at the recording's end. Smoothed state probabilities also supply expected counts for Baum–Welch learning.

Sometimes the desired answer is one complete explanation of the observations. Viterbi decoding finds the most likely hidden-state sequence. It accounts for transitions between states, which separate most-likely choices at individual times can ignore.

Change the objective

The target is $\arg {\max }_{x_{1:t}}P(x_{1:t}\mid e_{1:t})$. Every candidate has the same evidence denominator, so maximizing the joint score $P(x_{1:t},e_{1:t})$ selects the same path. This score differs from a final-state posterior, which adds every path ending in that state.

With solar observations High, Low, the most likely individual states after smoothing are Sunny on day 1 and Cloudy on day 2. Yet Sunny, Sunny is the most likely complete path: its posterior is about 0.3282, compared with 0.2872 for Sunny, Cloudy. With forbidden transitions, individually plausible states can even make an impossible path.

Keep the best prefix for each ending state

Let $m_t(j)$ be the best joint path-and-evidence score ending in state $j$. Initialize $m_1(j)=P(X_1=j)P(e_1\mid j)$. Then use

Save the maximizing predecessor as a backpointer. Paths ending in the same state have the same possible future continuations, so a lower-scoring prefix can be discarded. The forward algorithm adds competing prefixes; Viterbi selects their maximum.

Fill the trellis for Low, Low, High

The initial scores are (0.10, 0.35). On day 2, the Sunny candidates before emission are $0.10(0.8)=0.08$ and $0.35(0.4)=0.14$. Keep the second and multiply by 0.2 to get 0.028, pointing to Cloudy. For Cloudy, compare 0.02 with 0.21; multiplying the larger by 0.7 gives 0.147, also pointing to Cloudy.

On day 3, Sunny compares $0.028(0.8)=0.0224$ with $0.147(0.4)=0.0588$. Multiplying the larger by the High likelihood 0.8 gives 0.04704. Cloudy compares 0.0056 with 0.0882; multiplying the larger by 0.3 gives 0.02646. Both final pointers lead to Cloudy on day 2.

Backtrack from the end

The largest final score is 0.04704 at Sunny. Follow its pointer to Cloudy on day 2, then that pointer to Cloudy on day 1. Reverse this backward traversal to obtain Cloudy, Cloudy, Sunny. Dividing by the evidence likelihood 0.1113 gives its posterior, approximately 0.4226.

Choosing the largest score separately at every column would discard the stored predecessor relationships. The final score vector also cannot be normalized into a filtering belief: it retains just one path per state, not their sums.

Use logarithms for long sequences

Products can underflow. Store log scores instead:

Logarithms preserve ordering, so the path and pointers stay unchanged. Zero probabilities become negative infinity. Equivalently, negative log scores turn decoding into a minimum-cost path through a time-layered graph, or trellis. Dense Viterbi costs $O(S^{2}t)$ time and stores $O(St)$ pointers. If paths tie for the largest score, each is a valid most likely explanation.

A probability table becomes difficult to store when the state space is huge. Continuous beliefs also lack a finite table in general. A particle filter represents a belief using sampled states, allowing computation to focus on a manageable population of possibilities.

Represent probability with particles

Each particle is one complete state, not a separate physical object. After resampling, all particles have equal weight, and a state's estimated probability is the fraction occupying it. Ten particles split seven Sunny and three Cloudy represent the belief (0.7, 0.3).

Draw initial particles from $P(X_1)$. A prior of (0.5, 0.5) gives expected equal counts but does not force every random sample to split equally. Under our time convention, weight these initial particles by the first observation and resample before any transition.

Elapse time by sampling transitions

For each later step, move each particle independently using the transition row for its current state. With weather rows (0.8, 0.2) and (0.4, 0.6), seven Sunny and three Cloudy particles have an expected sunny count of $7(0.8)+3(0.4)=6.8$ after moving.

One realized sample might contain six Sunny and four Cloudy particles. An expected count can be fractional; a realized particle count must be an integer. Keeping exactly 6.8 particles would not be a sampling algorithm.

Weight by the reading

Suppose the new solar output is Low. Each Sunny particle gets likelihood 0.2; each Cloudy particle gets 0.7. The six Sunny particles have total weight $6(0.2)=1.2$, and the four Cloudy particles have $4(0.7)=2.8$. Out of total weight 4.0, Sunny has weighted probability 0.3 and Cloudy 0.7.

Counts matter as well as per-particle weights. Normalizing only 0.2 and 0.7 would ignore how much predicted probability each group represented. Weighting reuses the same Bayes update as exact filtering on this sampled prediction.

Resample a fresh population

Draw ten particles with replacement, each old particle selected in proportion to its weight. Each new draw is Sunny with probability 0.3 and Cloudy with probability 0.7. The expected sunny count is three, though a run may give two, four, or another count. Multiple copies are allowed; they represent probability mass.

Reset the resulting particles to equal weights. Evidence has already affected which particles were copied, so retaining the old likelihood weights would count it again. The next iteration moves this new population before processing the next observation.

Compare with the exact update

Exact filtering from (0.7, 0.3) predicts (0.68, 0.32). Low then gives weights (0.136, 0.224), so the exact sunny posterior is $0.136\mathrm{/}0.36\approx 0.3778$. The particle run's weighted result was 0.3 because its random motion produced only six Sunny particles. Resampling introduces another source of variation.

The loop is therefore initialization, first-observation weighting and resampling, followed by repeated motion, weighting, and resampling. Before resampling, read weighted fractions; afterward, read counts. A step costs roughly $O(N)$ for $N$ particles when state sampling and weighting have fixed cost. For two weather states, exact filtering is simpler. Particle methods become useful when a large or continuous state lacks an affordable compact exact filter.

A particle estimate is random, so its quality depends on both population size and where the particles survive. More particles improve the approximation, but a large population can still be ineffective when nearly all its useful information sits in a few samples.

Understand the accuracy scale

For an independent-sample estimate of a probability $p$, the standard error is approximately $\sqrt{p(1-p)\mathrm{/}N}$. With $p=0.3$, this is about 0.046 for 100 samples and 0.0046 for 10,000. Particle-filter error often has the same rough $1\mathrm{/}\sqrt{N}$ scale, though resampled particles are dependent and model difficulty matters.

Quadrupling the population roughly halves error; doubling it does not. For a fixed observation history, increasing the number of particles makes a consistent particle filter approach the exact belief. This does not make one finite run exact or remove errors in the underlying model. Fix a random seed for reproducible comparisons, or compare results across several runs.

Distinguish two failures

Without resampling, multiplying likelihoods over many steps can leave almost every particle with negligible weight. Resampling replaces that waste with copies of useful states. But it can also erase an alternative location that temporarily fits less well.

Resampling alone cannot recreate an absent region. Recovery depends on motion samples reaching it or another mechanism introducing particles there. If transitions make that region nearly inaccessible, recovery may be slow. Adding small random perturbations or replacing a small fraction with fresh particles can help, but these choices must respect the state representation and intended approximation.

Handle zero total weight

If every particle receives weight zero, resampling probabilities are undefined. The observation may be possible elsewhere in the model even though the sampled population missed those states. Reinitialize from a suitable distribution, such as the prior or a uniform distribution over valid states, and check the sensor model. A nonzero outlier component can reduce these failures. If the model itself rules out the observation everywhere, more particles alone cannot fix it.

Choose a representation that fits the model

Exact forward filtering suits small discrete state spaces. A Kalman filter is exact when the prior is Gaussian and the transition and sensor models are linear with Gaussian noise; a mean and covariance then describe the belief. A particle filter accommodates nonlinear models and beliefs with separated peaks.

A single Gaussian cannot faithfully represent a robot that is likely in either of two distant corridors but unlikely between them. Particle clusters can retain both alternatives. For a linear-Gaussian tracking model, the Kalman representation usually avoids unnecessary sampling noise.

In a DBN, each particle holds a full assignment to all state variables. Sample next-step variables in topological order from their parent-conditioned models. Factoring reduces work per sample compared with enumerating every joint state, although high-dimensional beliefs may still require many particles to cover their important regions.

Tracking combines uncertain motion with noisy measurements. The hidden state may contain position and velocity; observations may come from GPS, radar, or a camera. Filtering carries a distribution of plausible locations from one reading to the next.

Localize in a five-cell corridor

A robot occupies one of five cells, with doors at cells 1 and 4. Its sensor reports a door with probability 0.9 at a door and 0.2 elsewhere. Start uniformly, with probability 0.2 per cell. A door report gives weights (0.18, 0.04, 0.04, 0.18, 0.04), totaling 0.48.

The updated belief is $(0.375,1\mathrm{/}12,1\mathrm{/}12,0.375,1\mathrm{/}12)\mathrm{.}$ Both door cells remain plausible. Selecting just one peak would throw away the symmetry the sensor has not resolved.

Move the whole belief

The robot tries to move one cell right. It succeeds with probability 0.8 and stays with probability 0.2; from cell 5 it stays with certainty at the wall. Every cell receives contributions from all starting cells that can reach it.

Cell 1 gets $0.375(0.2)=0.075$. Cell 2 gets $0.375(0.8)+(1\mathrm{/}12)(0.2)\approx 0.3167$. Cells 3 and 4 get approximately 0.0833 and 0.1417. Cell 5 gets $(0.375)(0.8)+1\mathrm{/}12\approx 0.3833$: both arrivals from cell 4 and all existing cell-5 mass remain there.

The prediction is approximately (0.0750, 0.3167, 0.0833, 0.1417, 0.3833). Handling the boundary as another ordinary 0.8 move would lose probability beyond the modeled corridor.

Observe no door

The no-door likelihood is 0.1 in cells 1 and 4 and 0.8 elsewhere. Multiplying the unrounded prediction gives total weight approximately 0.6483. Normalizing produces (0.0116, 0.3907, 0.1028, 0.0219, 0.4730).

The likely locations are now cells 2 and 5, just after the two doors. The belief remains multimodal, with separate peaks. One sensor reading is evidence, not a true-position measurement; keeping alternatives gives later motion and readings a chance to distinguish them.

Extend to realistic robots

In Monte Carlo localization, a particle is a pose: position in meters and heading. Move each pose using commanded motion plus noise, then weight it by agreement between observed ranges and ranges predicted from a known map. A concentrated initial population tracks a known starting location; a broad one supports global localization.

If the map is also unknown, include it in the hidden state. Simultaneous localization and mapping, or SLAM, estimates map and pose together. With multiple objects, another issue is data association: deciding which detection belongs to which object. Different assignments produce different trajectory hypotheses.

Vehicle tracking can combine a motion prediction with GPS readings. At 15 m/s with one-second steps, the expected motion is about 15 m between readings. A suitable Kalman model combines uncertain motion and measurement to reduce the effect of noisy readings. A transition model with no allowance for real motion variation can exclude the true trajectory, even when its arithmetic is correct.

Sequence models can infer labels as well as physical states. A speech recognizer connects a changing sound signal to possible words. A part-of-speech tagger connects observed words to hidden grammatical labels. Both must score choices in context across time.

Combine sound fit and language probability

Speech recognition seeks the word sequence with greatest posterior probability:

The acoustic model $P(s\mid w)$ scores how well words explain the sound; the language model $P(w)$ scores their prior plausibility. The shared denominator $P(s)$ does not affect the ranking. An acoustic likelihood is not itself a posterior probability of words.

For illustrative scores, compare “recognize speech” with “wreck a nice beach.” Acoustic likelihoods are 0.0004 and 0.0005; language probabilities are 0.00002 and 0.000001. The first product is $8\times {10}^{-9}$ and the second $5\times {10}^{-10}$. Language context makes the first phrase win despite its slightly lower acoustic likelihood.

Turn audio into a time sequence

A common setup uses overlapping 25 ms frames beginning every 10 ms, yielding about 100 feature vectors per second. The vectors are observations. Hidden states represent parts of speech sounds, or phones, often with beginning, middle, and end states. A pronunciation dictionary connects words to phones.

Self-loops allow a sound state to occupy multiple frames. Without duration flexibility, changing speaking speed would require a fixed and often unsuitable alignment between frames and sound states. Different state paths express different alignments of the same observed recording.

Represent short language context

A bigram model approximates a word sequence with $P(w_1){\prod }_{i=2}^{n}P(w_i\mid w_{i-1})$. A trigram uses the previous two words. Estimate these conditional probabilities from text counts. The Markov assumption here is a practical approximation: long-range grammatical and semantic relationships can extend beyond one or two preceding words.

Viterbi can find the best state path through linked phone and word models. For a large vocabulary, beam search discards less promising partial paths to reduce work. Once discarded, a path cannot win later, so a narrow beam can miss the best full path. Also, the best single state path for a word sequence differs in objective from summing all its possible alignments.

Use the same structure for tags

In part-of-speech tagging, states are tags and observations are words. Transitions score $P({\mathrm{t}\mathrm{a}\mathrm{g}}_i\mid {\mathrm{t}\mathrm{a}\mathrm{g}}_{i-1})$; emissions score $P({\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{d}}_i\mid {\mathrm{t}\mathrm{a}\mathrm{g}}_i)$. In “They can fish,” “can” may describe ability or putting fish into cans. The tag path must account for both word likelihoods and transitions between tags.

Place HMMs in speech practice

Large-vocabulary systems from the 1980s to the early 2010s commonly combined HMMs with Gaussian mixture acoustic models. Around 2010–2012, neural acoustic models became prominent in hybrid DNN–HMM systems. Modern end-to-end neural systems can map audio to text without an explicit HMM. The shared ideas of uncertain alignment, sequence scoring, and dynamic programming remain useful, and HMMs also appear in applications such as gene finding in DNA.