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.

(¹) Added in edit

  • 1
    $\begingroup$ 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. $\endgroup$ – Anthony Quas Mar 3 '16 at 2:33
  • $\begingroup$ But what if mu doesn't have a first moment? Is it obviously transient? $\endgroup$ – Vladimir Mar 3 '16 at 22:14
  • $\begingroup$ 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). $\endgroup$ – 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).

  • $\begingroup$ 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! $\endgroup$ – Vladimir Mar 14 '16 at 23:38
  • $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ 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? $\endgroup$ – Vladimir Mar 9 '16 at 21:36
  • $\begingroup$ Yes, you are right $\endgroup$ – R W Mar 9 '16 at 23:28
  • $\begingroup$ 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. $\endgroup$ – Vladimir Mar 10 '16 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.