Deterministic State Updates as Markov Chains

From an Update Rule to a Transition Matrix

A process can be random even when its update rule is not. If the initial state is random, the future path is random through that starting value; once the starting state is known, however, a deterministic rule fixes every later state. This setting gives a direct example of how a state-update mechanism can define a Markov chain.

Let \(S\) be a nonempty finite state space, let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, and let \(X_0\) be an \(S\)-valued random variable. Suppose \(f:S\to S\) is a fixed function and define the discrete-time process recursively by \(X_{n+1}=f(X_n)\) for every \(n\ge0\). The same function is used at every time. For each \(n\), use the natural filtration \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\).

This matrix is row-stochastic: for each \(i\in S\), precisely one state \(j\in S\) satisfies \(f(i)=j\), so \(\sum_{j\in S}p_{ij}=1\). The row convention matters: row \(i\) records the possible next states when the current state is \(i\). In a deterministic update, there is exactly one possible next state.

Why the Process Is Markov

The conditional probability given \(\mathcal{F}_n\) is meaningful as a conditional random variable, and the displayed equality is an almost-sure equality. To interpret a conditional probability given the event \(X_n=i\) as a ratio, that event must have positive probability. The matrix \(P\), however, is defined for every state, including states the process does not visit under its chosen initial distribution.

Proof. Fix \(n\ge0\) and \(j\in S\). The update rule gives \(\mathbf{1}_{\{X_{n+1}=j\}}=\mathbf{1}_{\{f(X_n)=j\}}\). The right-hand side is \(\mathcal{F}_n\)-measurable because \(X_n\) is \(\mathcal{F}_n\)-measurable and \(f\) is a fixed function on \(S\). The conditional expectation of an integrable, \(\mathcal{F}_n\)-measurable random variable given \(\mathcal{F}_n\) is that variable itself. Therefore, \(\mathbb{P}(X_{n+1}=j\mid\mathcal{F}_n)=\mathbb{E}[\mathbf{1}_{\{X_{n+1}=j\}}\mid\mathcal{F}_n]=\mathbf{1}_{\{f(X_n)=j\}}=p_{X_nj}\) almost surely. The conditional distribution of the next state thus depends on the observed past only through \(X_n\), which is the Markov property. Because the same \(f\), and hence the same \(P\), is used for every \(n\), the chain is time-homogeneous. \(\square\)

There is also a simple pathwise consequence. If \(X_0=i\), then \(X_1=f(i)\), \(X_2=f(f(i))\), and each subsequent state is fixed by another application of \(f\). This does not require any further random choices. It does not mean that \(X_0\) itself must be nonrandom: different initial states can still produce different paths.

Worked Examples

When Does Every State Have a Predecessor?

Every deterministic update has one outgoing transition from each state, but it need not have one incoming transition to each state. In the four-state example, both \(0\) and \(2\) have no incoming transitions, while \(1\) and \(3\) each have two. A useful distinction is whether the update map is one-to-one and onto.

Proof. For a state \(j\), the entries equal to \(1\) in column \(j\) are exactly those \(p_{ij}\) for which \(f(i)=j\). Thus the number of ones in column \(j\) is the number of states mapped to \(j\). If \(f\) is a bijection, every \(j\in S\) has exactly one preimage, so every column has exactly one \(1\). Conversely, if every column has exactly one \(1\), then every \(j\in S\) has exactly one preimage. Having at least one preimage for each \(j\) makes \(f\) onto, and having at most one preimage for each \(j\) makes \(f\) one-to-one. Therefore \(f\) is a bijection. \(\square\)

The proposition also handles the one-state case: the only map on a singleton sends its state to itself, and its sole matrix entry is \(1\). For larger finite state spaces, bijectivity is an additional feature, not part of the definition of a deterministic transition matrix.

A Common Mistake and a Practical Check

A deterministic rule does not mean that the next state is uncertain after the current state has been specified. For example, in the capped-increment rule, state \(1\) always goes to state \(2\). A mistaken row might assign probability \(\tfrac12\) to state \(1\) and \(\tfrac12\) to state \(2\), on the grounds that two destinations were considered. That row would say \(p_{11}=\tfrac12\) and \(p_{12}=\tfrac12\), contradicting \(f(1)=2\). The correct row is \((0,0,1)\): its entries are \(p_{10}=0\), \(p_{11}=0\), and \(p_{12}=1\), and its sum is \(0+0+1=1\).

Another possible source of confusion is the randomness of the initial distribution. In the toggle example, \(X_1\) is random before observing \(X_0\), because the initial state is random. But conditional on \(X_0=0\), \(X_1=1\) with probability \(1\); conditional on \(X_0=1\), \(X_1=0\) with probability \(1\). Randomness in the starting state and randomness in the transition mechanism are different things.

To model a deterministic update, first list the states in a fixed order. For each state \(i\), apply the rule once to obtain \(f(i)\), put a \(1\) in the column for \(f(i)\), and put \(0\) in every other column of that row. Finally, check every row sum. This procedure gives a transition matrix because the rule assigns exactly one next state in \(S\) to every current state.