Boolean Reachability From a Transition Matrix

From Transition Probabilities to Reachability

A transition matrix records more than the probabilities of individual moves: its powers also encode which states can be reached in a specified number of steps. For accessibility, the exact values often matter less than whether an entry is zero or positive. Replacing each positive entry by \(1\) turns the calculation into a finite bookkeeping problem, provided we keep track of paths of different lengths and stop only when no new states can be added.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with row-stochastic transition matrix \(P=(p_{ij})\). Thus \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for each \(i\). Write \(P^{(n)}=P^n\), with \(P^{(0)}=I\). We say \(j\) is accessible from \(i\) if \(p_{ij}^{(n)}>0\) for some integer \(n\ge0\). The choice \(n=0\) makes every state accessible from itself by a path of length zero; it does not assert that the chain returns there at a positive time.

Boolean multiplication uses “and” along a two-step route and “or” across possible intermediate states. In contrast, ordinary matrix multiplication multiplies probabilities along each route and adds over routes. Since all transition probabilities are nonnegative, a sum of route probabilities is positive exactly when at least one route has positive probability.

Proof. For \(n=0\), \(P^{(0)}=I\), so its positive entries are exactly the diagonal entries, which are also the \(1\) entries of \(B^{\odot0}=I\). Suppose the assertion holds at \(n\). Matrix multiplication gives \(p_{ij}^{(n+1)}=\sum_{k\in S}p_{ik}^{(n)}p_{kj}\). Every term is nonnegative, so this sum is positive if and only if at least one term is positive. A term is positive exactly when \(p_{ik}^{(n)}>0\) and \(p_{kj}>0\). By the induction hypothesis and the definition of \(B\), this is exactly the condition \((B^{\odot n}\odot B)_{ij}=1\). This proves the assertion at \(n+1\), and induction completes the proof. \(\square\)

The theorem gives an exact test for accessibility, but checking powers one at a time is not the safest stopping rule. A chain can move among the same states in a repeating pattern, so the support of \(P^{(n)}\) may keep changing even after every accessible state has been found. Instead, take the union of states reached at all lengths up to the current step.

Proof. First, \(R_m(i)\) contains exactly the states accessible in at most \(m\) steps. This holds for \(m=0\) by the definition of a length-zero path. If it holds at \(m\), a path of at most \(m+1\) steps either already has length at most \(m\), or ends with one positive-probability transition from a state reached in at most \(m\) steps. Those are precisely the two parts of the definition of \(R_{m+1}(i)\), proving the claim by induction.

Each set contains its predecessor. If an iteration adds a state, its size increases by at least one; since \(R_0(i)\) has size one and \(S\) has \(|S|\) states, there can be at most \(|S|-1\) such increases. If \(R_{m+1}(i)=R_m(i)\), every one-step successor of every state in \(R_m(i)\) is already in \(R_m(i)\). Inductively, a path starting in \(R_m(i)\) stays in that set at every later step. In particular, no later path from \(i\) can reach a state outside it. The first part of the proof shows every state in \(R_m(i)\) is accessible, so the set is exactly the accessible set. This proves both termination and correctness. \(\square\)

Worked Reachability Calculations

Practical Checks and a Common Mistake

The reachability computation depends only on which entries are exactly positive, not on their magnitudes. With exact fractions, the distinction between zero and positive is unambiguous. When probabilities are represented by rounded numerical values, a small computed value should not automatically be treated as a positive transition: the support matrix must come from the specified transition matrix, not from an arbitrary numerical tolerance.

Common mistake: checking only one step. For example, on \(S=\{1,2,3\}\), let

Each row sums to \(1\). Since \(p_{13}=0\), it is wrong to conclude that \(3\) is inaccessible from \(1\). The two-step probability is \(p_{13}^{(2)}=p_{12}p_{23}=1\cdot1=1\), so \(3\in R_2(1)\). The correction is to follow positive transitions repeatedly and stop only when the cumulative set does not grow.

For each starting state, the method can be summarized as follows:

The finite-state assumption is what guarantees that this cumulative search terminates after finitely many additions. It is not necessary for the exact support identity for a fixed power, but without a finite state space this finite stopping argument does not apply. Also keep the length-zero convention in mind: the identity matrix makes \(i\) accessible from itself, while a question about a positive-time return requires checking a positive-length path instead.