Stochastic Processes 5: Markov Processes

The Markov process is one of the most important classes of stochastic processes, often loosely summarized as “the future depends only on the present, not the past.” That phrase is easy to remember but easy to misread: if $X_1$ affects $X_2$, and $X_2$ affects $X_3$, then $X_1$ clearly affects $X_3$ indirectly through $X_2$ — so how can we still say $X_3$ doesn’t depend on the past? The key is that the Markov property doesn’t say “the past has no effect” — it says once the current state is known, the past provides no additional information.

1. The Markov Property

1.1 Definition: conditional independence, not memorylessness

The discrete-time first-order Markov property is written $P(X_{t+1}\mid X_t,X_{t-1},\dots,X_0)=P(X_{t+1}\mid X_t)$: once the current state $X_t$ is known, the earlier history $X_{t-1},X_{t-2},\dots$ provides no additional information for predicting the next step $X_{t+1}$.

Consider the dependency chain $X_1\rightarrow X_2\rightarrow X_3$: in general, $X_1$ and $X_3$ being correlated ($X_1\not\perp X_3$) is entirely possible, since influence can propagate along the chain. But the Markov property requires $X_1\perp X_3\mid X_2$: once $X_2$ is known, being additionally told $X_1$ doesn’t further change the conditional distribution of $X_3$. This is called conditional independence — Probability and Statistics 2 Section 4 discussed how a conditional distribution changes with new information, which is the foundation for understanding conditional independence.

1.2 Verifying conditional independence with a two-state example

Suppose a system has only states 0 and 1, and at each step there’s a 90% chance of staying in the same state and a 10% chance of flipping. If we only know $X_1=1$, we can indeed use it to infer something about $X_3$: the probability of $1\to1\to1$ is $0.9\times0.9=0.81$, and the probability of $1\to0\to1$ is $0.1\times0.1=0.01$; adding the two paths together, $P(X_3=1\mid X_1=1)=0.82$, clearly different from the probability of a single flip.

But once we already know $X_2=0$, $P(X_3=1\mid X_2=0)=0.1$; at that point, even if we’re additionally told $X_1=1$, the result is still $P(X_3=1\mid X_2=0,X_1=1)=0.1$ — completely unchanged. What’s actually cut off is “additional information,” not the past’s historical influence on the present — the past still affects $X_3$ through $X_2$; it’s just that once $X_2$ is known, $X_1$ can no longer add anything.

2. State Design Determines the Markov Property

2.1 The same system can become Markov with a different state representation

Consider a moving object: if only its current position $X_t$ is used as the state, that’s usually not enough to predict its position a second later, since velocity also matters — two cars currently at the same position, one moving east at high speed and one moving west at high speed, will clearly be in different places a second later, so the “position process” alone may not be Markov. But once the state is expanded to $S_t=(X_t,V_t)$, including both position and velocity, then in a simple dynamics model $S_{t+1}$ may depend only on $S_t$. The same physical system can behave as Markov or non-Markov depending on which state representation is chosen — this is the step most easily overlooked when choosing a state representation, and the most common source of modeling errors.

2.2 A non-Markov example and how to fix it

Consider $X_{t+1}=X_t+X_{t-1}+\epsilon_t$: knowing $X_t$ alone isn’t enough to determine the conditional distribution of the next step, because $X_{t-1}$ still provides additional information, $P(X_{t+1}\mid X_t,X_{t-1})\neq P(X_{t+1}\mid X_t)$ — this is a simple non-first-order Markov process. After redefining the state as $S_t=(X_t,X_{t-1})$, the new state process becomes first-order Markov again — this trick can be applied almost without limit: any $k$-th-order Markov process can be rewritten in first-order Markov form by packing the past $k$ steps into a larger state, at the cost of the state space growing exponentially with $k$.

3. Markov Chains and Transition Matrices

3.1 The one-step transition matrix

When both time and the state space are discrete, the result is a Markov chain. Suppose the state space has only $A,B,C$; the one-step transition matrix can be written as:

$$P= \begin{bmatrix} 0.7 & 0.2 & 0.1\\ 0.1 & 0.8 & 0.1\\ 0.3 & 0.2 & 0.5 \end{bmatrix}$$

The first row means that, currently at A, the probability of staying at A next step is 0.7, moving to B is 0.2, and moving to C is 0.1; every row sums to 1, since the next step must land on some state.

3.2 Multi-step transitions: the Chapman–Kolmogorov equation worked out

Given the one-step transition matrix $P$, the transition probability after any number of steps is a power of $P$: the $n$-step transition matrix equals $P^n$. Using the $P$ above as an example, computing $P^2$ gives the probability of going from A to B in two steps, $P(X_2=B\mid X_0=A)=0.32$. This number can also be verified directly by summing over paths: the probability of reaching B within two steps by passing through the three possible intermediate states A, B, or C is $0.7\times0.2=0.14$ (via A), $0.2\times0.8=0.16$ (via B), and $0.1\times0.2=0.02$ (via C) respectively, and the three sum to exactly $0.14+0.16+0.02=0.32$. This is a concrete demonstration of the Chapman–Kolmogorov equation: a multi-step transition probability equals the sum, over every possible intermediate state, of the probability of “reaching the intermediate state first” multiplied by “reaching the destination from there.” A seemingly complex long-run random evolution can therefore be built entirely by composing local one-step transition rules, with no additional assumptions needed.

4. Common Misconceptions and Model Limitations

The most common misconception is understanding the Markov property as “the past and future are entirely unrelated” — what it actually means is that, given the current state, the past no longer provides additional information; the past can still affect the future indirectly through the current state, its effect has simply been compressed into $X_t$. The second common mistake is insufficient state design: many systems that “look non-Markov” simply have too narrow a state, and adding back the missing information (such as velocity in the earlier example, or higher-order history) makes them Markov again — but this also means the first-order Markov assumption can always be satisfied by this kind of “cheating.” The genuinely meaningful question is often not “can this be written as Markov” but “how large a state space is needed to write it as Markov” — an overly bloated state space makes estimation and computation impractical. The third limitation is that transition probabilities are usually assumed not to change over time (time-homogeneous); if the system’s own dynamics evolve over time, a time-varying transition matrix needs to be handled separately, and the $P^n$ result can’t be applied directly.

5. Summary

The Markov property is conditional independence, not “the past and future are unrelated”: given the current state, the past provides no additional information about the future, but the past’s influence can still propagate along a chain like $X_1\to X_2\to X_3$ — it has simply been compressed into the current state. Whether a process is Markov depends on how the state is defined, which is also why state representation is so central to Markov theory. The one-step transition matrix, through matrix powers, can be composed into the transition probability after any number of steps — a property that is also the computational foundation for discussing a Markov chain’s long-run behavior next, in Stochastic Processes 6: Long-Run Behavior of Markov Chains — concepts such as stationary distribution, recurrent, transient, absorbing state, and mixing.