Expected Visits and Return Probabilities

Expected Visits as a Sum of Probabilities

For a Markov chain, the number of visits to a state is random: a path may return many times, or may leave and never come back. To find its expectation, count visits one time point at a time. The indicator of being at the state at time $n$ has expectation equal to the probability of being there at time $n$. Summing these probabilities gives the expected count, and the sum is allowed to be infinite.

Let $(X_n)_{n\ge0}$ be a time-homogeneous 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)$, and its $n$-step transition probabilities are $p_{ij}^{(n)}=\mathbb{P}_i(X_n=j)$, with $P^{(0)}=I$. The initial distribution is written as a row vector. When the chain starts at $i$, write $\mathbb{P}_i$ and $\mathbb{E}_i$. Use the natural filtration $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$; no conditioning on this filtration is needed for the visit-count identity below.

Definition: For a state $i$, the total number of visits to $i$ is $V_i=\sum_{n=0}^{\infty}\mathbf{1}_{\{X_n=i\}}$. When $X_0=i$, the number of future returns, excluding the visit at time $0$, is $V_i^+=\sum_{n=1}^{\infty}\mathbf{1}_{\{X_n=i\}}$. Both counts take values in the nonnegative integers together with $+\infty$.

There is an important distinction between a return at time $n$ and a first return at time $n$. The probability $p_{ii}^{(n)}$ is the probability that the chain is at $i$ at time $n$, whether or not it visited $i$ at an earlier positive time. By contrast, the first return time is $T_i^+=\inf\{n\ge1:X_n=i\}$. The expected count uses the probabilities $p_{ii}^{(n)}$, not just the probabilities of first return at each time.

Theorem (Expected visits and $n$-step return probabilities): For a chain started at $i$, the expected total number of visits to $i$, allowing $+\infty$, is $$ \mathbb{E}_i[V_i]=\sum_{n=0}^{\infty}p_{ii}^{(n)} =1+\sum_{n=1}^{\infty}p_{ii}^{(n)}. $$ The expected number of future returns is $$ \mathbb{E}_i[V_i^+]=\sum_{n=1}^{\infty}p_{ii}^{(n)}. $$ Each equality is an equality of extended nonnegative numbers, so it remains valid when the series diverges.

Proof. For each integer $N\ge0$, define $V_{i,N}=\sum_{n=0}^{N}\mathbf{1}_{\{X_n=i\}}$. Linearity of expectation for this finite sum gives $\mathbb{E}_i[V_{i,N}]=\sum_{n=0}^{N}\mathbb{P}_i(X_n=i)=\sum_{n=0}^{N}p_{ii}^{(n)}$. As $N$ increases, $V_{i,N}$ increases pointwise to $V_i$. The monotone convergence theorem for nonnegative random variables therefore gives $\mathbb{E}_i[V_i]=\lim_{N\to\infty}\mathbb{E}_i[V_{i,N}]=\sum_{n=0}^{\infty}p_{ii}^{(n)}$, with the limit permitted to be $+\infty$. This use of the monotone convergence theorem is the standard measure-theoretic result; its proof is beyond this tutorial. Since $X_0=i$ under $\mathbb{P}_i$, $p_{ii}^{(0)}=1$, which yields the displayed split into time $0$ and future times. Applying the same finite-sum argument to $\sum_{n=1}^{N}\mathbf{1}_{\{X_n=i\}}$, then taking the increasing limit, gives the formula for $V_i^+$. $\square$

The proof does not require the chain to be irreducible, recurrent, or aperiodic. It uses only the meaning of the visit count, finite-sum linearity of expectation, and monotone convergence. The theorem also does not assert that the chain returns with probability one: it computes an expected count from the probabilities of occupancy at all times.

Worked Calculations

Worked Example: A Self-Loop Followed by Absorption

Let $S=\{i,a\}$, and suppose the chain stays at $i$ with probability $\tfrac14$ and moves to the absorbing state $a$ with probability $\tfrac34$. State $a$ stays at $a$ with probability $1$. Starting at $i$, find the expected total visits to $i$ and the expected future returns.

In the order $i,a$, the transition matrix is

P=\begin{bmatrix} \tfrac14&\tfrac34\\ 0&1 \end{bmatrix}.

The first row sums to $\tfrac14+\tfrac34=1$, and the second sums to $0+1=1$. To be at $i$ at time $n$, the chain must have stayed at $i$ on each of its first $n$ transitions. Thus $p_{ii}^{(n)}=(\tfrac14)^n$, including $p_{ii}^{(0)}=1$. The expected total number of visits is

\mathbb{E}_i[V_i]=\sum_{n=0}^{\infty}\left(\tfrac14\right)^n =\frac{1}{1-\tfrac14}=\tfrac43.

The expected number of future returns excludes the initial visit, so it is $\sum_{n=1}^{\infty}(\tfrac14)^n=\tfrac14\cdot\tfrac43=\tfrac13$.

Check: The probability of at least $m$ visits, including time $0$, is $(\tfrac14)^{m-1}$ for $m\ge1$. Summing these tail probabilities gives $\sum_{m=1}^{\infty}(\tfrac14)^{m-1}=\tfrac43$, agreeing with the visit-probability series. The expected future count is therefore $\tfrac43-1=\tfrac13$.

Worked Example: Periodic Returns with Infinite Expected Visits

Consider a chain on $S=\{i,j\}$ that moves from $i$ to $j$ with probability $1$ and from $j$ to $i$ with probability $1$. Starting at $i$, compute the expected number of visits to $i$.

The transition matrix is $P=\begin{bmatrix}0&1\\1&0\end{bmatrix}$. Its first row sums to $0+1=1$, and its second row sums to $1+0=1$. The chain alternates deterministically: $X_n=i$ exactly when $n$ is even. Therefore $p_{ii}^{(n)}=1$ for even $n$, and $p_{ii}^{(n)}=0$ for odd $n$.

