From One-Step Moves to Finite Paths
A transition matrix records the probability of moving from one state to another in a single step. But a state may be reachable even when there is no direct move to it: the chain can pass through intermediate states. Accessibility gives a precise way to describe this possibility. The length-zero case is part of the definition, so a state is accessible from itself whether or not the chain can return to it after moving.
Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Its transition matrix is \(P=(p_{ij})\), where \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\); each row sums to \(1\). Write \(P^{(n)}=P^n\), with \(P^{(0)}=I\). The Markov property and Chapman–Kolmogorov equations give \(p_{ij}^{(n)}=\mathbb{P}_i(X_n=j)\).
For a path of positive length, the probability of following its specified sequence of states, conditional on starting at \(x_0\), is the product \(\prod_{r=1}^{m}p_{x_{r-1}x_r}\). This product is positive exactly when every factor is positive. Accessibility is an existence statement: at least one such path must exist. It does not require that every route work, or that the one-step probability \(p_{ij}\) be positive.
Proof. First suppose \(m=0\). Then a length-zero path exists exactly when \(i=j\), and \(p_{ij}^{(0)}=I_{ij}\) is positive exactly in that case. Now take \(m\ge1\). The path expansion for an \(m\)-step transition probability is \(p_{ij}^{(m)}=\sum_{x_1,\ldots,x_{m-1}\in S}p_{ix_1}p_{x_1x_2}\cdots p_{x_{m-1}j}\); for \(m=1\), this is just \(p_{ij}\). Each summand is nonnegative. If a positive-probability path exists, its product is one of the summands and is positive, so the sum is positive. Conversely, a sum of nonnegative terms can be positive only if at least one term is positive. That term specifies a sequence of intermediate states whose transition factors are all positive, giving a finite path. This proves both directions. \(\square\)
The theorem separates two related tests. A direct one-step move from \(i\) to \(j\) exists exactly when \(p_{ij}>0\), which is the length-one case. Accessibility allows any finite length, including zero. Thus a positive one-step probability implies accessibility, but accessibility need not imply a positive one-step probability.
Worked Example: A Two-Step Route With No Direct Move
Consider \(S=\{1,2,3\}\) and the transition matrix below. Check its rows, then decide which states are accessible from state \(1\), paying particular attention to the difference between a direct move and a finite path.
The row sums are \(0+1+0=1\), \(0+0+1=1\), and \(0+0+1=1\), so \(P\) is row-stochastic. From state \(1\), the chain moves to \(2\) with probability \(1\), then from \(2\) to \(3\) with probability \(1\). The path \(1,2,3\) has probability \(1\cdot1=1\), while \(p_{13}=0\). Thus \(3\) is accessible from \(1\) but is not reachable in one step.
The two-step matrix confirms this calculation:
For example, \(p_{13}^{(2)}=p_{12}p_{23}=1\). Each row of \(P^{(2)}\) also sums to \(1\): in every row the entries are \(0,0,1\). State \(1\) is accessible from itself by the length-zero path, even though \(p_{11}=0\). In fact, no positive-length path returns from \(1\) to \(1\): after one step the chain is at \(2\), and after two or more steps it is at \(3\).
Path Probabilities and Multiple Routes
The probability of being at \(j\) after exactly \(m\) steps can include contributions from many different paths. The path expansion adds the products for all possible intermediate-state sequences. Therefore, when deciding accessibility, it is enough to find one positive-probability path; when computing \(p_{ij}^{(m)}\), all paths of that length must be included.
Worked Example: Adding the Probabilities of Two Paths
Let \(S=\{a,b,c,d\}\), with transition matrix
where rows and columns are ordered \(a,b,c,d\). The row sums are \(0+\tfrac12+\tfrac12+0=1\), \(0+0+\tfrac23+\tfrac13=1\), \(0+0+\tfrac34+\tfrac14=1\), and \(0+0+0+1=1\). There are two length-two paths from \(a\) to \(d\): \(a,b,d\) and \(a,c,d\). Their probabilities are, respectively, \(\tfrac12\cdot\tfrac13=\tfrac16\) and \(\tfrac12\cdot\tfrac14=\tfrac18\). Consequently,
As a matrix-product check, column \(d\) of \(P\) is \((0,\tfrac13,\tfrac14,1)^{\mathsf T}\), and row \(a\) is \((0,\tfrac12,\tfrac12,0)\). Their product is \(0\cdot0+\tfrac12\cdot\tfrac13+\tfrac12\cdot\tfrac14+0\cdot1=\tfrac7{24}\), as obtained by enumerating paths. Since \(p_{ad}=0\), the positive two-step probability also confirms that accessibility does not mean a direct transition.
A path can establish accessibility at one length even if no path of another specified length works. In particular, a positive probability at time \(m\) answers the question “can the chain be at \(j\) after exactly \(m\) steps?” Accessibility asks the broader question “is there at least one finite time at which such a path is possible?” It does not assert that the chain reaches \(j\) with probability \(1\), or that it will do so from every starting state.
Worked Example: The Same Destination at Different Times
Let \(S=\{1,2,3,4\}\), ordered as written, and take
The row sums are \(0+\tfrac13+\tfrac23+0=1\), \(0+\tfrac12+0+\tfrac12=1\), \(0+1+0+0=1\), and \(0+0+0+1=1\). We will calculate the probability of being at \(4\) after two and after three steps when starting from \(1\).
In two steps, the only path from \(1\) to \(4\) is \(1,2,4\). Its probability is \(\tfrac13\cdot\tfrac12=\tfrac16\), so \(p_{14}^{(2)}=\tfrac16\). To calculate the three-step probability, first note that after two steps the probability of being at \(2\) is \(\tfrac13\cdot\tfrac12+\tfrac23\cdot1=\tfrac16+\tfrac23=\tfrac56\). The probability of being at \(4\) after two steps remains \(\tfrac16\). From state \(2\), the probability of moving to \(4\) is \(\tfrac12\), and from state \(4\), it is \(1\). Hence
Direct enumeration checks the result. The three length-three paths from \(1\) to \(4\) are \(1,2,2,4\), \(1,2,4,4\), and \(1,3,2,4\). Their probabilities are \(\tfrac13\cdot\tfrac12\cdot\tfrac12=\tfrac1{12}\), \(\tfrac13\cdot\tfrac12\cdot1=\tfrac16\), and \(\tfrac23\cdot1\cdot\tfrac12=\tfrac13\). Their sum is \(\tfrac1{12}+\tfrac2{12}+\tfrac4{12}=\tfrac7{12}\). Both \(p_{14}^{(2)}\) and \(p_{14}^{(3)}\) are positive, so either path length establishes accessibility.
Basic Consequences of the Definition
Proof. For reflexivity, the length-zero path from \(i\) to \(i\) has no transition factors to check and is allowed by definition. For transitivity, suppose there is a positive-probability path of length \(m\) from \(i\) to \(j\) and one of length \(n\) from \(j\) to \(k\). Concatenate the two sequences at \(j\). The resulting path from \(i\) to \(k\) has length \(m+n\), and its probability is the product of the two path probabilities, which is positive. This argument also covers \(m=0\) or \(n=0\), since multiplying by the empty product \(1\) leaves the other path unchanged.
For the final equivalence, the event \(\{T_{\{j\}}<\infty\}\) is the countable union \(\bigcup_{n\ge0}\{X_n=j\}\) under \(\mathbb{P}_i\). If some \(p_{ij}^{(n)}>0\), then this union has positive probability. In the other direction, if the union has positive probability, at least one of its events must have positive probability: if every event had probability zero, countable subadditivity would give probability zero for their union. Thus \(p_{ij}^{(n)}=\mathbb{P}_i(X_n=j)>0\) for some \(n\ge0\), and the finite-path characterization gives accessibility. \(\square\)
The proposition makes the role of the zero-length path precise. Starting at \(j\), the chain has already hit \(j\) at time \(0\), so \(T_{\{j\}}=0\) under \(\mathbb{P}_j\). This fact is different from saying that a positive-length return is possible. It is also different from saying that a chain started at another state will eventually hit \(j\) with probability \(1\): accessibility requires only positive probability of hitting at some finite time.
A Common Mistake and a Reliable Test
Common mistake: In the four-state example with states \(a,b,c,d\), one might calculate \(p_{ad}^{(2)}\) using only the route \(a,b,d\), write \(p_{ad}^{(2)}=\tfrac12\cdot\tfrac13=\tfrac16\), and treat that as the full two-step probability. This omits the route \(a,c,d\). The correction is to sum over both intermediate states: \(\tfrac12\cdot\tfrac13+\tfrac12\cdot\tfrac14=\tfrac16+\tfrac18=\tfrac7{24}\). The omitted route does not change the conclusion that \(d\) is accessible from \(a\), but it does change the transition probability.
For a concrete accessibility check, ask whether there is a finite sequence starting at \(i\) and ending at \(j\) for which every consecutive transition has strictly positive probability. A zero-probability step disqualifies that particular sequence, but it does not rule out a different path. Conversely, if \(p_{ij}=0\), this rules out only the one-step route; intermediate states may still provide a positive-probability path.
Check Your Understanding
Use the definition and the path probabilities to answer each question. Treat a path as valid only when every transition along it has strictly positive probability; include paths of length zero where relevant.
- If \(p_{ij}=0\), can \(j\) still be accessible from \(i\)? State the condition that would make it so.
- Suppose \(p_{12}=\tfrac14\) and \(p_{23}=\tfrac12\). What is the probability of the specified path \(1,2,3\), and what does it imply about accessibility?
- Why is every state accessible from itself under this definition, even if its diagonal transition probability is zero?
- For a fixed \(m\ge1\), explain why \(p_{ij}^{(m)}>0\) requires at least one positive-probability path of exactly \(m\) steps.
- In the four-state example with states \(a,b,c,d\), identify both length-two paths from \(a\) to \(d\) and verify their probabilities add to \(\tfrac7{24}\).