Markov Chain Monte Carlo (MCMC)

The crime story of a Mathematical Smuggler

A seasoned intelligence operative was assigned a difficult mission: track an arms smuggler who never stayed in one place long enough to be caught. The smuggler moved relentlessly across cities, completing deals and vanishing before anyone could react. Following him directly was impossible.

So the operative chose a different approach. Instead of chasing the smuggler, he decided to understand his movement.

He began keeping a diary.

Each page of the diary represented a step in the smuggler’s journey. On the $t^{th}$ page, he wrote down a vector that captured his belief about the smuggler’s location. For every city $k$, he recorded the probability that the smuggler would be there after $t$ moves. At the beginning, these probabilities were uncertain and scattered.

However, the operative had one powerful piece of information. Through intelligence reports, he had determined how the smuggler moved between cities. He represented this behavior as a matrix $P$, where each entry $P_{ij}$ described the probability of traveling from city $i$ to city $j$.

With this, the diary became more than just notes. It became a system.

If the probabilities on page $t$ were given by $x_t$, then the next page followed a precise rule:

$$x_{t+1} = x_t P$$

Each new page was obtained by applying the same transition matrix. The operative did not need to guess anymore. He could compute how his belief evolved over time.

As the pages filled, something interesting happened. The probabilities began to settle. The changes between consecutive pages became smaller and smaller. Eventually, the distribution reached a stable form that barely changed with further updates.

The operative understood what this meant.

The smuggler’s movement was not arbitrary. It followed a Markov chain, where each step depended only on the current city. Because of this structure, repeated application of the transition matrix revealed a long-term pattern.

The diary no longer just described where the smuggler might be next. It revealed where he was most likely to be found in the long run.