# Robustly recurrent random walk

Is there a probability measure $\mu$ on $\mathbb{Z}$ such that, for every $0 < \alpha \leq 1$ and every finitely supported (¹) probability measure $\nu$ on $\mathbb{Z}$, it holds that the $\alpha \mu + (1-\alpha)\nu$-random walk on $\mathbb{Z}$ is recurrent? It seems like $\mu(n) = C/(1+n^2)$ is a good candidate.

• I believe this question is answered negatively in Spitzer's book. I think if $\mu$ doesn't have a first moment, then the random walk is not recurrent (in one dimension); in two dimensions, you need a second moment (and the expectation to be 0) for recurrence, I believe. – Anthony Quas Mar 3 '16 at 2:33
• But what if mu doesn't have a first moment? Is it obviously transient? – Vladimir Mar 3 '16 at 22:14
• Since the answers below are to your original question, I took the liberty to mention the part that I understood was added. Fix if I was wrong, and note that it is better to make edits more explicit (I had much trouble understanding the answers after reading the edited version of the question). – Benoît Kloeckner Mar 9 '16 at 21:48

It's indeed not so clear (to me) if one can have a recurrent random walk with a measure that doesn't have an expectation, but the answer to your actual question is no (and it's quite a bit more subtle than I thought originally, in my naïve comment). We obtain precise criteria from versions of the law of large numbers for random variables with $E|X_j|=\infty$, which can be found in this 1973 article by Erickson.

Adapted to your setting, Erickson proves that $\limsup S_n/n=\infty$ if and only if $$\sum_{n\ge 1} \frac{n}{f(n)}\rho(n)=\infty , \quad f(n):=\int_{-n}^0 \rho((-\infty,x])\, dx \quad\quad\quad\quad (1)$$ (= Theorem 2(a)). Here, $S_n$ denotes the position of the random walk at time $n$, and $\rho$ is the distribution of a single step.

Similarly, the analogous condition $$\sum_{n\ge 1} \frac{n}{g(n)}\rho(-n)=\infty , \quad g(n):=\int_0^n \rho((x,\infty))\, dx \quad\quad\quad\quad (2)$$ is equivalent to $\liminf S_n/n=-\infty$, and if we have (1), but not (2), then $\lim S_n/n=\infty$ a.s. (this is Theorem 2(c)), which means that the RW is transient.

Now to answer to your question, I claim that given any $\mu$, I will be able to find a $\nu$ such that $\rho=(1/2)(\mu+\nu)$ satisfies (1), but not (2). In fact, (1) is easy because $f(n)=o(n)$, so I just need $\nu(n)$'s not extremely small every once in a while at very large $n$'s.

As for (2), let me assume that $\mu$ is supported by the negative integers (it only gets easier otherwise). Take $N_1$ so large that $\sum_{n\le N_1}\mu(-n)\ge 1/2$. My $\nu$ will be supported by the positive integers, and we now agree that it will give zero weight to $n\le N_1$. Then $g(n)=n/2$ for those $n$. Next, I take $N_2>N_1$ so large that $\sum_{N_1<n\le N_2}\mu(n)\ge 1/4$, and we then agree that $\nu$ gives weight $\le 1/10$ to this interval. This will make sure that $g(n)\ge (9/20)n$, so $n/g(n)$ from the sum from (2) amplifies the $\mu(-n)$'s by at most $20/9$. We can continue in this way. The sum will be finite, and the conditions on $\nu$ that I obtain from this procedure only require me to move much of the weight very far out, which is not interfering with (1) (in fact, it's helping me).

• Thank you very much for your detailed answer. However, I had omitted an important part of the question, and I don't think that your answer still applies to the question now posted. Do you think the same argument applies when $\nu$ has to be finitely supported? Thanks! – Vladimir Mar 14 '16 at 23:38
• No, the whole argument will only work to establish transience. I can start out with a $\mu$ such as yours and then conclude that for a finitely supported perturbation, we'll have $\liminf S_n/n=-\infty$, $\limsup S_n/n=\infty$ a.s., but this only says that I cross $0$ infinitely many times, I can't be sure if I also hit $n=0$ exactly eventually. – Christian Remling Mar 15 '16 at 1:18

Contrary to the common opinion, it is not true that any random walk with infinite first moment on $\mathbb Z$ is transient. Example E2 on p.87 of the second edition of Spitzer's book Principles of Random Walks shows that for the probability measures $\mu$ on $\mathbb Z$ such that $$|n|^\alpha\mu(n) = c + o(1) \qquad \text{with} \;c>0$$ the random walk $(\mathbb Z,\mu)$ is recurrent if and only if $\alpha\ge 2$. However, for $\alpha=2$ the first moment of the measure $\mu$ is infinite (this is precisely the situation the OP is referring to). In fact, Spitzer further (in example E3) gives a very explicit example of a recurrent measure with an infinite first moment (which also satisfies the above formula with $\alpha=2$). This is the step distribution of the random walk on the diagonal $\{(n,m)\in\mathbb Z^2: n=m\}$ induced by the simple random walk on $\mathbb Z^2$.

Now, returning to your question about "robustness". The answer is no. Moreover, it is the transience that is "robust" in your sense. The reason is a comparison criterion for recurrence/transience of general Markov chains (Theorem 2.25 in Woess' book Random Walks on Infinite Graphs and Groups). In the group setup it implies that if the random walk on a group $G$ determined by the measure $\alpha\mu +(1-\alpha)\nu$ is recurrent and the measure $\nu$ is symmetric, then the random walk $(G,\nu)$ is also recurrent. Or, in other words, if $(G,\nu)$ is transient for a symmetric $\nu$, then $(G,\alpha\mu +(1-\alpha)\nu)$ is also transient for any $\mu$ and any $\alpha<1$.

• Note: I added an additional hypothesis, namely that $\nu$ is finitely supported. Given this, it seems that your answer would imply that $\alpha \mu + (1-\alpha)\nu$ is also recurrent, given that $|n|^2\mu(n) = c+o(1)$. No? – Vladimir Mar 9 '16 at 21:36
• Yes, you are right – R W Mar 9 '16 at 23:28
• Actually, I looked at Spitzer's book and the criterion you give is only stated for symmetric $\mu$. So again I'm not sure what the answer is. – Vladimir Mar 10 '16 at 17:33