Prediction from the Present
Suppose we observe a process up to time \(n\) and want to predict \(X_{n+1}\). The Markov property says that, for this prediction, the whole observed history can be replaced by the current state \(X_n\). It does not say that the states at different times are independent. Rather, it says that earlier observations provide no additional information about the next state once the current state is known.
Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, and let \((X_n)_{n\ge0}\) be a discrete-time process with values in a finite or countable state space \(S\). Its natural filtration is \(\mathcal{F}_n^X=\sigma(X_0,\ldots,X_n)\), the information generated by the observations up to time \(n\). Write \(\mathcal{H}_n=\sigma(X_0,\ldots,X_{n-1})\) for the information strictly before time \(n\); \(\mathcal{H}_0\) contains only the sure and impossible events.
For a state \(i\) with \(\mathbb{P}(X_n=i)>0\), the right side describes the conditional distribution of \(X_{n+1}\) given \(X_n=i\). If \(\mathbb{P}(X_n=i)=0\), conditioning on the event \(X_n=i\) by an ordinary ratio is not defined. The conditional-expectation formulation avoids assigning a meaningful prediction to such a zero-probability event; any version of the conditional expectation is only determined almost surely.
Conditional Independence: The Precise Meaning
Two sources of information can remain associated overall and yet become independent after a third quantity is known. Here, the two sources are the next state and the history strictly before the current state. The quantity being conditioned on is the current state.
This factorization is the conditional-independence version of the Markov property. It says that once \(X_n\) is given, learning whether a particular earlier-history event \(H\) occurred does not change the conditional probability of \(X_{n+1}\in A\).
Proof. Let \(g=\mathbb{E}[\mathbf{1}_{\{X_{n+1}\in A\}}\mid\sigma(X_n)]\), for a fixed set \(A\subseteq S\). First suppose the Markov property holds. For \(H\in\mathcal{H}_n\), the event \(H\) is measurable with respect to \(\mathcal{F}_n^X\). The tower property of conditional expectation therefore gives $$ \begin{aligned} \mathbb{E}[\mathbf{1}_{\{X_{n+1}\in A\}}\mathbf{1}_H\mid\sigma(X_n)] &=\mathbb{E}\!\left[ \mathbb{E}[\mathbf{1}_{\{X_{n+1}\in A\}}\mid\mathcal{F}_n^X]\mathbf{1}_H \mid\sigma(X_n)\right]\\ &=\mathbb{E}[g\mathbf{1}_H\mid\sigma(X_n)]\\ &=g\,\mathbb{E}[\mathbf{1}_H\mid\sigma(X_n)]. \end{aligned} $$ The second equality uses the Markov property, and the third uses that \(g\) is measurable with respect to \(\sigma(X_n)\). This is the conditional-independence factorization.
Conversely, suppose the factorization holds for all \(A\) and \(H\). By the definition of \(g\), the right side of that factorization is \(g\,\mathbb{E}[\mathbf{1}_H\mid\sigma(X_n)]\). To verify that \(g\) is also the conditional expectation given \(\mathcal{F}_n^X\), test it on events in that sigma-field. Since \(X_n\) is countable-valued, every event \(D\in\mathcal{F}_n^X=\mathcal{H}_n\vee\sigma(X_n)\) can be written as a countable union of events \(H_j\cap\{X_n=j\}\), with \(H_j\in\mathcal{H}_n\). Applying the assumed factorization with \(H=H_j\), multiplying by \(\mathbf{1}_{\{X_n=j\}}\), and taking expectations gives $$ \mathbb{E}[\mathbf{1}_{\{X_{n+1}\in A\}}\mathbf{1}_{H_j}\mathbf{1}_{\{X_n=j\}}] = \mathbb{E}[g\mathbf{1}_{H_j}\mathbf{1}_{\{X_n=j\}}]. $$ Summing these equalities over the countable state space gives \(\mathbb{E}[\mathbf{1}_{\{X_{n+1}\in A\}}\mathbf{1}_D]=\mathbb{E}[g\mathbf{1}_D]\) for every \(D\in\mathcal{F}_n^X\). This is the defining property of the conditional expectation given \(\mathcal{F}_n^X\), so the Markov property follows. \(\square\)
A Test Using Positive-Probability Histories
When the state space is countable, the information in \(\mathcal{F}_n^X\) is generated by the finite histories \((X_0,\ldots,X_n)\). This gives a direct way to test the property. A history is relevant to an ordinary conditional-probability calculation only when its probability is positive.
Proof. For each history with positive probability, the event specifying that history is an atom of \(\mathcal{F}_n^X\). The conditional expectation of \(\mathbf{1}_{\{X_{n+1}=j\}}\) given \(\mathcal{F}_n^X\) on that event is the ordinary conditional probability displayed in the proposition. If the Markov property holds, this conditional expectation is a function of \(X_n\) almost surely. Thus all positive-probability histories ending at \(i\) give the same value. Conversely, suppose that for each such \(i\) the value is constant across histories ending at \(i\). Define \(g(i)\) to be that common value for states with positive probability, and assign any value to \(g(i)\) for states with zero probability. Then the conditional expectation given \(\mathcal{F}_n^X\) equals \(g(X_n)\) almost surely. Since \(g(X_n)\) is the conditional probability given \(\sigma(X_n)\), the defining equality of the Markov property holds. \(\square\)
Worked Example: An Independent Bernoulli Sequence
Let \((X_n)_{n\ge0}\) be independent Bernoulli random variables on a probability space, with state space \(S=\{0,1\}\) and \(\mathbb{P}(X_n=1)=\tfrac13\) for every \(n\). For any positive-probability history through time \(n\), independence gives $$ \mathbb{P}(X_{n+1}=1\mid X_0=x_0,\ldots,X_n=x_n)=\tfrac13,\qquad \mathbb{P}(X_{n+1}=0\mid X_0=x_0,\ldots,X_n=x_n)=\tfrac23. $$ The probabilities sum to \(\tfrac13+\tfrac23=1\), and neither depends on the history or on the current state. Consequently the conditional distribution given the full history agrees with the conditional distribution given \(X_n\), so the process has the Markov property.
For a numerical check on a history, take \(n=1\) and the event \(X_0=1,X_1=0\). Its probability is \(\tfrac13\cdot\tfrac23=\tfrac29>0\). The probability of that history followed by \(X_2=1\) is \(\tfrac13\cdot\tfrac23\cdot\tfrac13=\tfrac{2}{27}\), so the conditional probability is \((\tfrac{2}{27})/(\tfrac29)=\tfrac13\), as required.
Worked Example: A Process That Fails the Test
Let \(X_0\) and \(X_1\) be independent fair binary variables on a probability space, and set \(X_2=X_0\). Consider the process at time \(n=1\), with state space \(S=\{0,1\}\). Its four possible pairs \((X_0,X_1)\) each have probability \(\tfrac14\), so their probabilities sum to \(4\cdot\tfrac14=1\).
On the positive-probability history \(X_0=0,X_1=0\), the definition \(X_2=X_0\) gives \(\mathbb{P}(X_2=1\mid X_0=0,X_1=0)=0\). But the event \(X_1=0\) has probability \(\tfrac12\), and within it the two possible values of \(X_0\) each have probability \(\tfrac14\). Therefore $$ \mathbb{P}(X_2=1\mid X_1=0) =\frac{\mathbb{P}(X_0=1,X_1=0)}{\mathbb{P}(X_1=0)} =\frac{\tfrac14}{\tfrac12} =\tfrac12. $$ The full-history and current-state conditional probabilities differ on an event of probability \(\tfrac14\), so the Markov property fails at time \(1\).
Check: Conditioning only on \(X_1=0\) averages over the two possible earlier values, giving \(\tfrac12(0)+\tfrac12(1)=\tfrac12\) for the probability that \(X_2=1\). Conditioning on the particular history \(X_0=0,X_1=0\) instead gives \(0\). Both calculations use events of positive probability.
Worked Example: Conditional Independence Does Not Mean Independence
Let \(X_0\) be fair on \(\{0,1\}\), and let \(U_1,U_2\) be independent binary variables, independent of \(X_0\), with \(\mathbb{P}(U_k=1)=\tfrac14\) and \(\mathbb{P}(U_k=0)=\tfrac34\). Define \(X_1=X_0\mathbin{\oplus}U_1\) and \(X_2=X_1\mathbin{\oplus}U_2\), where \(\oplus\) is addition modulo \(2\). Each step flips the state with probability \(\tfrac14\) and leaves it unchanged with probability \(\tfrac34\); these two conditional probabilities sum to \(1\).
Given any positive-probability history through \(X_1\), the independent variable \(U_2\) still has probability \(\tfrac14\) of being \(1\). Thus the conditional probabilities of \(X_2=X_1\) and \(X_2\ne X_1\) are respectively \(\tfrac34\) and \(\tfrac14\), regardless of \(X_0\). This verifies the Markov property at time \(1\).
Nevertheless, \(X_0\) and \(X_2\) are not independent. They are equal exactly when either neither flip occurs or both flips occur. Hence $$ \mathbb{P}(X_0=X_2)=\left(\tfrac34\right)^2+\left(\tfrac14\right)^2 =\tfrac9{16}+\tfrac1{16} =\tfrac58. $$ Both \(X_0\) and \(X_2\) are fair, so independence would instead give \(\mathbb{P}(X_0=X_2)=\tfrac12\). A direct joint-probability check gives \(\mathbb{P}(X_0=0,X_2=0)=\tfrac12\cdot\tfrac58=\tfrac5{16}\), whereas \(\mathbb{P}(X_0=0)\mathbb{P}(X_2=0)=\tfrac12\cdot\tfrac12=\tfrac14\). The states at separated times can therefore be dependent even though the next state is conditionally independent of earlier history given the current state.
For the conditional-independence interpretation, \(U_2\) is independent of \((X_0,X_1)\). Once \(X_1\) is given, \(X_2\) is determined by \(U_2\), while the earlier variable \(X_0\) is determined without using \(U_2\). Thus the randomness that determines the next step does not add information about \(X_0\) once \(X_1\) is known.
A Common Mistake
A frequent error is to compute a conditional probability given only the current state and assume that it must also be the answer after conditioning on the full history. In the second example, \(\mathbb{P}(X_2=1\mid X_1=0)=\tfrac12\). Using this value for the history \(X_0=0,X_1=0\) would incorrectly claim that \(\mathbb{P}(X_2=1\mid X_0=0,X_1=0)=\tfrac12\). The actual value is \(0\), because \(X_2=X_0\). The correction is to compare the two conditional probabilities rather than presume they agree. Their agreement on every positive-probability history is exactly what must be checked.
The Markov property is therefore a statement about the information relevant to one-step prediction. It neither asserts stationarity nor says that observations at different times are independent. Its conditional-independence formulation is useful because it identifies precisely what the current state screens off: the influence of the earlier history on the next observation.
Check Your Understanding
Use conditional probabilities only on events with positive probability, and distinguish conditioning on the current state from conditioning on the full history.
- State the Markov property at time \(n\) using conditional expectations and the natural filtration.
- In the failing-process example, compute \(\mathbb{P}(X_2=1\mid X_0=1,X_1=0)\). Is this history positive-probability?
- Explain why conditional independence of \(X_{n+1}\) and the earlier history given \(X_n\) does not imply that \(X_{n+1}\) is ordinarily independent of that history.
- Why does the finite-history test omit histories whose probability is zero?
- For the flip process, what are the conditional probabilities of \(X_{n+1}=X_n\) and \(X_{n+1}\ne X_n\) given the observed history through time \(n\)?