Inverse-Transform Sampling for Categorical Transitions

From a Transition Row to a Uniform Draw

A row of a transition matrix specifies the probabilities of the next state, conditional on the current state. In simulation, one convenient way to realize those probabilities is to divide the unit interval into pieces whose lengths match the entries of the row. A uniform random variable falls in each piece with probability equal to its length, so the selected state has the desired distribution. The endpoint convention matters: it makes the rule defined for every possible input, even though individual endpoints have probability zero.

Let \((X_n)_{n\ge0}\) be a discrete-time process on a finite state space \(S=\{s_1,\ldots,s_m\}\), with the states listed in a fixed order. Its transition matrix is \(P=(p_{ij})\), where \(p_{ij}\) is the probability of moving from \(s_i\) to \(s_j\). Each entry is nonnegative and each row sums to one. For now, fix a row \(i\); write its entries in the chosen order as \(p_{i1},\ldots,p_{im}\). The construction below applies separately to every row.

Because the row sums to one, at least one entry is positive, so \(k_i\) exists. Also \(c_{i,k_i}=1\): entries after \(k_i\) are zero, and the entire row sums to one. Thus the listed intervals cover \([0,1]\) without overlap. A zero-probability entry before \(k_i\) gives an empty interval. Zero-probability entries after \(k_i\) receive no interval, including when the input is \(u=1\). The last positive entry is assigned the endpoint \(1\) so that every \(u\in[0,1]\) has exactly one selected state.

Why the Interval Rule Gives the Right Probabilities

Proof. Fix an index \(r\). If \(r<k_i\), the set of inputs selecting \(s_r\) is the half-open interval \([c_{i,r-1},c_{ir})\). Its length is \(c_{ir}-c_{i,r-1}=p_{ir}\). A uniform random variable assigns an interval probability equal to its length, so the selection probability is \(p_{ir}\). This also covers \(p_{ir}=0\), since then the interval is empty. If \(r=k_i\), the set of inputs selecting \(s_r\) is \([c_{i,k_i-1},1]\). Its length is \(1-c_{i,k_i-1}=p_{i,k_i}\), because \(c_{i,k_i}=1\). Its probability is therefore \(p_{i,k_i}\). If \(r>k_i\), then \(p_{ir}=0\) by the definition of \(k_i\), and the rule never selects \(s_r\). These cases account for every index, proving the claim. \(\square\)

The interval endpoint choices are a way to make a single-valued rule, not an additional probabilistic assumption. Changing which state receives a shared endpoint does not change the selection probabilities when \(U\) is uniform, because a finite set of endpoints has probability zero. But a rule used in a definition or a computer program still needs to say what happens at those endpoints.

Using a Fresh Uniform at Each Transition

The row rule becomes a Markov-chain construction by applying it to whichever row corresponds to the current state. Let \((\Omega,\mathcal F,\mathbb P)\) be a probability space carrying independent random variables \(U_1,U_2,\ldots\), each uniform on \([0,1]\). Choose \(X_0\) with initial distribution \(\mu\), independently of these uniforms. At step \(n+1\), use \(U_{n+1}\) in the row belonging to \(X_n\) to define \(X_{n+1}\).

Proof. Each \(X_n\) is determined by \(X_0,U_1,\ldots,U_n\), so it is measurable with respect to \(\mathcal F_n\). The next draw \(U_{n+1}\) is independent of \(\mathcal F_n\) and uniform on \([0,1]\). On \(\{X_n=s_i\}\), the rule selecting \(X_{n+1}\) is exactly the inverse-transform rule for row \(i\). By the categorical inverse-transform proposition, a uniform input selects \(s_j\) with probability \(p_{ij}\). Independence of \(U_{n+1}\) from \(\mathcal F_n\) therefore gives \(\mathbb P(X_{n+1}=s_j\mid\mathcal F_n)=p_{ij}\) on that event. Since this conditional probability depends on the past only through \(X_n\), the process has the Markov property, and since the same matrix \(P\) is used at every step, its transition law is time-homogeneous. \(\square\)

The filtration records the information available through the current step. It is important that the next uniform is independent of that information; without this assumption, the row intervals alone would not guarantee the required conditional transition probabilities.

Zero Probabilities and the Endpoint One

Zero-probability entries require special care only because of endpoint conventions. If \(p_{ir}=0\) and \(r<k_i\), then \(c_{ir}=c_{i,r-1}\), so the assigned half-open interval \([c_{i,r-1},c_{ir})\) is empty. If \(r>k_i\), the state is not assigned an interval at all. In particular, if the final listed entry \(p_{im}\) is zero, the rule does not automatically assign \(u=1\) to that state: the endpoint belongs to the last positive-probability state instead.

Why This Construction Is Useful

The inverse-transform rule gives a direct simulation procedure: store the cumulative probabilities for each row, draw an independent uniform variable at every step, and find the interval containing it. It also provides a concrete way to verify the interpretation of a row: the probability of landing in each interval is its length, which is the corresponding transition probability. For a finite state space, only finitely many comparisons are needed at each transition.

Several distinctions are worth keeping in view:

• The row used at step \(n+1\) is determined by the current state \(X_n\); the interval rule does not choose a row independently of the chain.
• A fresh independent uniform is used for each transition. The proof of the Markov transition law uses independence from the information already observed.
• The states must be assigned a fixed order so that each row has an unambiguous sequence of cumulative sums.
• When cumulative sums are equal because of zero entries, the endpoint convention decides which state receives a shared boundary; it does not give a zero-probability state positive probability.