Random-Map Constructions of Markov Chains

From Random Functions to a Markov Chain

A transition matrix describes the probabilities of moving from each state to each other state. A random-map construction gives another way to specify the same evolution: at each step, draw a random function on the state space and apply it to the current state. The function chosen at a step determines the update for every possible starting state, even though the chain follows only the update from its current state.

Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, let \(S\) be a nonempty finite state space, and let \((F_n)_{n\ge1}\) be independent, identically distributed random maps from \(S\) to \(S\). A random map means that for each \(i\in S\), \(F_n(i)\) is an \(S\)-valued random variable, and the map \(F_n\) itself takes values among functions \(S\to S\). Let \(X_0\) be an \(S\)-valued random variable independent of all the maps. Define \(X_n=F_n(X_{n-1})\) for \(n\ge1\). The filtration used below is \(\mathcal{F}_n=\sigma(X_0,F_1,\ldots,F_n)\).

For each fixed \(i\), the events \(\{F(i)=j\}\), as \(j\) ranges over \(S\), are disjoint and have union \(\Omega\). Therefore \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\): the induced matrix is row-stochastic. The key condition for a chain construction is that each new map is independent of the past and has the same distribution at every time.

Proof. Fix \(n\ge0\) and \(j\in S\). The random variable \(X_n\) is \(\mathcal{F}_n\)-measurable, and \(F_{n+1}\) is independent of \(\mathcal{F}_n\), with the same distribution as \(F\). On the event \(\{X_n=i\}\), the event \(\{X_{n+1}=j\}\) is \(\{F_{n+1}(i)=j\}\). Thus its conditional probability given \(\mathcal{F}_n\), on that event, is \(\mathbb{P}(F(i)=j)=p_{ij}\). Since the events \(\{X_n=i\}\) partition \(\Omega\), this gives \(\mathbb{P}(X_{n+1}=j\mid\mathcal{F}_n)=p_{X_nj}\) almost surely. The right-hand side depends on the past only through \(X_n\), which is the Markov property, and it does not depend on \(n\), which is time homogeneity. Conditioning further on \(\{X_n=i\}\) gives the stated conditional probability when that event has positive probability. \(\square\)

The conditional statement given \(X_n=i\) requires positive probability for that event; the formula given \(\mathcal{F}_n\) holds almost surely and does not require every state to have positive probability at time \(n\). Notice also that the construction does not require the values \(F(i)\) and \(F(k)\) to be independent for different states \(i\) and \(k\). Their dependence is part of the distribution of the random map.

Prescribing a Transition Matrix

The construction works in reverse as well. For a finite state space, any row-stochastic matrix can be obtained from a random map. One convenient choice is to choose the image of each state independently according to its row of the matrix. This independence across states is a design choice, not a requirement of the random-map theorem.

Proof. For each \(i\in S\), choose an \(S\)-valued random variable \(Y_i\) with \(\mathbb{P}(Y_i=j)=p_{ij}\), and make the variables \((Y_i)_{i\in S}\) independent. These variables can be defined on the finite product of their categorical probability spaces. Set \(F(i)=Y_i\) for each \(i\); this defines a random function \(F:S\to S\). For every \(i,j\), \(\mathbb{P}(F(i)=j)=\mathbb{P}(Y_i=j)=p_{ij}\). Hence the induced transition matrix is \(P\). Taking independent, identically distributed copies of \(F\), independent also of \(X_0\), and applying the first theorem proves the final assertion. \(\square\)

What the Map View Adds

A transition matrix records the distribution of the next state separately for each current state. A random map records a joint update for all states at once. This can matter when comparing two chains that use the same maps but start at different states: their next states may be dependent because both are updated by the same random function. For instance, a constant map sends every starting state to the same destination, while a bijective map preserves the distinction between different starting states. Neither feature is visible in the individual rows alone.

For one chain, however, only the current state's image determines the next transition. The map construction therefore provides a realization of the chain without changing its one-step transition probabilities. Once the maps are independent and identically distributed, the theorem shows exactly why the chain has one-step memory and a transition law that does not vary with time.

Common mistake: treating map probabilities as separate transition probabilities without accounting for the map. In the two-state example, it would be wrong to say that the probability of moving from \(1\) to \(0\) is just the probability of choosing the flip map, \(\tfrac14\). From state \(1\), the constant map \(C_0\) also sends the chain to \(0\). The correct calculation is \(\mathbb{P}(F(1)=0)=\mathbb{P}(F=R)+\mathbb{P}(F=C_0)=\tfrac14+\tfrac14=\tfrac12\). Each transition probability must include every map that sends the specified current state to the specified destination.

When designing a construction, first verify that each row of the desired matrix is a probability distribution. Then specify a distribution on maps whose image at state \(i\) has that row's probabilities. Many different map distributions can induce the same matrix: the transition matrix fixes the marginal distribution of each \(F(i)\), but generally does not fix the dependence between images at distinct states.