Lazy Walks and Recurrence Classification

Holding Changes the Clock, Not the Classification

A simple symmetric walk on a lattice moves at every step. A lazy version sometimes stays where it is and otherwise takes an ordinary simple symmetric step. The holding creates extra returns at short times and changes how many time steps elapse between moves. To decide whether the walk is recurrent or transient, however, it is useful to look at the sequence of actual moves: after the holding steps are removed, that sequence is just the original simple symmetric walk.

Let \(d\ge1\), let \(S=\mathbb{Z}^d\), and fix a holding probability \(a\) with \(0<a<1\). Write \(b=1-a\) for the probability of moving. On a probability space \((\Omega,\mathcal{F},\mathbb{P})\), let \((Y_m)_{m\ge0}\) be a simple symmetric walk on \(\mathbb{Z}^d\), started at \(0\), and let \((B_n)_{n\ge1}\) be independent Bernoulli random variables, independent of \(Y\), with \(\mathbb{P}(B_n=1)=b\). Set \(K_0=0\), \(K_n=\sum_{\ell=1}^n B_\ell\), and \(X_n=Y_{K_n}\). Thus \(X_n\) is a discrete-time Markov chain on \(S\), with transition matrix \(P=(p_{ij})\). From each \(i\), it stays at \(i\) with probability \(a\) and moves to each of its \(2d\) lattice neighbors with probability \(b/(2d)\). Every row sums to \(a+2d\cdot b/(2d)=a+b=1\).

Return Probabilities and Green Functions

By time \(n\), the lazy walk has made \(m\) actual moves with probability \(\binom{n}{m}b^m a^{n-m}\). Conditional on that number of moves, its location has the distribution of \(Y_m\). The possible values of \(m\) are disjoint, so for every \(n\ge0\),

This formula also covers \(m=0\): if the walk makes no moves in \(n\) steps, it is still at its starting point. Summing over all times gives a particularly simple relation.

Proof. All terms in the formula for \(q_n\) are nonnegative. Therefore the two sums can be rearranged, including when their value is infinite. Group the terms contributing to a fixed \(u_m\):

For fixed \(m\), put \(r=n-m\). The inner sum is \(\sum_{r=0}^{\infty}\binom{r+m}{m}a^r=(1-a)^{-m-1}=b^{-m-1}\), by the power-series identity for \((1-a)^{-m-1}\), valid because \(0<a<1\). Hence \(b^m\) times that sum is \(1/b\), and \(G_{\mathrm{l}}=(1/b)\sum_{m=0}^{\infty}u_m=G_{\mathrm{s}}/b\).

To connect this calculation to recurrence, let \(f=\mathbb{P}_0(T_0^+<\infty)\) for either walk, and let \(v_n\) be its return probability at time \(n\), with \(v_0=1\). The number of visits to \(0\), including the visit at time \(0\), has expectation \(\sum_{n\ge0}v_n\): write that number as \(\sum_{n\ge0}\mathbf{1}_{\{X_n=0\}}\) and use monotone convergence. By the Markov property at successive returns, the probability of at least \(k\) returns after time \(0\) is \(f^k\) for every integer \(k\ge0\). Thus the expected number of visits is \(\sum_{k\ge0}f^k\): it is \(1/(1-f)\) if \(f<1\), and infinite if \(f=1\). In particular, the Green function is infinite exactly when the state is recurrent. Since \(G_{\mathrm{l}}=G_{\mathrm{s}}/b\) with \(0<b<1\), one is infinite exactly when the other is. This proves the classification claim. \(\square\)

For these walks, the standard lattice classification established in the earlier material on Green functions and Pólya’s theorem is that the simple symmetric walk is recurrent in dimensions \(1\) and \(2\), and transient in dimensions \(d\ge3\). The theorem therefore gives the same classification for every \(0<a<1\): the lazy walk is recurrent in dimensions \(1\) and \(2\), and transient in dimensions \(d\ge3\). The dimension-dependent conclusion comes from the simple walk’s Green function; the effect of laziness is the exact factor \(1/b\).

Period and a Common Pitfall

Holding also changes the period. For a state \(i\), its period is the greatest common divisor of the positive integers \(n\) for which \(p_{ii}^{(n)}>0\). In the non-lazy simple symmetric lattice walk, every return takes an even number of steps, so its period is \(2\). In the lazy walk, \(p_{ii}=a>0\), so a return in one step is possible and the period is \(1\). This change in period is not a change in recurrence: period concerns which times can have positive return probability, while recurrence concerns whether a return eventually occurs with probability \(1\).

Common mistake. A tempting but incorrect calculation is to say that a lazy walk has the same return probabilities as the simple walk because deleting holds leaves a simple walk. Deleting holds preserves the sequence of visited positions, but it changes the time index. For example, in one dimension with \(a=\tfrac12\), the simple walk has \(u_1=0\), whereas the lazy walk has \(q_1=\tfrac12\). The correct calculation conditions on the number \(m\) of moves by time \(n\), giving \(q_n=\sum_{m=0}^n\binom{n}{m}a^{n-m}b^m u_m\). Summing that formula over all \(n\) yields the factor \(1/b\), not equality of the return probabilities.

The condition \(0<a<1\) matters. If \(a=1\), the walk never moves and its transition matrix is not an irreducible lattice-walk kernel; if \(a=0\), there is no holding and the relation \(G_{\mathrm{l}}=G_{\mathrm{s}}/b\) reduces to the identity. For positive holding probability and positive move probability, laziness lengthens the clock and permits returns at additional times, but it leaves the embedded sequence of lattice moves unchanged. The exact Green-function identity makes that distinction precise.