Green Functions as Expected Visit Counts

Visits as a Potential

A random walk can spend time near a state, leave it, and perhaps return many times. A useful way to measure this behavior is to count visits rather than only ask whether a state is ever reached. The expected number of visits gives a single quantity that records both accessibility and the possibility of repeated returns.

The Green function is this expected visit count. Its values can be finite or infinite. In particular, finite state space alone does not guarantee finite values: an ordinary finite irreducible walk keeps returning, so its expected total number of visits to each state is infinite. To obtain finite counts in a finite example, it is often appropriate to stop counting when the walk is absorbed.

Definition of the Green Function

Let $(X_n)_{n\geq 0}$ be a discrete-time Markov chain on a countable state space $S$, with transition probabilities $P(x,y)=\mathbb P(X_{n+1}=y\mid X_n=x)$. Write $\mathbb P_x$ and $\mathbb E_x$ for probability and expectation when $X_0=x$. The visit count to $y$ includes time zero, so a walk started at $y$ has already made one visit.

Definition: For $x,y\in S$, the Green function is the extended nonnegative quantity $$ G(x,y)=\mathbb E_x\!\left[\sum_{n=0}^{\infty}\mathbf 1_{\{X_n=y\}}\right] =\sum_{n=0}^{\infty}\mathbb P_x(X_n=y). $$ The equality follows by applying the monotone convergence theorem to the partial sums of the nonnegative indicators.

Thus $G(x,y)$ is the expected total number of visits to $y$ when the chain starts at $x$. The sum may equal $+\infty$. The term at $n=0$ is $1$ when $x=y$ and $0$ otherwise.

For a walk killed upon leaving a set $D\subseteq S$, write $\tau_D=\inf\{n\geq 0:X_n\notin D\}$. Its killed Green function, for $x,y\in D$, counts visits before exit: $$ G_D(x,y)=\mathbb E_x\!\left[\sum_{0\leq n<\tau_D}\mathbf 1_{\{X_n=y\}}\right]. $$ This differs from the ordinary Green function: visits after leaving $D$ are not counted, even if the original chain could later return.

Return Probabilities and Visit Counts

To distinguish transient and recurrent behavior, consider a chain started at $y$. Let $T_y^+=\inf\{n\geq 1:X_n=y\}$, the first return time after time zero. The state $y$ is recurrent if $\mathbb P_y(T_y^+<\infty)=1$, and transient if $\mathbb P_y(T_y^+<\infty)<1$. These definitions concern the chance of a return; the Green function records the expected number of visits.

Theorem: Let $f_y=\mathbb P_y(T_y^+<\infty)$. Then $$ G(y,y)= \begin{cases} \dfrac{1}{1-f_y},& f_y<1,\\[6pt] +\infty,& f_y=1. \end{cases} $$ For any $x\in S$, if $T_y=\inf\{n\geq0:X_n=y\}$, then $$ G(x,y)=\mathbb P_x(T_y<\infty)\,G(y,y), $$ where if the hitting probability is zero, the Green function is zero, including when $G(y,y)=+\infty$.

Proof: Starting from $y$, let $K=\sum_{n=0}^{\infty}\mathbf 1_{\{X_n=y\}}$. For each integer $k\geq1$, the event $K\geq k$ means that the walk makes at least $k-1$ returns after its initial visit. Applying the Markov property at successive return times gives $$ \mathbb P_y(K\geq k)=f_y^{\,k-1}. $$ For a nonnegative integer-valued random variable, its expectation is the sum of its tail probabilities, with the equality also valid when the sum diverges. Therefore $$ G(y,y)=\mathbb E_y[K]=\sum_{k=1}^{\infty}f_y^{\,k-1}. $$ This geometric series equals $1/(1-f_y)$ if $f_y<1$, and diverges if $f_y=1$.

Now start from $x$. There are no visits to $y$ if $T_y=\infty$. On the event $T_y<\infty$, the chain is at $y$ at time $T_y$, and the Markov property says that the expected number of visits from that time onward is $G(y,y)$. The visit at time $T_y$ is included in this count. Taking the expectation over whether $T_y$ is finite gives the stated identity when $G(y,y)$ is finite. If $G(y,y)=+\infty$, the same conclusion follows by first counting only the first $m$ visits after hitting $y$, then letting $m$ increase; a positive probability of hitting $y$ gives infinite expected visits. If the hitting probability is zero, there are no visits. $\square$

In particular, a transient state has finite expected visits when the walk starts there. A recurrent state has infinite expected visits from itself, and also from any starting state that has positive probability of reaching it. Recurrence alone does not say that every other state can reach $y$; accessibility matters in the formula.

Worked Examples

Worked Example: Geometric Returns in an Infinite Chain

Consider the state space $\{o,e_1,e_2,\ldots\}$. From $o$, the chain moves to $e_1$. From $e_1$, it moves to $o$ with probability $r$, and to $e_2$ with probability $1-r$, where $0\leq r<1$. From each $e_n$, $n\geq2$, it moves deterministically to $e_{n+1}$.

Each time the chain is at $o$, it next visits $e_1$. It then returns to $o$ with probability $r$, beginning another such cycle, or escapes along $e_2,e_3,\ldots$ with probability $1-r$. Thus the probability of at least $k$ visits to $o$, starting from $o$, is $r^{k-1}$. Consequently, $$ G(o,o)=\sum_{k=1}^{\infty}r^{k-1}=\frac{1}{1-r}. $$ Likewise, every visit to $o$ is followed by exactly one visit to $e_1$, so $G(o,e_1)=1/(1-r)$. Escape eventually occurs with probability one, since the probability of at least $k$ returns is $r^k\to0$. After escaping, each $e_n$, $n\geq2$, is visited exactly once. Hence $G(o,e_n)=1$ for all $n\geq2$. The state $o$ is transient because its return probability is $r<1$.

Worked Example: A Finite Walk Killed at Absorption

Take transient states $a,b$ and an absorbing state $\partial$. From $a$, move to $b$ with probability $p$ and to $\partial$ with probability $1-p$. From $b$, move to $a$ with probability $q$ and to $\partial$ with probability $1-q$, where $0\leq p,q<1$. Count visits to $a,b$ only before absorption.

Starting at $a$, each return to $a$ after time zero requires the two-step path $a\to b\to a$, with probability $pq$. The probability of at least $k$ visits to $a$ is therefore $(pq)^{k-1}$, giving $$ G_D(a,a)=\sum_{k=1}^{\infty}(pq)^{k-1}=\frac{1}{1-pq}. $$ A visit to $b$ occurs on a cycle precisely when the chain leaves $a$ for $b$; summing over the possible number of completed return cycles gives $$ G_D(a,b)=p\sum_{k=0}^{\infty}(pq)^k=\frac{p}{1-pq}. $$ The same path count, now starting at $b$, yields $$ G_D(b,b)=\frac{1}{1-pq}, \qquad G_D(b,a)=\frac{q}{1-pq}. $$ For example, if $p=1/2$ and $q=1/3$, then $pq=1/6$, and the four values are $G_D(a,a)=6/5$, $G_D(a,b)=3/5$, $G_D(b,a)=2/5$, and $G_D(b,b)=6/5$. These counts are finite because each two-step cycle has probability $1/6<1$, and absorption eventually occurs.

Worked Example: A Finite Irreducible Walk with Infinite Counts

Let the walk alternate deterministically between the two states $0$ and $1$: from either state it moves to the other with probability one. Starting at $0$, the walk visits $0$ at times $0,2,4,\ldots$ and $1$ at times $1,3,5,\ldots$. Thus $$ G(0,0)=\sum_{k=0}^{\infty}1=+\infty, \qquad G(0,1)=\sum_{k=0}^{\infty}1=+\infty. $$ Starting at $1$ gives the same result for either target. The chain has only two states, but each state is visited infinitely many times. This example shows why an ordinary Green function on a finite chain need not be finite; killing or restricting the time counted changes the question.

Finite Irreducible Chains

The alternating walk is a particular case of a general fact: every finite irreducible Markov chain is recurrent. Here irreducibility means that for every pair of states $z,y$, there is a positive-probability path from $z$ to $y$.

Proposition: In a finite irreducible Markov chain, every state $y$ is recurrent, and $G(y,y)=+\infty$.

Proof: Fix a target state $y$. From each state $z$, irreducibility supplies a finite path to $y$ with positive probability. Since there are finitely many states, there are an integer $m\geq1$ and a number $\delta>0$ such that, from every state, the probability of hitting $y$ within the next $m$ steps is at least $\delta$. Applying the Markov property at times $m,2m,3m,\ldots$, the probability of avoiding $y$ through $km$ steps is at most $(1-\delta)^k$. This tends to zero, so $y$ is hit almost surely from every state.

Starting from $y$, after the first step the chain is still in the state space, so the same argument shows that it hits $y$ again almost surely. Therefore $y$ is recurrent. The return-probability formula gives $G(y,y)=+\infty$. $\square$

Interpretation and a Common Pitfall

The Green function combines two effects: the chance of ever reaching the target and the expected number of returns once the target has been reached. The hitting decomposition makes those contributions explicit. A target may have a large Green value because it is easy to reach, because it tends to be revisited, or both. If the target is recurrent, any positive chance of reaching it already forces the expected visit count to be infinite.

A common error is to treat a finite expected hitting time, a high hitting probability, and a finite expected visit count as interchangeable. They are different quantities. Another is to omit the time-zero visit, which changes $G(y,y)$ by one and changes the return-count formula. Finally, when a walk is killed, specify exactly when counting stops: the killed Green function counts only visits strictly before the exit time.

Green functions provide a compact language for occupation and repeated visits. In finite absorbing models, the counts can be obtained by summing the probabilities of successive cycles, as in the example above. In recurrent settings, the value $+\infty$ is meaningful rather than a computational failure: it records that the expected total number of visits does not remain finite.

Check Your Understanding

Use the definitions and examples above to answer the following questions.

Why does the definition of $G(y,y)$ include a visit at time zero?
If $f_y=2/5$, what is $G(y,y)$, and is $y$ transient or recurrent?
In the two-state killed chain, why is the probability of another completed cycle $pq$?
Can a finite irreducible chain have a finite ordinary Green function $G(y,y)$? Explain.
What distinction separates $G_D(x,y)$ from the ordinary Green function?