What a Markov-property check compares
A process is Markov when its current state contains all the information from its observed past that is relevant to predicting its next state. To check this, compare histories that end at the same state: if conditioning on those different histories gives different next-state distributions, the process is not Markov. If the distributions agree, the comparison supports the Markov property, but the check must cover all positive-probability histories at every time.
Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, let \(S\) be a finite state space, and let \((X_n)_{n\ge0}\) be an \(S\)-valued process. Its natural filtration is \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\), the information generated by the process through time \(n\). A history through time \(n\) is a specification of the values \(X_0,\ldots,X_n\). A conditional probability given a history is used only when that history has positive probability.
This definition permits transition probabilities to depend on time \(n\). If the conditional probability also does not depend on \(n\), the process is time-homogeneous: there is one transition matrix \(P=(p_{ij})\) such that \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\) for every \(n\) and every \(i\) with \(\mathbb{P}(X_n=i)>0\). Each row of a transition matrix is a probability distribution, so its entries are nonnegative and sum to \(1\). Homogeneity is an additional property, not part of the Markov property itself.
A precise history test
For a finite state space, at any fixed time \(n\), the events specifying the complete histories form the atoms of \(\mathcal{F}_n\), after histories of probability zero are ignored. This gives a direct test using conditional probabilities on those atoms.
Proof. Suppose first that the process is Markov. By definition, for each \(j\in S\), the conditional probability of \(X_{n+1}=j\) given \(\mathcal{F}_n\) equals the conditional probability given \(X_n\), almost surely. On either history event \(h\) or \(h'\), the current state is \(i\). Since each event has positive probability, conditioning the almost-sure equality on that event gives the same value, \(\mathbb{P}(X_{n+1}=j\mid X_n=i)\), for both histories. This holds for every \(j\), so the conditional distributions agree. Conversely, suppose the distributions agree for every pair of positive-probability histories ending at the same state. For each \(n\), define \(g_j(i)\) to be their common conditional probability of \(X_{n+1}=j\) for histories ending at \(i\) that have positive probability. If \(\mathbb{P}(X_n=i)=0\), the value of \(g_j(i)\) can be chosen arbitrarily, since that state is encountered with probability zero at time \(n\). On each positive-probability history atom, the conditional probability given \(\mathcal{F}_n\) is constant and equals \(g_j(X_n)\). Thus \(\mathbb{P}(X_{n+1}=j\mid\mathcal{F}_n)=g_j(X_n)=\mathbb{P}(X_{n+1}=j\mid X_n)\) almost surely. This is the Markov property. \(\square\)
The test is about the whole conditional distribution, not just one summary such as its mean. For a finite state space, it is enough to compare the probability of each possible next state. Also, equality at one time or for a selection of histories is not enough: the definition requires the condition at every time and for all relevant histories.
Choose \(n\) and a state \(i\). Only compare histories whose final state at time \(n\) is \(i\).
Use conditional probabilities only for histories with positive probability. A conditional probability given an event of probability zero is not defined by the elementary ratio formula.
For every \(j\in S\), find the conditional probability of \(X_{n+1}=j\) given each history.
Different distributions for histories ending at the same state disprove the Markov property. To establish it, the equality must hold for every such comparison at every time.
Worked examples: passing and failing the test
Worked Example: An Independent Bernoulli Process
Let \((Y_n)_{n\ge0}\) be independent Bernoulli random variables with \(\mathbb{P}(Y_n=1)=\tfrac13\) and \(\mathbb{P}(Y_n=0)=\tfrac23\), and set \(X_n=Y_n\). The process has state space \(S=\{0,1\}\). Check the Markov property by conditioning on histories.
Fix \(n\), and consider any positive-probability history \(X_0=i_0,\ldots,X_n=i_n\). Independence means \(Y_{n+1}\) is independent of \(Y_0,\ldots,Y_n\). Since \(X_k=Y_k\), the event specifying the history is determined by those earlier variables. Therefore
Both possible histories through any finite time have positive probability, because each specified value has positive probability and the variables are independent. In particular, any two histories ending in the same state give the same next-state distribution. The process is Markov. Its time-homogeneous transition matrix, with states ordered as \(0,1\), is
Check: The first row sums to \(\tfrac23+\tfrac13=1\), and the second row sums to \(\tfrac23+\tfrac13=1\). For example, conditioning on either history \((0,1,0)\) or \((1,1,0)\), both of which have positive probability, gives probability \(\tfrac13\) that the next state is \(1\). The histories differ, but the current state is \(0\) in each and the conditional distributions agree.
Worked Example: A Markov Chain with Two Histories to Compare
Consider a time-homogeneous Markov chain \((X_n)_{n\ge0}\) on \(S=\{0,1\}\), with initial row distribution \(\mu=(\tfrac12,\tfrac12)\) and transition matrix
The rows sum to \(1\): \(\tfrac12+\tfrac12=1\) and \(\tfrac13+\tfrac23=1\). Compare histories \((0,1)\) and \((1,1)\) through time \(1\). Each ends at state \(1\), and both have positive probability. By the path-probability rule, their probabilities are
For the first history, the probability of the extended path \((0,1,1)\) is \(\tfrac12\cdot\tfrac12\cdot\tfrac23=\tfrac16\). Thus
For the second history, the probability of \((1,1,1)\) is \(\tfrac12\cdot\tfrac23\cdot\tfrac23=\tfrac29\). Therefore
The probability of next state \(0\) is \(1-\tfrac23=\tfrac13\) for both histories. The distributions agree, as the Markov property requires. The calculation also checks that conditioning on the current state \(X_1=1\) gives the same probability: \(\mathbb{P}(X_2=1\mid X_1=1)=\tfrac23\). In this example the transition probabilities are independent of time, so the chain is homogeneous as well as Markov.
Worked Example: Overlapping Variables Reveal Dependence on the Past
Let \((Z_n)_{n\ge0}\) be independent fair Bernoulli variables on a probability space, and define \(X_n=Z_nZ_{n+1}\), with state space \(S=\{0,1\}\). Thus \(X_n=1\) precisely when both \(Z_n\) and \(Z_{n+1}\) equal \(1\). Compare histories through time \(1\) that end at \(X_1=0\).
First, the history \((X_0,X_1)=(1,0)\) has positive probability. It requires \(Z_0=Z_1=1\) and \(Z_2=0\), so its probability is \(\tfrac12\cdot\tfrac12\cdot\tfrac12=\tfrac18\). On this event, \(X_2=Z_2Z_3=0\), regardless of \(Z_3\). Hence
Now condition only on \(X_1=0\). This event has probability \(1-\mathbb{P}(Z_1=1,Z_2=1)=1-\tfrac14=\tfrac34\). The joint event \(X_1=0,X_2=1\) requires \(Z_2=Z_3=1\) and \(Z_1=0\); \(Z_0\) can be either value. Its probability is \(\tfrac12\cdot\tfrac12\cdot\tfrac12=\tfrac18\). Consequently
The two conditional probabilities, \(0\) and \(\tfrac16\), differ, even though both conditioning histories end in state \(0\). Therefore this process is not Markov. The discrepancy has a direct explanation: knowing \(X_0=1\) forces \(Z_1=1\), and then \(X_1=0\) forces \(Z_2=0\); that makes \(X_2=1\) impossible. Knowing only \(X_1=0\) does not determine \(Z_2\) in this way.
For comparison, at time \(1\) the current-state conditional probabilities alone would give \(\mathbb{P}(X_2=1\mid X_1=0)=\tfrac16\) and \(\mathbb{P}(X_2=1\mid X_1=1)=\tfrac12\). These correspond to the current-state transition matrix \(\begin{bmatrix}\tfrac56&\tfrac16\\\tfrac12&\tfrac12\end{bmatrix}\), whose rows sum to \(1\). But those current-state probabilities do not establish the Markov property: the history comparison above contradicts the required equality.
Common mistake and why the distinction matters
A common mistake is to calculate \(\mathbb{P}(X_{n+1}=j\mid X_n=i)\) and stop. That calculation averages over all possible histories ending at \(i\). Different histories can contribute to the average with different conditional probabilities, so the average can conceal a disagreement. In the overlapping-variable example, the current-only probability \(\tfrac16\) is an average over histories with \(X_1=0\); it does not equal the probability \(0\) given the particular history \((1,0)\).
Common mistake: treating the averaged value as proof. The incorrect argument is: “Given \(X_1=0\), the probability of \(X_2=1\) is \(\tfrac16\); therefore the process is Markov.” The correction is to compare against another positive-probability history with the same current state. Here \((X_0,X_1)=(1,0)\) has probability \(\tfrac18\) and gives conditional probability \(0\), while conditioning only on \(X_1=0\) gives \(\tfrac16\). Since these differ, the Markov property fails.
There are two other points to keep separate. First, a history with probability zero cannot be used in a ratio such as \(\mathbb{P}(A\cap B)/\mathbb{P}(B)\); the Markov property is an almost-sure statement and imposes no condition on a null history. Second, a process may be Markov even if its transition probabilities vary with time. To claim time-homogeneity, one must additionally check that the conditional next-state probabilities do not change with \(n\). The central Markov check remains the same: at each time, histories sharing the same current state must give the same conditional next-state distribution.
Check Your Understanding
For each question, use only histories with positive probability when computing conditional probabilities.
- For a process on \(\{0,1\}\), two histories through time \(n\) both end at \(1\). What must be true of their conditional distributions for the Markov property to hold?
- In the overlapping-variable example, calculate \(\mathbb{P}(X_2=0\mid X_0=1,X_1=0)\). Why does this confirm the distributional comparison?
- Suppose \(\mathbb{P}(X_{n+1}=1\mid X_n=0)=\tfrac14\). Does this single probability establish the Markov property? Explain what else must be checked.
- Why may a conditional probability given a zero-probability history not be used in the elementary ratio test?
- What additional condition distinguishes a time-homogeneous Markov chain from a Markov process whose transition probabilities may vary with time?