What “One-Step Memory” Means
A Markov chain is often described as a process with “one-step memory.” This phrase does not mean that successive states are independent. It means that, once the current state is known, the earlier history gives no additional information about the next state. The distinction matters: the current state may itself carry information from earlier times, so states at different times can remain dependent even when the Markov property holds.
Let \((X_n)_{n\ge0}\) be a discrete-time process on a probability space \((\Omega,\mathcal F,\mathbb P)\), with finite state space \(S\). Use its natural filtration \(\mathcal F_n=\sigma(X_0,\ldots,X_n)\), the information generated by the states observed through time \(n\). For an event \(A\) with \(\mathbb P(A)>0\), conditional probability given \(A\) is \(\mathbb P(B\mid A)=\mathbb P(B\cap A)/\mathbb P(A)\). Conditional statements given a state are understood only for states that occur with positive probability, or as almost-sure statements.
The current state is therefore sufficient for predicting the next state, in the specific sense of the displayed conditional probability. The definition places no requirement that \(X_n\) and \(X_{n+1}\) be independent. Independence would be a different statement: it would require knowing \(X_n\) not to change the distribution of \(X_{n+1}\) at all.
A Criterion for Independence of Two States
Proof. Suppose first that \(X_n\) and \(X_{n+1}\) are independent. For any \(i\) with \(\mathbb P(X_n=i)>0\) and any \(j\in S\), independence gives $$ \mathbb P(X_{n+1}=j\mid X_n=i) = \frac{\mathbb P(X_n=i,X_{n+1}=j)}{\mathbb P(X_n=i)} = \frac{\mathbb P(X_n=i)\mathbb P(X_{n+1}=j)}{\mathbb P(X_n=i)} = \mathbb P(X_{n+1}=j). $$ Conversely, suppose the conditional distribution equals the marginal distribution for every such \(i\). Then for each \(i\) with positive probability and each \(j\), $$ \mathbb P(X_n=i,X_{n+1}=j) = \mathbb P(X_n=i)\mathbb P(X_{n+1}=j\mid X_n=i) = \mathbb P(X_n=i)\mathbb P(X_{n+1}=j). $$ If \(\mathbb P(X_n=i)=0\), both the joint probability and the product on the right are zero. Thus the factorization holds for all \(i,j\), which is independence for finite-valued random variables. \(\square\)
For a Markov chain, the conditional distribution in this proposition is also the distribution given the entire observed history. The proposition shows precisely what the Markov property does not say: it does not require that this conditional distribution equal the marginal distribution.
Worked Example: A Markov Chain with Dependent Neighbors
Let \(S=\{0,1\}\), let the initial distribution be \(\mu=(\tfrac12,\tfrac12)\), and use the transition matrix $$ P=\begin{bmatrix} \tfrac34&\tfrac14\\ \tfrac14&\tfrac34 \end{bmatrix}. $$ Each row sums to \(1\): \(\tfrac34+\tfrac14=1\) and \(\tfrac14+\tfrac34=1\). Take \((X_n)\) on a probability space with these initial and transition probabilities, and let \(\mathcal F_n=\sigma(X_0,\ldots,X_n)\). By the transition rule, given the observed history, the next state has the row of \(P\) indexed by the current state. Thus this is a Markov chain.
Compute the probability that both of the first two states are \(0\): $$ \mathbb P(X_0=0,X_1=0) = \mathbb P(X_0=0)\mathbb P(X_1=0\mid X_0=0) = \tfrac12\cdot\tfrac34 = \tfrac38. $$ The marginal probability of \(X_1=0\) is $$ \mathbb P(X_1=0) = \tfrac12\cdot\tfrac34+\tfrac12\cdot\tfrac14 = \tfrac38+\tfrac18 = \tfrac12. $$ If \(X_0\) and \(X_1\) were independent, the probability that both equal \(0\) would be \(\tfrac12\cdot\tfrac12=\tfrac14\), not \(\tfrac38\). Therefore they are dependent. In this example, knowing \(X_0=0\) changes the probability that \(X_1=0\) from \(\tfrac12\) to \(\tfrac34\), even though knowing the full history gives no further information once \(X_0\) is known.
Check: \(\mathbb P(X_0=0,X_1=0)=\tfrac38\), while the product of the marginals is \(\tfrac12\cdot\tfrac12=\tfrac14\). Since \(\tfrac38\ne\tfrac14\), the dependence test agrees with the calculation.
Dependence Can Persist Across More Than One Step
The Markov property also does not say that a state becomes independent of the distant past after one or more steps. It says that the next state is conditionally independent of the earlier history given the current state. The current state can still transmit information from that history. The same two-state chain makes this visible at lag two.
Worked Example: Dependence Between \(X_0\) and \(X_2\)
Use the chain from the previous example, with \(\mu=(\tfrac12,\tfrac12)\) and $$ P=\begin{bmatrix} \tfrac34&\tfrac14\\ \tfrac14&\tfrac34 \end{bmatrix}. $$ The rows sum to \(1\), as \(\tfrac34+\tfrac14=1\) in each row. To find the two-step probabilities, sum over the possible middle state. Starting from \(0\), the probability of being at \(0\) two steps later is $$ \mathbb P(X_2=0\mid X_0=0) = \tfrac34\cdot\tfrac34+\tfrac14\cdot\tfrac14 = \tfrac9{16}+\tfrac1{16} = \tfrac58. $$ Starting from \(1\), the probability of being at \(0\) two steps later is $$ \mathbb P(X_2=0\mid X_0=1) = \tfrac14\cdot\tfrac34+\tfrac34\cdot\tfrac14 = \tfrac3{16}+\tfrac3{16} = \tfrac38. $$ Thus the two-step transition probabilities are represented by $$ P^2= \begin{bmatrix} \tfrac58&\tfrac38\\ \tfrac38&\tfrac58 \end{bmatrix}. $$ Each row again sums to \(1\): \(\tfrac58+\tfrac38=1\). In particular, $$ \mathbb P(X_0=X_2) = \tfrac12\cdot\tfrac58+\tfrac12\cdot\tfrac58 = \tfrac5{16}+\tfrac5{16} = \tfrac58. $$ The marginal distribution of \(X_2\) is uniform, since $$ \mathbb P(X_2=0) = \tfrac12\cdot\tfrac58+\tfrac12\cdot\tfrac38 = \tfrac5{16}+\tfrac3{16} = \tfrac12, $$ and consequently \(\mathbb P(X_2=1)=\tfrac12\). If \(X_0\) and \(X_2\) were independent with these marginals, equality of the two states would have probability \(\tfrac12\cdot\tfrac12+\tfrac12\cdot\tfrac12=\tfrac12\). The actual probability is \(\tfrac58\), so \(X_0\) and \(X_2\) are dependent.
This does not contradict the Markov property. Given \(X_1=0\), the probability that \(X_2=0\) is \(\tfrac34\), regardless of whether the earlier history includes \(X_0=0\) or \(X_0=1\). The dependence between \(X_0\) and \(X_2\) can remain because \(X_0\) is associated with \(X_1\), and \(X_1\) affects the distribution of \(X_2\).
Check: The two ways to have \(X_2=X_0\) are \(X_0=X_2=0\) and \(X_0=X_2=1\). Each has probability \(\tfrac12\cdot\tfrac58=\tfrac5{16}\), so their sum is \(\tfrac{10}{16}=\tfrac58\), matching the calculation above.
Conditional and Unconditional Dependence
A useful way to organize this distinction is to separate dependence remaining after conditioning from dependence explained by the conditioning variable. For square-integrable random variables \(U,V\) and a finite-valued random variable \(Z\), define $$ \operatorname{Cov}(U,V\mid Z) = \mathbb E\big[(U-\mathbb E[U\mid Z])(V-\mathbb E[V\mid Z])\mid Z\big]. $$
Proof. Write \(U=(U-\mathbb E[U\mid Z])+\mathbb E[U\mid Z]\) and \(V=(V-\mathbb E[V\mid Z])+\mathbb E[V\mid Z]\). Expand the covariance using these sums. The covariance of the two residual terms is \(\mathbb E[\operatorname{Cov}(U,V\mid Z)]\), by the definition of conditional covariance and averaging over \(Z\). Each cross term has expectation zero: for example, $$ \mathbb E[(U-\mathbb E[U\mid Z])(\mathbb E[V\mid Z]-\mathbb E[V])] = \mathbb E\!\left[(\mathbb E[V\mid Z]-\mathbb E[V])\, \mathbb E[U-\mathbb E[U\mid Z]\mid Z]\right] = 0. $$ The other cross term vanishes by the same conditional-expectation calculation with \(U\) and \(V\) interchanged. The covariance of the two conditional means is the remaining term. Adding the terms gives the stated identity. \(\square\)
For example, in the first two-state calculation, take \(U=\mathbf 1_{\{X_0=0\}}\), \(V=\mathbf 1_{\{X_1=0\}}\), and \(Z=X_0\). Given \(X_0\), \(U\) is fixed, so \(\operatorname{Cov}(U,V\mid X_0)=0\). The dependence is instead reflected in the variation of the conditional mean of \(V\): it is \(\tfrac34\) when \(X_0=0\) and \(\tfrac14\) when \(X_0=1\). Directly, the covariance is $$ \operatorname{Cov}(U,V) = \mathbb E[UV]-\mathbb E[U]\mathbb E[V] = \tfrac38-\tfrac12\cdot\tfrac12 = \tfrac18. $$ So conditioning can remove the uncertainty about the past that is relevant for prediction, while unconditional dependence remains.
Independence Is Possible, but It Is an Extra Property
Worked Example: An Independent Sequence Is Also Markov
Let \(S=\{0,1\}\), and let \((X_n)_{n\ge0}\) be independent random variables with \(\mathbb P(X_n=0)=\tfrac23\) and \(\mathbb P(X_n=1)=\tfrac13\) for every \(n\). This defines a process on a probability space with its natural filtration \(\mathcal F_n=\sigma(X_0,\ldots,X_n)\). Its initial distribution is \(\mu=(\tfrac23,\tfrac13)\), and its transition matrix is $$ P=\begin{bmatrix} \tfrac23&\tfrac13\\ \tfrac23&\tfrac13 \end{bmatrix}. $$ Both rows sum to \(1\), since \(\tfrac23+\tfrac13=1\). Independence means that, for either current state with positive probability, the conditional distribution of \(X_{n+1}\) is \((\tfrac23,\tfrac13)\). In particular, the conditional distribution given the whole history is that same distribution, so the process has the Markov property.
For a numerical check, the probability that \(X_0=1\) and \(X_1=1\) is $$ \mathbb P(X_0=1,X_1=1) = \tfrac13\cdot\tfrac13 = \tfrac19, $$ which equals the product of the marginals, \(\tfrac13\cdot\tfrac13=\tfrac19\). More generally, for any finite sequence \(x_0,\ldots,x_m\) of states, independence gives $$ \mathbb P(X_0=x_0,\ldots,X_m=x_m) = \prod_{r=0}^{m}\mathbb P(X_r=x_r). $$ Thus independence can occur in a Markov chain, but it is an additional feature of this example, not a consequence of the Markov property.
Check: The row indexed by either state gives probability \(\tfrac13\) of the next state being \(1\), which equals its marginal probability. The adjacent-state independence criterion therefore holds.
A Common Misreading
Common mistake: “The chain is Markov, so \(X_0\) and \(X_1\) are independent.” Applying that claim to the first example would give $$ \mathbb P(X_0=0,X_1=0) \stackrel{\text{wrong}}{=} \mathbb P(X_0=0)\mathbb P(X_1=0) = \tfrac12\cdot\tfrac12 = \tfrac14. $$ The correct joint probability uses the conditional transition probability: $$ \mathbb P(X_0=0,X_1=0) = \mathbb P(X_0=0)\mathbb P(X_1=0\mid X_0=0) = \tfrac12\cdot\tfrac34 = \tfrac38. $$ The error is replacing a conditional probability by a marginal probability without establishing independence. The Markov property justifies conditioning on the current state instead of the full history; it does not justify dropping the conditioning altogether.
The distinction is useful whenever interpreting a transition model. A model can have short conditional memory while retaining strong temporal dependence in its sample paths. Predicting the next step requires the current state, and predictions at later times may still reflect earlier states through the intervening states. To claim independence, check the factorization of joint probabilities or use the conditional-distribution criterion above.
Check Your Understanding
For each question, distinguish carefully between conditioning on the current state and asserting independence.
- In the first example, calculate \(\mathbb P(X_1=1\mid X_0=0)\). What is \(\mathbb P(X_1=1)\), and what do the two values imply?
- For the first example, compute \(\mathbb P(X_0=1,X_1=1)\) and compare it with the product of the two marginal probabilities.
- In the lag-two example, why does dependence between \(X_0\) and \(X_2\) not violate the Markov property?
- State the conditional-distribution criterion for independence of two finite-valued random variables, including what to do with states of probability zero.
- For the independent-sequence example, verify that the probability of the path \((0,1,1)\) equals the product of its three marginal probabilities.