The partial expected count through time $2m$ is $\sum_{n=0}^{2m}p_{ii}^{(n)}=m+1$, since the even times are $0,2,\ldots,2m$, a total of $m+1$ times. As $m$ increases, $m+1$ has no finite upper bound. Hence $\mathbb{E}_i[V_i]=+\infty$, and $\mathbb{E}_i[V_i^+]=+\infty$ as well.

Check: On every sample path the chain visits $i$ at times $0,2,4,\ldots$, so $V_i=+\infty$ pathwise. This agrees with the divergent series $1+1+1+\cdots$. The example also shows why no aperiodicity assumption belongs in the expected-visits identity.

Worked Example: Returns Through a Two-Step Excursion

Let $S=\{i,j,a\}$. From $i$, the chain moves to $j$ with probability $\tfrac12$ and to $a$ with probability $\tfrac12$. From $j$, it moves to $i$ with probability $\tfrac13$ and to $a$ with probability $\tfrac23$. State $a$ is absorbing. Starting at $i$, find the expected total visits and future returns to $i$.

In the order $i,j,a$, the matrix is

P=\begin{bmatrix} 0&\tfrac12&\tfrac12\\ \tfrac13&0&\tfrac23\\ 0&0&1 \end{bmatrix}.

The row sums are $0+\tfrac12+\tfrac12=1$, $\tfrac13+0+\tfrac23=1$, and $0+0+1=1$. A return from $i$ must take two steps, following $i\to j\to i$, with probability $\tfrac12\cdot\tfrac13=\tfrac16$. Each further two-step return requires the same pair of transitions. Since there is no route from $a$ back to $i$, the only paths that are at $i$ at time $2k$ have made $k$ such two-step excursions. Consequently $p_{ii}^{(2k)}=(\tfrac16)^k$ for $k\ge0$; at odd times $p_{ii}^{(2k+1)}=0$.

Summing the nonzero terms gives

\mathbb{E}_i[V_i]=\sum_{k=0}^{\infty}\left(\tfrac16\right)^k =\frac{1}{1-\tfrac16}=\tfrac65, \qquad \mathbb{E}_i[V_i^+]=\sum_{k=1}^{\infty}\left(\tfrac16\right)^k =\tfrac16\cdot\tfrac65=\tfrac15.

Check: The initial visit contributes $1$, and the expected future returns contribute $\tfrac15$, so the total is $1+\tfrac15=\tfrac65$. Also, the probability of at least one future return is $\tfrac16$, whereas the expected number of future returns is $\tfrac15$; these differ because a path can make more than one return.

Why the Initial Visit and the Type of Probability Matter

The time-zero term is not a technical decoration. If the question asks for total visits from a chain started at $i$, then the chain is already at $i$, so the count includes one visit before any transition occurs. If the question asks for future returns, exclude that term. This distinction changes the answer by exactly $1$, even when either expectation is infinite.

A second distinction is between occupancy probabilities and first-return probabilities. In the first worked example, the probability of a first return is $\tfrac14$: the chain must take the self-loop on its first step. But the expected number of future returns is $\tfrac13$, not $\tfrac14$, because after a return the chain can return again. The series in the theorem counts the event $\{X_n=i\}$ separately at every time $n$; it does not count only the first such event.

Common mistake. In the first example, one might omit time $0$ and write $\mathbb{E}_i[V_i]=\sum_{n=1}^{\infty}(\tfrac14)^n=\tfrac13$. That computation is correct for $V_i^+$, the number of future returns, but not for total visits. The correction is to include $p_{ii}^{(0)}=1$: $\mathbb{E}_i[V_i]=1+\tfrac13=\tfrac43$.

It is also not valid to specify the numbers $p_{ii}^{(n)}$ independently without checking whether they can come from a transition matrix. For instance, if $p_{ii}=\tfrac14$, Chapman–Kolmogorov gives $p_{ii}^{(2)}=\sum_{k\in S}p_{ik}p_{ki}\ge p_{ii}p_{ii}=\tfrac1{16}$. Thus the claims $p_{ii}^{(1)}=\tfrac14$ and $p_{ii}^{(2)}=0$ cannot both hold. In the first example the realizable sequence is $p_{ii}^{(n)}=(\tfrac14)^n$, because leaving $i$ makes a return impossible.

The identity is useful whenever a problem gives or permits calculation of $n$-step transition probabilities and asks for an expected count. It also provides a direct route to detecting divergence: if the partial sums of the return probabilities grow without bound, the expected number of visits is infinite. The identity itself does not require classifying the state as recurrent or transient, and it should not be confused with a criterion based on a return-probability series; that is a separate question.

Check Your Understanding

For each question, distinguish the time-zero visit from future returns and show the relevant sum or finite partial sums.

A chain starts at $i$, stays there with probability $\tfrac13$, and otherwise moves to an absorbing state. What are the expected total visits to $i$ and the expected future returns?
In a deterministic two-state alternation, how many visits to the starting state occur by time $2m$, inclusive? What does this imply about the expected total count?
Explain why $p_{ii}^{(n)}$ is not generally the probability that the first return occurs at time $n$.
If $\sum_{n=1}^{N}p_{ii}^{(n)}$ increases without bound as $N$ increases, what can you conclude about $\mathbb{E}_i[V_i^+]$? Identify the result that justifies the conclusion.
For the three-state excursion example, verify that the first nonzero future return term is $p_{ii}^{(2)}=\tfrac16$, and state why all odd-time return terms vanish.

Expected Visits and Return Probabilities

What You'll Learn