Constructing Finite Chains from Independent Uniforms

From Transition Probabilities to Random Updates

A transition matrix describes the probabilities of moving from each state, but it does not by itself specify how to generate a sample path. A useful construction turns each row of the matrix into a partition of the unit interval. At time \(n\), the current state selects the row, and an independent uniform random variable selects a part of that row’s partition. This gives a direct way to build a chain with the desired transitions.

Let \(S=\{s_1,\ldots,s_m\}\) be a finite state space with a fixed ordering, and let \(P=(p_{ij})\) be a row-stochastic matrix: \(p_{ij}\ge 0\) and \(\sum_{j=1}^m p_{ij}=1\) for every \(i\). Work on a probability space \((\Omega,\mathcal F,\mathbb P)\). Let \(U_0,U_1,\ldots\) be independent random variables, each uniform on \([0,1]\), and let \(X_0\) be an \(S\)-valued random variable independent of all the \(U_n\), with initial distribution \(\mu\). For row \(i\), form the cumulative sums

Thus \(c_{im}=1\). To make a disjoint partition, assign the intervals \([c_{i,j-1},c_{ij})\) to states \(s_j\) for \(j<m\), and assign \([c_{i,m-1},1)\cup\{1\}\) to the last state \(s_m\). Denote the assigned set by \(A_{ij}\). The singleton \(\{1\}\) is included so the construction is defined for every possible value of a uniform variable, not just almost surely.

The convention at 1 resolves a small but important issue. Half-open intervals avoid overlap at interior cut points, and assigning 1 to the final state completes the partition of \([0,1]\). When a final transition probability is zero, the resulting assigned set is not empty: it is the singleton \(\{1\}\), whose probability is nevertheless zero.

Why the Construction Has the Required Transitions

Proof. The sets \(A_{i1},\ldots,A_{im}\) are disjoint and have union \([0,1]\), so exactly one next state is assigned for every current state and every value of \(U_n\). The random variable \(X_n\) is \(\mathcal F_n\)-measurable, while \(U_n\) is independent of \(\mathcal F_n\), because \(X_0\) and the uniforms are independent and the variables \(U_0,\ldots,U_{n-1}\) are the only uniforms in \(\mathcal F_n\). For each \(i,j\), the set \(A_{ij}\) has Lebesgue measure \(p_{ij}\): its interval part has length \(c_{ij}-c_{i,j-1}=p_{ij}\), and adding the singleton \(\{1\}\), when applicable, does not change its measure. Therefore, using the independence of \(U_n\) from \(\mathcal F_n\),

This conditional probability depends on the past only through \(X_n\), which is the Markov property, and it uses the same matrix \(P\) at every time, which makes the chain time-homogeneous. Since \(X_0\) has distribution \(\mu\), the chain has the stated initial distribution. \(\square\)

The same construction also gives the probability of any finite state path. This is useful for checking that it has the intended law, not just the intended one-step probabilities.

Proof. For \(k=1\), condition on \(\mathcal F_0=\sigma(X_0)\). On the event \(\{X_0=s_{i_0}\}\), the conditional probability of \(X_1=s_{i_1}\) is \(p_{i_0i_1}\), so the joint probability is \(\mu_{i_0}p_{i_0i_1}\). For a general \(k\), the event \(\{X_0=s_{i_0},\ldots,X_{k-1}=s_{i_{k-1}}\}\) belongs to \(\mathcal F_{k-1}\). Conditioning on \(\mathcal F_{k-1}\), the probability of the additional event \(X_k=s_{i_k}\) is \(p_{i_{k-1}i_k}\) on that path event. Thus each added step multiplies the preceding path probability by its corresponding transition probability. Starting with \(\mathbb P(X_0=s_{i_0})=\mu_{i_0}\) gives the formula. \(\square\)

In particular, the construction specifies all finite path probabilities from \(\mu\) and \(P\). Different choices on probability-zero endpoints would not change those probabilities, but a complete endpoint convention makes the recursion an unambiguous function for every input.

Worked Constructions

Endpoint Conventions and a Common Error

At a cut point \(c_{ij}\), the half-open convention assigns the point to the interval on its right, except at 1, which belongs to the final state’s assigned set. For example, in the three-state example, a uniform value of \(\tfrac12\) from state \(A\) belongs to \([\tfrac12,\tfrac56)\), so it selects \(B\), not \(A\). The choice at a single cut point does not alter transition probabilities because any specified point has uniform probability zero; it does matter for making the update rule single-valued.

Common mistake. Replacing every interval by a closed interval can make the update ambiguous. In the row for state \(A\) in the first example, the incorrect sets \([0,\tfrac12]\) and \([\tfrac12,\tfrac56]\) both contain \(\tfrac12\). One input would then prescribe two next states. Use \([0,\tfrac12)\) and \([\tfrac12,\tfrac56)\) instead, and assign 1 only to the final set. A related error is to say that a zero-length final set is always empty: when the last transition probability is zero, its interval part is \([1,1)=\varnothing\), but the endpoint convention adds \(\{1\}\). That singleton is nonempty and has probability zero.

The construction is useful for simulating a finite chain and for specifying its transitions explicitly from independent randomness. Its justification depends on two ingredients: each row partitions the unit interval into sets of the prescribed lengths, and the uniform variable used at step \(n\) is independent of the information available through time \(n\). If the uniforms were dependent on the past, the conditional transition probabilities need not equal the row entries, even if each uniform separately had a uniform distribution.