The Markov Property

The Markov property is the fundamental assumption that the future evolution of a stochastic process depends only on its present state, not on its past history. This "memoryless" property makes Markov chains tractable for analysis while remaining rich enough to model many real-world phenomena.

Discrete-time Markov chains

Definition1.1Markov chain

A discrete-time stochastic process $(X_n)_{n \geq 0}$ taking values in a countable state space $S$ is a Markov chain if for all $n \geq 0$ and all states $i_0, i_1, \ldots, i_n, j \in S$ :

$\mathbb{P}(X_{n+1} = j \mid X_n = i_n, X_{n-1} = i_{n-1}, \ldots, X_0 = i_0) = \mathbb{P}(X_{n+1} = j \mid X_n = i_n),$

whenever the conditional probabilities are well-defined.

The right-hand side $\mathbb{P}(X_{n+1} = j \mid X_n = i)$ is called the transition probability from state $i$ to state $j$ .

RemarkTime-homogeneous chains

A Markov chain is time-homogeneous (or stationary) if the transition probabilities do not depend on time: $p_{ij}(n) = p_{ij}$ for all $n$ . Unless stated otherwise, we work with time-homogeneous chains and denote

$p_{ij} = \mathbb{P}(X_{n+1} = j \mid X_n = i).$

The matrix $P = (p_{ij})$ is called the transition matrix.

ExampleSimple random walk on Z

On $S = \mathbb{Z}$ , let $X_0 = 0$ and

$X_{n+1} = X_n + \xi_n,$

where $\xi_n$ are i.i.d. with $\mathbb{P}(\xi_n = 1) = p$ and $\mathbb{P}(\xi_n = -1) = q = 1-p$ . Then $(X_n)$ is a Markov chain with transition probabilities:

$p_{i,i+1} = p, \quad p_{i,i-1} = q, \quad p_{ij} = 0 \text{ if } |i-j| \neq 1.$

This is the simple random walk on $\mathbb{Z}$ .

ExampleTwo-state chain

Let $S = \{0, 1\}$ with transition matrix

$P = \begin{pmatrix} 1-\alpha & \alpha \\ \beta & 1-\beta \end{pmatrix}.$

If $\alpha, \beta \in (0,1)$ , the chain moves between states with positive probability. The stationary distribution (if it exists) satisfies $\pi P = \pi$ , giving

$\pi_0 = \frac{\beta}{\alpha + \beta}, \quad \pi_1 = \frac{\alpha}{\alpha + \beta}.$

The Chapman-Kolmogorov equation

Definition1.2n-step transition probability

The $n$ -step transition probability is

$p_{ij}^{(n)} = \mathbb{P}(X_{m+n} = j \mid X_m = i),$

the probability of being in state $j$ exactly $n$ steps after starting in state $i$ .

Theorem1.1Chapman-Kolmogorov equation

For all states $i, j \in S$ and all integers $m, n \geq 0$ :

$p_{ij}^{(m+n)} = \sum_{k \in S} p_{ik}^{(m)} p_{kj}^{(n)}.$

In matrix form, $P^{(m+n)} = P^{(m)} P^{(n)}$ , i.e., $P^{(n)} = P^n$ .

The proof follows from the law of total probability and the Markov property: to go from $i$ to $j$ in $m+n$ steps, we must pass through some intermediate state $k$ at time $m$ .

ExampleComputing P²

For the two-state chain with

$P = \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix},$

we compute

$P^2 = \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix}^2 = \begin{pmatrix} 0.61 & 0.39 \\ 0.52 & 0.48 \end{pmatrix}.$

Thus, $p_{00}^{(2)} = 0.61$ : starting in state 0, the probability of being in state 0 after 2 steps is 0.61.

Strong Markov property

Definition1.3Stopping time

A random variable $\tau: \Omega \to \{0, 1, 2, \ldots\} \cup \{\infty\}$ is a stopping time with respect to $(X_n)$ if the event $\{\tau = n\}$ depends only on $X_0, X_1, \ldots, X_n$ for each $n \geq 0$ .

Intuitively, the decision to stop at time $n$ can be made using only information available up to time $n$ .

ExampleHitting times are stopping times

For a set $A \subseteq S$ , the hitting time (or first passage time) is

$\tau_A = \inf\{n \geq 0 : X_n \in A\}.$

Then $\tau_A$ is a stopping time: $\{\tau_A = n\}$ occurs iff $X_0, \ldots, X_{n-1} \notin A$ and $X_n \in A$ , which depends only on $X_0, \ldots, X_n$ .

Theorem1.2Strong Markov property

Let $\tau$ be a stopping time with $\mathbb{P}(\tau < \infty) = 1$ . Then, conditionally on $\{\tau < \infty, X_\tau = i\}$ , the process $(X_{\tau+n})_{n \geq 0}$ is a Markov chain starting from $i$ , independent of $X_0, \ldots, X_\tau$ .

The strong Markov property says that "restarting" the chain at a random (stopping) time preserves the Markov property. This is crucial for analyzing recurrence and transience.

RemarkApplication to recurrence

Using the strong Markov property, we can decompose long-run behavior into i.i.d. excursions between visits to a fixed state. This leads to the classification of states into recurrent and transient states (see Theorem 1.3 and related content).

Irreducibility and aperiodicity

Definition1.4Irreducibility

A Markov chain is irreducible if for every pair of states $i, j \in S$ , there exists $n \geq 0$ such that $p_{ij}^{(n)} > 0$ . In other words, every state is accessible from every other state.

Definition1.5Period

The period of a state $i$ is

$d(i) = \gcd\{n \geq 1 : p_{ii}^{(n)} > 0\}.$

State $i$ is aperiodic if $d(i) = 1$ . A chain is aperiodic if all states are aperiodic.

ExamplePeriodic random walk

The simple symmetric random walk on $\mathbb{Z}$ has period 2: starting from the origin, $X_n$ is even if $n$ is even and odd if $n$ is odd. Hence $p_{00}^{(n)} = 0$ for all odd $n$ .

RemarkIrreducibility + aperiodicity

For an irreducible, aperiodic Markov chain on a finite state space, the distribution $\mathbb{P}(X_n = j \mid X_0 = i)$ converges to a unique stationary distribution $\pi$ as $n \to \infty$ , regardless of the initial state $i$ . This is the content of the convergence theorem (see Theorem 1.4).

Summary

The Markov property provides a mathematically tractable framework for modeling random evolution:

Memorylessness: Future depends only on present, not past.
Chapman-Kolmogorov: $n$ -step transitions multiply as matrices.
Strong Markov property: Restarting at a stopping time preserves the Markov property.
Irreducibility and aperiodicity: Ensure long-run convergence to equilibrium.

These foundational concepts underpin the entire theory of Markov chains, from finite-state models to general state space processes.