Why Independence Produces a Markov Chain
A Markov chain predicts the next state from the current state, rather than from the full history. For an independent sequence, the next variable is independent of that history altogether. If the variables also share a common distribution, the law of the next state is the same at every time. These two facts together give a particularly simple transition matrix: every row is identical.
Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \(S\) be a finite or countable state space, and let \((X_n)_{n\ge0}\) be \(S\)-valued random variables. The natural filtration of the sequence is \(\mathcal{F}_n^X=\sigma(X_0,\ldots,X_n)\), the information available from observations through time \(n\). The sequence is a Markov chain if, for every \(n\ge0\) and \(j\in S\), the conditional probability \(\mathbb{P}(X_{n+1}=j\mid\mathcal{F}_n^X)\) is almost surely a function of \(X_n\). It is time-homogeneous if that function is given by the same transition probabilities at every time.
Proof. Fix \(n\ge0\) and \(j\in S\). Independence of the sequence means that \(X_{n+1}\) is independent of the vector \((X_0,\ldots,X_n)\), and hence independent of \(\mathcal{F}_n^X\). For every event \(A\in\mathcal{F}_n^X\), this gives \(\mathbb{E}[\mathbf{1}_A\mathbf{1}_{\{X_{n+1}=j\}}]=\mathbb{P}(A)\nu(j)\). The defining property of conditional expectation then gives \(\mathbb{E}[\mathbf{1}_{\{X_{n+1}=j\}}\mid\mathcal{F}_n^X]=\nu(j)\) almost surely: both sides have the same integral over every \(A\in\mathcal{F}_n^X\). Since \(\nu(j)=p_{X_n,j}\) for every value of \(X_n\), the conditional probability depends only on \(X_n\), proving the Markov property. The value \(p_{ij}=\nu(j)\) does not depend on \(n\), so the chain is time-homogeneous. Finally, for every \(i\in S\), \(\sum_{j\in S}p_{ij}=\sum_{j\in S}\nu(j)=1\), because \(\nu\) is a probability distribution. Thus \(P\) is row-stochastic. \(\square\)
The theorem also covers states with \(\nu(i)=0\). Conditioning directly on the event \(X_n=i\) is meaningful as an ordinary conditional probability only when \(\mathbb{P}(X_n=i)>0\). The transition matrix above is nevertheless defined for every \(i\in S\): it assigns the next-state distribution \(\nu\) to that row as well. On states the process never visits, this is a chosen, valid extension of the transition rule; it does not change any almost-sure Markov property of the sequence.
Finite-State Examples
Worked Example: Independent Biased Coin Outcomes
Let \(X_n=1\) when the \(n\)th outcome is heads and \(X_n=0\) when it is tails. Suppose the outcomes are independent, with \(\mathbb{P}(X_n=0)=\tfrac23\) and \(\mathbb{P}(X_n=1)=\tfrac13\) for every \(n\). Use state order \(0,1\).
The common distribution is \(\nu=(\tfrac23,\tfrac13)\), so the theorem gives the transition matrix \(P=\begin{bmatrix}\tfrac23&\tfrac13\\\tfrac23&\tfrac13\end{bmatrix}\). Each row sums to \(\tfrac23+\tfrac13=1\), as required. In particular, from either current state, the probability of a tail next is \(\tfrac23\), and the probability of a head next is \(\tfrac13\).
For a direct check, the probability of the three-state path \(1,0,1\), beginning at time \(0\), is \(\mathbb{P}(X_0=1,X_1=0,X_2=1)=\tfrac13\cdot\tfrac23\cdot\tfrac13=\tfrac2{27}\), by independence. Using the initial distribution and the transition probabilities gives the same result: \(\mathbb{P}(X_0=1)p_{10}p_{01}=\tfrac13\cdot\tfrac23\cdot\tfrac13=\tfrac2{27}\).
Worked Example: Three Outcomes with Unequal Probabilities
Suppose the independent variables take values in \(S=\{A,B,C\}\), with common probabilities \(\nu(A)=\tfrac12\), \(\nu(B)=\tfrac13\), and \(\nu(C)=\tfrac16\). In the state order \(A,B,C\), the transition matrix is \(P=\begin{bmatrix}\tfrac12&\tfrac13&\tfrac16\\\tfrac12&\tfrac13&\tfrac16\\\tfrac12&\tfrac13&\tfrac16\end{bmatrix}\).
For each of the three rows, the sum is \(\tfrac12+\tfrac13+\tfrac16=\tfrac36+\tfrac26+\tfrac16=1\). For example, after observing \(X_n=C\), independence still gives \(\mathbb{P}(X_{n+1}=B\mid\mathcal{F}_n^X)=\tfrac13\). The probability of the path \(A,C,B\) is \(\tfrac12\cdot\tfrac16\cdot\tfrac13=\tfrac1{36}\). The transition calculation agrees: the initial probability of \(A\) is \(\tfrac12\), the transition from \(A\) to \(C\) is \(\tfrac16\), and the transition from \(C\) to \(B\) is \(\tfrac13\), giving \(\tfrac12\cdot\tfrac16\cdot\tfrac13=\tfrac1{36}\).
Countable State Spaces and a Changing Distribution
Worked Example: Independent Geometric States
Let \(S=\{0,1,2,\ldots\}\), and suppose the \(X_n\) are independent with common distribution \(\nu(j)=2^{-(j+1)}\) for \(j\ge0\). Every row of the transition matrix has entries \(p_{ij}=2^{-(j+1)}\), independent of \(i\). The row sum is \(\sum_{j=0}^{\infty}2^{-(j+1)}=\tfrac12\sum_{j=0}^{\infty}(1/2)^j=\tfrac12\cdot 2=1\), so the rows are probability distributions.
For any \(n\), the probability that the next state is at least \(2\), conditional on the entire observed history, is \(\mathbb{P}(X_{n+1}\ge2\mid\mathcal{F}_n^X)=\sum_{j=2}^{\infty}2^{-(j+1)}=\tfrac18\sum_{r=0}^{\infty}(1/2)^r=\tfrac18\cdot2=\tfrac14\) almost surely. The unconditional probability is also \(\mathbb{P}(X_{n+1}\ge2)=\tfrac14\), as independence requires. This verifies the transition rule for a countable, rather than finite, state space.
Independence alone still gives a Markov property when the distributions change with time, but it need not give time-homogeneous transitions. More precisely, suppose the \(X_n\) are independent and \(S\)-valued, with possibly different distributions \(\nu_n(j)=\mathbb{P}(X_n=j)\). The same conditioning argument gives \(\mathbb{P}(X_{n+1}=j\mid\mathcal{F}_n^X)=\nu_{n+1}(j)\) almost surely. Thus the transition probabilities at time \(n\) can be taken to be \(p_{ij}(n)=\nu_{n+1}(j)\). They do not depend on \(i\), but may depend on \(n\).
Proof of the changing-distribution statement. Fix \(n\), \(j\), and \(A\in\mathcal{F}_n^X\). Independence gives \(\mathbb{E}[\mathbf{1}_A\mathbf{1}_{\{X_{n+1}=j\}}]=\mathbb{P}(A)\nu_{n+1}(j)\). By the defining property of conditional expectation, \(\mathbb{E}[\mathbf{1}_{\{X_{n+1}=j\}}\mid\mathcal{F}_n^X]=\nu_{n+1}(j)\) almost surely. This equals \(p_{X_n,j}(n)\) for the specified transition probabilities, proving the Markov property at time \(n\). The argument applies at every \(n\), while the formula allows the transition law to vary with \(n\). \(\square\)
Worked Example: Independent but Not Time-Homogeneous
Let \(X_0,X_1,X_2,\ldots\) be independent, take values in \(S=\{0,1\}\), and have \(\mathbb{P}(X_1=1)=\tfrac13\) and \(\mathbb{P}(X_2=1)=\tfrac14\). (The distribution of \(X_0\) can be any probability distribution on \(S\).) At time \(0\), the next-state distribution is \((\tfrac23,\tfrac13)\), so a valid transition matrix for that step is \(K_0=\begin{bmatrix}\tfrac23&\tfrac13\\\tfrac23&\tfrac13\end{bmatrix}\). At time \(1\), it is \((\tfrac34,\tfrac14)\), giving \(K_1=\begin{bmatrix}\tfrac34&\tfrac14\\\tfrac34&\tfrac14\end{bmatrix}\). Every row of \(K_0\) sums to \(\tfrac23+\tfrac13=1\), and every row of \(K_1\) sums to \(\tfrac34+\tfrac14=1\). The matrices differ, so the sequence is not time-homogeneous, even though it is independent and therefore Markov.
For a numerical check, independence gives \(\mathbb{P}(X_1=1\mid\mathcal{F}_0^X)=\tfrac13\) and \(\mathbb{P}(X_2=1\mid\mathcal{F}_1^X)=\tfrac14\) almost surely. Those conditional probabilities match the second-column entries of \(K_0\) and \(K_1\), respectively, and are not equal.
A Common Calculation Error
A transition probability is conditional on the current state; it is not the joint probability of the current and next states. In the biased-coin example, independence gives \(\mathbb{P}(X_n=0,X_{n+1}=0)=\tfrac23\cdot\tfrac23=\tfrac49\) and \(\mathbb{P}(X_n=0,X_{n+1}=1)=\tfrac23\cdot\tfrac13=\tfrac29\). Treating these joint probabilities as row entries would produce the row \((\tfrac49,\tfrac29)\), whose sum is \(\tfrac49+\tfrac29=\tfrac69=\tfrac23\), not \(1\). It is not a transition-probability row.
The correction is to condition on the current state. Since \(\mathbb{P}(X_n=0)=\tfrac23>0\), \(\mathbb{P}(X_{n+1}=0\mid X_n=0)=\frac{\mathbb{P}(X_n=0,X_{n+1}=0)}{\mathbb{P}(X_n=0)}=\frac{4/9}{2/3}=\tfrac23\), and \(\mathbb{P}(X_{n+1}=1\mid X_n=0)=\frac{2/9}{2/3}=\tfrac13\). The corrected row sums to \(\tfrac23+\tfrac13=1\), and agrees with the common distribution of the next variable.
The identical-row structure is useful because it separates two roles: the initial distribution specifies \(X_0\), while each transition row specifies the distribution of a fresh independent variable. In the common-distribution case these happen to be the same distribution, but the Markov property itself concerns the conditional law of the next state given the current history. Checking that distinction prevents confusion between independence, identical distributions, and time-homogeneity.
Check Your Understanding
For each question, identify whether the statement concerns independence, a transition probability, or time-homogeneity.
- If \(S=\{a,b\}\) and the common distribution is \(\nu(a)=\tfrac35\), \(\nu(b)=\tfrac25\), write the transition matrix and verify its row sums.
- For independent \(S\)-valued variables with distributions \(\nu_n\), what is \(\mathbb{P}(X_{n+1}=j\mid\mathcal{F}_n^X)\)?
- Why can the transition row for a state \(i\) with \(\mathbb{P}(X_n=i)=0\) still be specified in the common-distribution theorem?
- For the geometric distribution in the countable-state example, calculate \(\mathbb{P}(X_{n+1}\ge1\mid\mathcal{F}_n^X)\).
- Explain why the joint probability \(\mathbb{P}(X_n=i,X_{n+1}=j)\) is not generally the transition probability \(p_{ij}\).