I want to know whether the Borel-Cantelli lemma is true for a random walk. More precisely, this question can be described as follows.

Let $X_1,X_2,\cdots$ be i.i.d. taking values in $\mathbb{R}^d$ and let $S_n=X_1+\cdots+X_n$. Suppose that $A\subset\mathbb{R}^d$ is a Borel set (for example, $A$ can be $\{0\}$ or $(-\infty,0]$ for $d=1$), then do we have $P(S_n\in A,i.o.)=0$ if and only if $\sum\limits_{n=1}^\infty P(S_n\in A)<\infty$ ?
Where $i.o.$ means infinitely often, that is $(S_n\in A,i.o.)=\mathop{\cap}\limits_{k=1}^\infty\mathop{\cup}\limits_{n=k}^\infty(S_n\in A)$.

Obviously, the "$\Leftarrow$" part of this question is true because of the usual Borel-Cantelli Lemma.
In a special case, when $A=\{0\}$, this proposition is true, and we can see a proof from Rick Durrett's book Probability:Theory and Examples, Fourth Edition, Chapter 4.2. It is proved by introducing a series of stopping time: let $\tau_n$ be the time of the $n$th return to $0$, that is define $\tau_0=0$ and $\tau_n=\inf\{m>\tau_{n-1}:S_m=0\}$. But this method does not work for other cases of $A$.
I know that this proposition is true when :
(1) $A$ is a finite set ; (2) $A$ is a bounded set and 0 is an interior point of $A$.
For case (1) , we can imitate the method described above when $A=\{0\}$.
For case (2) , we have a theorem (also from Probability:Theory and Examples, Fourth Edition, Chapter 4.2 ):

If $\sum\limits_{n=1}^\infty P(\Vert S_n\Vert<\varepsilon)=\infty$, then $P(\Vert S_n\Vert<2\varepsilon, i.o.)=1$, and the convergence or divergence of the sums is independent of $\varepsilon$. ( where $\Vert\cdot\Vert$ is a norm on $\mathbb{R}^d$ )

But what about other cases?


2 Answers 2


No, this isn't true, and to construct a counterexample, take any of the stable distributions with nice scaling properties that have first moments but not second moments, that would be in the usual notation, ( https://en.wikipedia.org/wiki/Stable_distribution) $\alpha \in (1,2)$, and base the random walk on X-1. $$P(S_n - n > 0) = P( \frac {S_n}{n^{\frac 1 \alpha}} - n^{1-\frac 1 \alpha} > 0) = P(X_1 > n^{\frac {\alpha -1} \alpha})$$$$$$ The wikipedia article mentions that this last is order of $\frac 1 {n^{\alpha -1}}$, which sums to infinity. The random walk, though, is just a negative mean r.w. and so it is not >0 i.o. This, https://en.wikipedia.org/wiki/Hsu–Robbins–Erdős_theorem,shows that this behavior is typical of r.w.s without 2nd moments.


Just a quick remark about another counterexample that one may construct: take a Simple Random Walk (on the integer lattice) in dimension $d\geq 3$ (so it is transient); then, an infinite set can be recurrent (i.e., visited infinitely often a.s.) or transient. To distinguish one from another, there is that Wiener's test (e.g., Corollary 6.5.9 in Lawler-Limic "Random walk - a modern introduction" book), which is formulated in terms of capacities of intersections of that set with exponentially growing annuli. So, you need an example of an infinite set which is transient, but the expected number of visits there is infinite. Since it is easy to estimate this expected number in terms of the distances of the points of the set to the origin (the total number of visits to the set is the sum of visit counts over all its points) and this would be much simpler than the Wiener' test, such an example should exist :)


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .