Return Probabilities as Visit Counts
For a random walk, the probability of being at the origin at time \(n\) measures the chance of a visit at one particular time. Adding these probabilities over time produces a quantity that records all visits on average. This sum is called the Green function at the origin. Its value may be finite or infinite, and its definition includes the visit at time zero.
Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, and let \((X_n)_{n\ge 0}\) be a discrete-time random walk on \(S=\mathbb{Z}^d\), where \(d\ge 1\). For the walks considered here, \(X_0=x\) and \(X_n=x+\xi_1+\cdots+\xi_n\), with independent, identically distributed increments \(\xi_k\) in \(\mathbb{Z}^d\); the empty sum at \(n=0\) is zero. Write \(\mathbb{P}_x\) and \(\mathbb{E}_x\) for probability and expectation when the initial state is \(x\). The transition kernel is \(p(x,y)=\mathbb{P}_x(X_1=y)\). It is row-stochastic: for every \(x\), \(\sum_{y\in S}p(x,y)=1\), since the possible next states have total probability one.
Both definitions use all times \(n\ge 0\). In particular, if \(X_0=0\), then the \(n=0\) term is \(1\) in the visit count and \(\mathbb{P}_0(X_0=0)=1\) in the Green function. The value \(G(0,0)\) is not defined as the probability of ever returning: it is the sum of the probabilities of being at the origin at each time, including the initial time.
Proof. For each integer \(N\ge 0\), define the finite visit count \(V_{0,N}=\sum_{n=0}^{N}\mathbf{1}_{\{X_n=y\}}\). Linearity of expectation for this finite sum and the identity \(\mathbb{E}_x[\mathbf{1}_{\{X_n=y\}}]=\mathbb{P}_x(X_n=y)\) give \(\mathbb{E}_x[V_{0,N}]=\sum_{n=0}^{N}\mathbb{P}_x(X_n=y)\). As \(N\) increases, \(V_{0,N}\) increases pointwise to \(\sum_{n=0}^{\infty}\mathbf{1}_{\{X_n=y\}}\). The monotone convergence theorem for nonnegative random variables therefore gives \(\mathbb{E}_x[\sum_{n=0}^{\infty}\mathbf{1}_{\{X_n=y\}}]=\lim_{N\to\infty}\mathbb{E}_x[V_{0,N}]\). The finite sums on the right increase to \(\sum_{n=0}^{\infty}\mathbb{P}_x(X_n=y)\). This proves the identity, including when the limit is infinite. \(\square\)
The proof does not require the Markov property or independent increments; it uses only nonnegative indicators and monotone convergence. The random-walk structure is useful for calculating the probabilities in the sum. A finite partial sum \(G_N(0,0)=\sum_{n=0}^{N}\mathbb{P}_0(X_n=0)\) is exactly the expected number of visits by time \(N\), including time zero. The full Green function is the increasing limit of these finite-time expectations.
Worked Green-Function Calculations
Worked Example: A Symmetric Walk on the Integers Through Time Four
Let \(S=\mathbb{Z}\), \(X_0=0\), and let each increment be \(+1\) or \(-1\) with probability \(\tfrac12\). Each row of the transition kernel has two nonzero entries, \(\tfrac12\) to the right and \(\tfrac12\) to the left, so every row sums to \(\tfrac12+\tfrac12=1\). Compute the expected number of visits to zero from time zero through time four.
A return to zero is possible only after an even number of steps, because each step changes the parity of the position. At time zero the walk is at zero with probability \(1\), and at times one and three its return probability is \(0\). At time two, the two returning paths are \((+1,-1)\) and \((-1,+1)\). There are \(2^2=4\) equally likely paths, so \(\mathbb{P}_0(X_2=0)=\tfrac24=\tfrac12\).
At time four, a path returns to zero exactly when it has two \(+1\) steps and two \(-1\) steps. There are \(\binom42=6\) such paths among \(2^4=16\) equally likely paths. Thus \(\mathbb{P}_0(X_4=0)=\tfrac6{16}=\tfrac38\). The finite Green sum is
By the theorem, this is also the expected number of visits to zero at times \(0,1,2,3,4\). As a direct check, the visit count is \(1+\mathbf{1}_{\{X_2=0\}}+\mathbf{1}_{\{X_4=0\}}\), since the odd-time indicators are zero. Its expectation is \(1+\tfrac12+\tfrac38=\tfrac{15}{8}\), the same value.
Worked Example: The Full Green Function for a Biased Walk
Let \(S=\mathbb{Z}\), \(X_0=0\), and take independent increments with probability \(p=\tfrac34\) of \(+1\) and probability \(q=\tfrac14\) of \(-1\). Every row has transition probabilities \(\tfrac34\) to the right and \(\tfrac14\) to the left, whose sum is \(1\). We compute \(G(0,0)\), including all times.
To be at zero at time \(2n\), the walk must have exactly \(n\) increments of each sign. There are \(\binom{2n}{n}\) such sequences, and each has probability \(p^nq^n\). Odd-time return probabilities are zero. Hence
Here \(pq=\tfrac{3}{16}\). To evaluate the sum, let \(a_n=\binom{2n}{n}\) and \(H(x)=\sum_{n=0}^{\infty}a_nx^n\) for \(0\le x<\tfrac14\). The ratio \(a_{n+1}/a_n=2(2n+1)/(n+1)\) tends to \(4\), so this power series converges for \(x<\tfrac14\), and it can be differentiated there. Comparing coefficients using \((n+1)a_{n+1}=2(2n+1)a_n\) gives \((1-4x)H'(x)=2H(x)\). Therefore the derivative of \(\sqrt{1-4x}\,H(x)\) is zero: the product rule gives \(-2H(x)/\sqrt{1-4x}+\sqrt{1-4x}\,H'(x)=0\) by that differential equation. Since \(H(0)=a_0=1\), the product is constantly \(1\), and \(H(x)=1/\sqrt{1-4x}\).
Substituting \(x=pq=\tfrac{3}{16}\), which is less than \(\tfrac14\), gives
Check: The first three nonzero terms, at times zero, two, and four, are \(1\), \(\binom21(\tfrac{3}{16})=\tfrac38\), and \(\binom42(\tfrac{3}{16})^2=6\cdot\tfrac9{256}=\tfrac{27}{128}\). They sum to \(\tfrac{128}{128}+\tfrac{48}{128}+\tfrac{27}{128}=\tfrac{203}{128}\), below the full value \(2=\tfrac{256}{128}\), as required for an increasing partial sum.
Worked Example: Four-Step Returns on the Three-Dimensional Lattice
Consider the simple symmetric nearest-neighbor walk on \(S=\mathbb{Z}^3\), started at the origin. At each step it chooses one of the six vectors \((1,0,0),(-1,0,0),(0,1,0),(0,-1,0),(0,0,1),(0,0,-1)\), each with probability \(\tfrac16\). Every row of the transition kernel has six entries equal to \(\tfrac16\), with sum \(6\cdot\tfrac16=1\). Find the expected number of visits through time four.
There is no return at times one or three: each step changes the parity of the sum of the coordinates. At time two, a return requires choosing a direction and then its opposite. There are six possible first steps, each with exactly one opposite second step, giving \(6\) returning paths out of \(6^2=36\). Thus \(\mathbb{P}_0(X_2=0)=\tfrac6{36}=\tfrac16\).
For a return at time four, either all four steps lie on one coordinate axis, with two steps in each direction, or the four steps use two coordinate axes, with one step in each direction on each axis. In the first case, choose the axis in \(3\) ways and arrange two positive and two negative steps in \(\binom42=6\) ways, giving \(3\cdot6=18\) paths. In the second case, choose the two axes in \(\binom32=3\) ways; for each choice, the four distinct signed directions can be ordered in \(4!=24\) ways, giving \(3\cdot24=72\) paths. These cases are disjoint and include every four-step return, so there are \(18+72=90\) returning paths out of \(6^4=1296\). Therefore \(\mathbb{P}_0(X_4=0)=\tfrac{90}{1296}=\tfrac5{72}\).
The expected number of visits through time four is consequently
Check: The path counts give the same probabilities directly: the time-two count is \(6/36=1/6\), and the time-four count is \(90/1296=5/72\). Adding these to the certain initial visit gives \(1+\tfrac16+\tfrac5{72}=\tfrac{89}{72}\).
Interpreting the Green Function Correctly
The identity between \(G(0,0)\) and \(\mathbb{E}_0[V_0]\) is an equality of an extended expectation with a nonnegative series. It does not assert that the series is finite. If the partial sums grow without bound, the expected total number of visits is infinite. Conversely, a finite value is an average count, not a probability. In the biased-walk example, \(G(0,0)=2\), which already shows it cannot be a probability of an event.
Common mistake: omitting the initial visit. For the biased walk above, omitting time zero would produce the incorrect sum \(G(0,0)-1=1\) as the expected total count. But \(V_0\) explicitly includes \(\mathbf{1}_{\{X_0=0\}}=1\), so its expectation must include the term \(\mathbb{P}_0(X_0=0)=1\); the correct value is \(2\). For a direct check on a walk that always steps one unit to the right, every row has a single transition of probability \(1\), and a walk started at zero visits zero only at time zero. Its Green function and total visit count are both \(1\), not \(0\).
A useful calculation strategy is to separate the conceptual identity from the path counting. First write the desired finite or infinite sum of return probabilities, retaining its \(n=0\) term. Then calculate each probability using the walk’s allowed increments and their probabilities. For a finite truncation, count paths of length \(n\) that end at the target and divide by the total probability mass of all length-\(n\) paths, or sum their individual probabilities when paths are not equally likely. Finally, the theorem identifies that sum with the corresponding expected visit count. The identity itself does not require a separate argument for each lattice dimension.
Check Your Understanding
In each question, count visits starting at time zero unless a different time range is specified.
- For the symmetric walk on \(\mathbb{Z}\), why are the return probabilities at times one and three zero?
- For the biased walk with \(p=\tfrac34\) and \(q=\tfrac14\), calculate the time-six return probability from \(\binom{6}{3}(pq)^3\).
- Write the finite-time visit-count identity for visits to a state \(y\) through time \(N\).
- Why does the Green-function identity remain valid if the expected total number of visits is infinite?
- For a walk started at the origin, identify the \(n=0\) term in both \(G(0,0)\) and the total visit count.