3
$\begingroup$

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$?

Thanks!

Improve this question
$\endgroup$
16
  • 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
    Commented Mar 3, 2016 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
    Commented Mar 3, 2016 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
    Commented Mar 3, 2016 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
    Commented Mar 3, 2016 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
    Commented Mar 3, 2016 at 18:27

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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