From Returns to a Visit Count
A return probability describes whether a chain comes back to a state after leaving it. A related question is how many times the chain visits that state over its entire future. The key is to view each return as the start of another opportunity for a later return. The Markov property makes the probability of that next return the same at every visit, so the total count has a simple distribution.
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_{jk})\), with \(\sum_{k\in S}p_{jk}=1\) for each \(j\). Use the natural filtration \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). For the chain started at \(i\), write \(\mathbb{P}_i\). The return probability from \(i\) is \(r_i=\mathbb{P}_i(T_i^+<\infty)\), where \(T_i^+=\inf\{n\ge1:X_n=i\}\).
To count visits in order, set \(R_0=0\), and, whenever \(R_m<\infty\), define \(R_{m+1}=\inf\{n>R_m:X_n=i\}\). If \(R_m=\infty\), set \(R_{m+1}=\infty\); as usual, the infimum of an empty set is \(\infty\). Thus \(R_m\) is the time of the \(m\)th return after the initial visit, if that return occurs. In particular, \(V_i\ge k\) exactly when \(R_{k-1}<\infty\).
Proof. For \(m\ge0\), the event \(\{R_m=n\}\) is determined by \(X_0,\ldots,X_n\), so it belongs to \(\mathcal{F}_n\). On this event, \(X_n=i\). By the Markov property at the deterministic time \(n\), conditional on \(\mathcal{F}_n\), the probability of a future return to \(i\) is \(r_i\). Summing over the disjoint events \(\{R_m=n\}\) gives $$ \mathbb{P}_i(R_{m+1}<\infty) =\sum_{n=0}^{\infty}\mathbb{P}_i(R_m=n,\ R_{m+1}<\infty) =r_i\sum_{n=0}^{\infty}\mathbb{P}_i(R_m=n) =r_i\mathbb{P}_i(R_m<\infty). $$ Since \(R_0=0\), \(\mathbb{P}_i(R_0<\infty)=1\). Induction therefore yields \(\mathbb{P}_i(R_m<\infty)=r_i^m\). The equivalence \(V_i\ge k\) if and only if \(R_{k-1}<\infty\) proves the tail formula. For \(r_i<1\), the event \(V_i=k\) is \(\{V_i\ge k\}\setminus\{V_i\ge k+1\}\), so its probability is \(r_i^{k-1}-r_i^k=(1-r_i)r_i^{k-1}\). When \(r_i=1\), each event \(\{V_i\ge k\}\) has probability one. Their countable intersection also has probability one, and on that intersection \(V_i=\infty\). When \(r_i=0\), the first return has probability zero, so \(V_i=1\) almost surely. \(\square\)
For \(0<r_i<1\), the count is geometric on the positive integers: each visit is followed by another return with probability \(r_i\), and the count stops when a return fails. The initial visit matters: it shifts the support from \(\{0,1,2,\ldots\}\) to \(\{1,2,3,\ldots\}\). The theorem gives the entire distribution, including its tail, without requiring a separate calculation for each possible number of visits.
Worked Example: A State with a Nonzero Chance of Escape
Consider the chain on \(S=\{i,a,b\}\) with states ordered as \(i,a,b\) and transition matrix $$ P= \begin{bmatrix} \tfrac12&\tfrac12&0\\ \tfrac12&\tfrac14&\tfrac14\\ 0&0&1 \end{bmatrix}. $$ The row sums are \(\tfrac12+\tfrac12+0=1\), \(\tfrac12+\tfrac14+\tfrac14=1\), and \(0+0+1=1\).
Starting from \(a\), let \(q\) be the probability of ever reaching \(i\). From \(a\), the chain moves directly to \(i\) with probability \(\tfrac12\), stays at \(a\) with probability \(\tfrac14\), or moves to \(b\) with probability \(\tfrac14\). Since \(b\) is absorbing and is not \(i\), conditioning on the first step gives \(q=\tfrac12+\tfrac14q\). Hence \(\tfrac34q=\tfrac12\), so \(q=\tfrac23\).
Starting from \(i\), the chain returns immediately with probability \(\tfrac12\). Otherwise it moves to \(a\), from which the probability of reaching \(i\) is \(\tfrac23\). Therefore $$ r_i=\tfrac12+\tfrac12\cdot\tfrac23=\tfrac12+\tfrac13=\tfrac56. $$ The theorem gives, for every integer \(k\ge1\), $$ \mathbb{P}_i(V_i=k)=\left(1-\tfrac56\right)\left(\tfrac56\right)^{k-1} =\tfrac16\left(\tfrac56\right)^{k-1}. $$ For instance, \(\mathbb{P}_i(V_i=1)=\tfrac16\), \(\mathbb{P}_i(V_i=2)=\tfrac16\cdot\tfrac56=\tfrac5{36}\), and \(\mathbb{P}_i(V_i\ge3)=(\tfrac56)^2=\tfrac{25}{36}\).
Check: The probabilities over all finite counts sum to \(\tfrac16\sum_{k=1}^{\infty}(\tfrac56)^{k-1}=\tfrac16\cdot\frac{1}{1-\tfrac56}=\tfrac16\cdot6=1\). Thus there is no remaining probability at \(V_i=\infty\), as required when \(r_i=\tfrac56<1\).
Starting Away from the State
The count also has a direct description when the chain starts at a state \(x\ne i\). Write \(T_i=\inf\{n\ge0:X_n=i\}\) and \(h_x=\mathbb{P}_x(T_i<\infty)\). Define \(N_i=\sum_{n=0}^{\infty}\mathbf{1}_{\{X_n=i\}}\), now under \(\mathbb{P}_x\). Because \(x\ne i\), the count can be zero if the chain never reaches \(i\).
Proof. On \(\{T_i=\infty\}\), there are no visits to \(i\), so \(N_i=0\). On \(\{T_i<\infty\}\), the chain is at \(i\) at time \(T_i\), and that visit is the first visit counted by \(N_i\). Conditional on reaching \(i\) at time \(n\), the Markov property gives the same law for subsequent returns as for a chain started at \(i\). To justify conditioning at the possibly random time, split \(\{T_i<\infty\}\) into the disjoint events \(\{T_i=n\}\). Each belongs to \(\mathcal{F}_n\), and on it \(X_n=i\), so the deterministic-time Markov property applies on each event. Summing over \(n\ge1\), the conditional count after the first hit has the distribution in the theorem. Multiplying its probabilities by \(\mathbb{P}_x(T_i<\infty)=h_x\) gives the formula for \(r_i<1\). If \(r_i=1\), the theorem says that after reaching \(i\), infinitely many visits occur almost surely; thus the probability of an infinite count is \(h_x\), and the probability of no visits is \(1-h_x\). \(\square\)
Worked Example: Counting Visits from a Different Initial State
Use the chain on \(\{i,a,b\}\) displayed above, now started at \(a\). Its rows sum to \(1\): \(\tfrac12+\tfrac12+0=1\), \(\tfrac12+\tfrac14+\tfrac14=1\), and \(0+0+1=1\). To reach \(i\) from \(a\), the first-step equation is \(h_a=\tfrac12+\tfrac14h_a\); solving gives \(\tfrac34h_a=\tfrac12\) and \(h_a=\tfrac23\).
For a chain started at \(i\), the probability of a return is \(\tfrac12+\tfrac12\cdot\tfrac23=\tfrac56\), because the first step either returns directly or goes to \(a\), from which the probability of reaching \(i\) is \(\tfrac23\). Thus \(r_i=\tfrac56\). The proposition gives $$ \mathbb{P}_a(N_i=0)=1-\tfrac23=\tfrac13 $$ and, for \(k\ge1\), $$ \mathbb{P}_a(N_i=k)=\tfrac23\left(1-\tfrac56\right)\left(\tfrac56\right)^{k-1} =\tfrac19\left(\tfrac56\right)^{k-1}. $$ In particular, \(\mathbb{P}_a(N_i=1)=\tfrac19\), and \(\mathbb{P}_a(N_i=2)=\tfrac19\cdot\tfrac56=\tfrac5{54}\).
Check: The total probability of a positive finite count is \(\tfrac19\sum_{k=1}^{\infty}(\tfrac56)^{k-1}=\tfrac19\cdot6=\tfrac23\). Adding the probability of no visits gives \(\tfrac23+\tfrac13=1\). Since \(r_i=\tfrac56<1\), the probability of infinitely many visits is zero.
When Return Is Certain
Worked Example: A Deterministic Cycle
Let \(S=\{1,2,3\}\), and let the chain move deterministically from \(1\) to \(2\), from \(2\) to \(3\), and from \(3\) to \(1\). In that state order, $$ P= \begin{bmatrix} 0&1&0\\ 0&0&1\\ 1&0&0 \end{bmatrix}. $$ The row sums are \(0+1+0=1\), \(0+0+1=1\), and \(1+0+0=1\). Starting at state \(1\), the chain returns to \(1\) after three steps, then again after another three steps, and continues in this way. Thus \(r_1=1\). The theorem gives \(\mathbb{P}_1(V_1=\infty)=1\), while \(\mathbb{P}_1(V_1=k)=0\) for each finite \(k\).
Check: Along every possible path from state \(1\), the visited states repeat as \(1,2,3,1,2,3,\ldots\). There are infinitely many occurrences of \(1\), confirming the distribution. This example also shows that certain return does not require a possible return at every time step: it is enough that a return occurs eventually with probability one.
A Common Counting Error
A frequent mistake is to use the geometric distribution with support beginning at zero even though the chain starts at the state being counted. In the first example, that mistake would assign probability \(1-r_i=\tfrac16\) to \(V_i=0\). But the chain starts at \(i\), so \(X_0=i\) and \(V_i\ge1\) on every path; therefore \(\mathbb{P}_i(V_i=0)=0\). The correct value \(\tfrac16\) is \(\mathbb{P}_i(V_i=1)\): it is the chance that the initial visit is not followed by any return.
It is also important to distinguish the probability of reaching \(i\) from a different starting state from the probability of returning to \(i\) once there. The first determines whether the count is zero; the second determines the distribution of the positive count. In the second worked example, these probabilities are \(h_a=\tfrac23\) and \(r_i=\tfrac56\), respectively. Using \(r_i\) in place of \(h_a\) would incorrectly give the probability of no visits as \(\tfrac16\), rather than \(1-h_a=\tfrac13\).
The visit-count law is useful because it converts a repeated-return question into a complete probability distribution. Its three cases have distinct meanings: \(r_i=0\) gives exactly one visit when starting at \(i\); \(0<r_i<1\) gives a finite geometric count almost surely; and \(r_i=1\) gives infinitely many visits almost surely. When starting elsewhere, the chance of never reaching the state adds a zero-count outcome, while the counts conditional on reaching it follow the same return-based law.
Check Your Understanding
Use the definitions and return-count formulas to answer the following questions.
- A chain starts at \(i\) and has return probability \(r_i=\tfrac23\). Find \(\mathbb{P}_i(V_i=1)\), \(\mathbb{P}_i(V_i=3)\), and \(\mathbb{P}_i(V_i\ge4)\).
- If \(r_i=0\), what is the distribution of \(V_i\) when the chain starts at \(i\)? Explain why the initial visit must be counted.
- A chain starts at \(x\ne i\), with \(\mathbb{P}_x(T_i<\infty)=\tfrac34\) and return probability \(r_i=\tfrac12\). Find \(\mathbb{P}_x(N_i=0)\) and \(\mathbb{P}_x(N_i=2)\).
- What is the distribution of \(V_i\) if the chain starts at \(i\) and \(r_i=1\)? Why does the conclusion concern infinitely many visits rather than just one return?
- State the difference between \(h_x=\mathbb{P}_x(T_i<\infty)\) and \(r_i=\mathbb{P}_i(T_i^+<\infty)\) when \(x\ne i\).