Designing a State That Makes the Process Markov

What Makes a State Description Useful?

A state is useful when it retains the information needed to describe the next step. A detailed description may be cumbersome, while a short summary may discard information that affects what happens next. The test is not whether a proposed label sounds like a state; it is whether the conditional distribution of the next label is determined by the current one.

Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, and let \((Z_n)_{n\ge0}\) be a process with finite state space \(S\). Its natural filtration is \(\mathcal{F}_n^Z=\sigma(Z_0,\ldots,Z_n)\), the information in its history through time \(n\). The process is Markov if, for every \(j\in S\), the conditional probability of \(Z_{n+1}=j\) given \(\mathcal{F}_n^Z\) depends only on \(Z_n\), up to events of probability zero. The next-step probabilities may depend on \(n\); if they do not, the chain is time-homogeneous.

Definition: A proposed state description passes the next-step test if, whenever two positive-probability histories through time \(n\) end in the same state \(i\), they give the same conditional distribution for \(Z_{n+1}\). It defines a time-homogeneous Markov chain if these distributions also do not depend on \(n\). Histories of probability zero impose no condition, because conditioning on such an event is not defined by the usual conditional-probability ratio.

For example, if histories \((i_0,\ldots,i_n)\) and \((i'_0,\ldots,i'_n)\) both have positive probability and \(i_n=i'_n=i\), compare the probabilities they assign to every possible next state \(j\). If even one probability differs, the proposed process is not Markov. If they agree for every \(j\), the common probabilities form a row of a transition matrix when they are also independent of time.

A Precise Test for a Finite State Description

Theorem (History test): A finite-state process \((Z_n)\) is Markov if and only if, for each \(n\), there are probabilities \(q_n(i,j)\) such that for every history \((i_0,\ldots,i_n)\) of positive probability, \(\mathbb{P}(Z_{n+1}=j\mid Z_0=i_0,\ldots,Z_n=i_n)=q_n(i_n,j)\) for all \(j\in S\). The process is time-homogeneous if these probabilities can be chosen independent of \(n\) on all states that occur with positive probability at the relevant times.

Proof. Suppose first that the process is Markov. By definition, for each \(j\), the conditional probability of \(Z_{n+1}=j\) given \(\mathcal{F}_n^Z\) is a function of \(Z_n\), almost surely. On any positive-probability history ending at \(i\), \(Z_n=i\), so the conditional probability has the same value for every such history. Call it \(q_n(i,j)\). Conversely, suppose the stated history condition holds. The positive-probability histories through time \(n\) are the atoms of the finite information \(\mathcal{F}_n^Z\). On each such atom ending at \(i\), the conditional probability of \(Z_{n+1}=j\) is \(q_n(i,j)\). Therefore the conditional probability given all of \(\mathcal{F}_n^Z\) equals \(q_n(Z_n,j)\) almost surely. This is the Markov property. If the same values can be used at every time, the next-step law depends only on the current state and is time-homogeneous. States or times that never occur do not have their transition probabilities determined by this condition. \(\square\)

The theorem turns state design into a concrete comparison: take histories that end at the same proposed state and ask whether they agree about the next step. For a time-homogeneous chain, the common values \(p_{ij}\) must be nonnegative and sum to one over \(j\) for each \(i\); the resulting matrix \(P=(p_{ij})\) is row-stochastic.

When a State-Dependent Update Works

Proposition (Fresh-randomness construction): Let \(S\) and \(E\) be finite sets. Suppose \(Z_n\in S\), \(U_{n+1}\in E\), and \(Z_{n+1}=F(Z_n,U_{n+1})\) for a fixed function \(F:S\times E\to S\). If \(U_{n+1}\) is independent of \(\mathcal{F}_n=\sigma(Z_0,U_1,\ldots,U_n)\) and has the same distribution at every time, then \((Z_n)\) is a time-homogeneous Markov chain with \(p_{ij}=\sum_{u\in E}\mathbb{P}(U_{n+1}=u)\mathbf{1}_{\{F(i,u)=j\}}\).

Proof. Fix a history through time \(n\) with positive probability and ending state \(i\). On that history, \(Z_n=i\). For each \(u\in E\), the event \(Z_{n+1}=j\) occurs when \(F(i,u)=j\). Independence of \(U_{n+1}\) from \(\mathcal{F}_n\) means its conditional probability on the history remains \(\mathbb{P}(U_{n+1}=u)\). Summing over the disjoint values of \(u\) that produce \(j\) gives the displayed formula. It depends on \(i\), not on earlier states, so the process is Markov. The distribution of \(U_{n+1}\) and the function \(F\) do not change with \(n\), so the transition probabilities are time-homogeneous. For fixed \(i\), each \(u\) produces exactly one next state; hence \(\sum_{j\in S}p_{ij}=\sum_{u\in E}\mathbb{P}(U_{n+1}=u)=1\). \(\square\)

Worked Example: A Board Position as the State

A token occupies one of three locations, \(A,B,C\). From \(A\) it always moves to \(B\); from \(C\) it always moves to \(B\); and from \(B\) it moves to \(A\) or \(C\) with equal probability. Each visit to \(B\) uses a fresh fair coin. Take the state to be the token's current location, and order the states as \(A,B,C\).

The update uses only the current location and, at \(B\), the fresh coin. Thus the state-dependent update proposition applies. The transition matrix is

P= \begin{bmatrix} 0&1&0\\ \tfrac12&0&\tfrac12\\ 0&1&0 \end{bmatrix}.

Row check: the row sums are \(0+1+0=1\), \(\tfrac12+0+\tfrac12=1\), and \(0+1+0=1\). Given any history ending at \(A\), the next state is \(B\) with probability \(1\); given any history ending at \(B\), the next state is \(A\) or \(C\) with probability \(\tfrac12\) each; and given any history ending at \(C\), the next state is \(B\) with probability \(1\). Earlier locations do not change these conditional probabilities.

As a numerical check, if \(Z_0=A\), then \(Z_1=B\) with probability \(1\). The next step gives \(\mathbb{P}(Z_2=A\mid Z_0=A)=\tfrac12\), \(\mathbb{P}(Z_2=C\mid Z_0=A)=\tfrac12\), and \(\mathbb{P}(Z_2=B\mid Z_0=A)=0\). These probabilities sum to \(1\), as required.

Worked Example: The Full Configuration of Two Bits

Let the state be the pair \(Z_n=(A_n,B_n)\in\{0,1\}^2\). At each step, the first bit toggles with probability \(\tfrac12\), and the second toggles with probability \(\tfrac14\); the two decisions are independent, fresh at every step, and independent of the past. A toggle changes \(0\) to \(1\) or \(1\) to \(0\). Order the states as \(00,10,01,11\).

The full pair determines how the two toggle decisions produce the next pair. Applying the proposition, the probability of each next configuration is the product of the two bit-update probabilities. For instance, from \(10\), reaching \(00\) requires toggling the first bit and keeping the second fixed, with probability \(\tfrac12\cdot\tfrac34=\tfrac38\). The full transition matrix is

P= \begin{bmatrix} \tfrac38&\tfrac38&\tfrac18&\tfrac18\\ \tfrac38&\tfrac38&\tfrac18&\tfrac18\\ \tfrac18&\tfrac18&\tfrac38&\tfrac38\\ \tfrac18&\tfrac18&\tfrac38&\tfrac38 \end{bmatrix}.

Row check: the first and second rows each sum to \(\tfrac38+\tfrac38+\tfrac18+\tfrac18=1\); the third and fourth each sum to \(\tfrac18+\tfrac18+\tfrac38+\tfrac38=1\). For a second entry check, from \(01\) to \(11\) the first bit must toggle and the second must stay fixed, giving \(\tfrac12\cdot\tfrac34=\tfrac38\), as shown. Because fresh toggle decisions are independent of the past, any two histories ending in the same pair have the same next-state probabilities.

When a Coarse Label Loses Information

Worked Example: Two Different Histories, One Observed State

Consider a Markov chain \(Y_n\) on \(S=\{a,b,c,d\}\), ordered as written, with transition matrix

P= \begin{bmatrix} \tfrac12&0&\tfrac12&0\\ 0&\tfrac34&\tfrac14&0\\ 1&0&0&0\\ 0&1&0&0 \end{bmatrix}.

The row sums are \(\tfrac12+0+\tfrac12+0=1\), \(0+\tfrac34+\tfrac14+0=1\), \(1+0+0+0=1\), and \(0+1+0+0=1\). Start with \(\mathbb{P}(Y_0=c)=\mathbb{P}(Y_0=d)=\tfrac12\). Now report only \(Z_n\), where \(Z_n=0\) if \(Y_n\in\{a,b\}\), \(Z_n=1\) if \(Y_n=c\), and \(Z_n=2\) if \(Y_n=d\).

The history \((Z_0,Z_1)=(1,0)\) has probability \(\tfrac12\): it means \(Y_0=c\), followed by \(Y_1=a\) with probability \(1\). Thus, conditional on this history, the probability that \(Z_2=1\) is the probability of moving from \(a\) to \(c\), namely \(\tfrac12\). The distinct history \((Z_0,Z_1)=(2,0)\) also has probability \(\tfrac12\): it means \(Y_0=d\), followed by \(Y_1=b\) with probability \(1\). Given this history, the probability that \(Z_2=1\) is the probability of moving from \(b\) to \(c\), namely \(\tfrac14\).

Both histories end in the same reported state \(Z_1=0\), but their conditional probabilities for \(Z_2=1\) are different: \(\tfrac12\ne\tfrac14\). The history test therefore shows that \((Z_n)\) is not Markov. The problem is not that the transition probabilities of \(Y_n\) are unknown; it is that the reported label combines states \(a\) and \(b\), whose next-step distributions differ.

A Common Averaging Error

In the preceding example, one might calculate \(\mathbb{P}(Z_2=1\mid Z_1=0)=\tfrac38\) and treat it as the transition probability from \(0\) to \(1\). That number is correct for this particular conditioning, but it does not establish the Markov property. Given \(Z_1=0\), the two histories \((1,0)\) and \((2,0)\) have equal probability, so averaging their conditional probabilities gives \(\tfrac12\cdot\tfrac12+\tfrac12\cdot\tfrac14=\tfrac38\). Yet conditioning on either history separately gives \(\tfrac12\) or \(\tfrac14\). A Markov transition probability must work after every positive-probability history, not only after histories have been averaged together.

When designing a state description, use this practical sequence:

Specify exactly what information the proposed state records.
List positive-probability histories that end in the same proposed state.
For each such history, find the conditional distribution of the next state.
If the distributions differ, the proposed description fails the Markov test. If they agree, check whether the common law also depends on time before calling the chain time-homogeneous.
For a transition matrix, check every row sums to \(1\).

The key question is predictive, not descriptive: does the current state determine the next-step law? A state can be a physical configuration, a location, or a label assigned to a more detailed process. Its name or simplicity does not settle the question; comparison of conditional distributions does.

Check Your Understanding

For each question, compare the next-step laws for histories that share the same current state.

A finite process has two positive-probability histories ending at state \(i\). For one history, the conditional probabilities of the next states \(a,b\) are \((\tfrac23,\tfrac13)\); for the other, they are \((\tfrac12,\tfrac12)\). Does the process pass the Markov test?
In the board-position example, what is the probability of moving to \(C\) next, given any history ending at \(B\)? Why does it not depend on earlier locations?
In the two-bit example, calculate the probability of moving from \(11\) to \(01\), and check it against the corresponding matrix entry.
In the coarse-label example, why does the value \(\tfrac38\) for \(\mathbb{P}(Z_2=1\mid Z_1=0)\) not make the observed process Markov?
What additional check is needed to conclude that a Markov process is time-homogeneous?