Consider the first $2n$ steps of a simple random walk on the integers, starting at the origin. A simple binomial argument shows that regardless of $n$, the origin gets visited the most (in expectation).

Question 1: Does this fact generalize? that is, suppose we have a symmetric random walk on $\mathbb{Z}$ starting at $0$. Is it still true that the origin gets visited the most (in expectation)?

Question 2: Suppose we have two random walks (not necessarily symmetric) $X=(X_j)_j$ and $Y=(Y_j)_j$ on $\mathbb{Z}_{\geq 0}$ that can be coupled such that $X_j\leq Y_j$ for all $j$, and such that the integer most visited by $Y$ is $0$. Does this imply the same for $X$? that is, is it necessarily true that the integer most visited by $X$ is $0$?


  • 1
    $\begingroup$ Q1: yes, look under 'green's function' in Spitzer's book or elsewhere Q2: By Q1 $X_j$ visits the point it starts from most, regardless of the coupling condition $\endgroup$ – user83457 Mar 3 '16 at 13:35
  • $\begingroup$ @michael: In Q2, I'm not assuming anything on the random walks other than, say, that they are Markovian. Specifically, I'm not assuming they are symmetric. Note however that the walk is on $\mathbb{Z}_{\geq 0}$ rather than on $\mathbb{Z}$. $\endgroup$ – Snoop Catt Mar 3 '16 at 14:07
  • 2
    $\begingroup$ Can you be precise about what you mean by the word "random walk"? The most common usage is "sum of iid random variables", which seems to be in conflict with your comments. Do you just mean an arbitrary Markov process on $\mathbb{Z}$? Is it supposed to be time-homogeneous? $\endgroup$ – Nate Eldredge Mar 3 '16 at 15:09
  • 1
    $\begingroup$ For any symmetric random walk starting from 0 on any group and any fixed even number $2n$ 0 is most visited after $2n$ steps. Indeed, let $p_k(g)$ be probability that we are in point $g$ after $k$ steps. Then $p_{2k}(0)=\sum_g (p_k(g))^2$ while for any fixed $h$ we have $p_{2k}(h)=\sum_g p_k(g)p_k(h-g)\leqslant \sum_g \frac{(p_k(g))^2+(p_k(h-g))^2}2=p_{2k}(0)$. But it does not directly imply what you need as there exist odd numbers. $\endgroup$ – Fedor Petrov Mar 3 '16 at 15:49
  • 1
    $\begingroup$ I don't think Q2 is true since you can have Y having the identical behavior at state 2,4,5,..,10, and then project Y to X so that 2,..,10 all get mapped to 2, and identity elsewhere. This way X is dominated by Y, and X may stay at 2 for a long time. $\endgroup$ – John Jiang Mar 3 '16 at 18:27

Here we prove that if steps are independent and identically symmetrically distributed, then Q1 has positive answer.

Let $p(k)$ be probability of step $k$, $p(-k)=p(k)$. Denote by $f(t)=\sum_k p(k)t^k$ the generating function. Then average number of visits of 0 during first $n$ steps is $[1] g(t)$, where $g(t)=1+f(t)+\dots+f^{n-1}(t)$, $[1]g$ means constant term of $g$. Average number of visits of a point $w$ is $[t^w] g(t)=[t^{-w}] g(t)=[1] \frac{t^w+t^{-w}}2g(t)$. Next, we use the formula $[1] h(t)=\frac1{2\pi}\int_0^{2\pi} h(e^{ix})dx$. Note that $f(e^{ix})=p_0+\sum_{k>0} 2p_k \cos kx\in [-1,1]$. Thus $$g(e^{ix})=\frac{1-f^n(e^{ix})}{1-f(e^{ix})}\geqslant 0.$$ Hence $$[1]g=\frac1{2\pi}\int_0^{2\pi} g(e^{ix})dx\geqslant \frac1{2\pi}\int_0^{2\pi} g(e^{ix})\cos (wx)dx=[1] \frac{t^w+t^{-w}}2g(t)$$ as desired.


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.