one-dimensional random walk

Question

Consider a one-dimensional random walk whose steps are $+2$ and $-1$ with probabilities $p$ and $1-p$ respectively, starting from $0$ and in the interval {$-n$, $n$}. The walk ends at $-n$ or $n$ or $n+1$. Let $m$ be the number of integers "jumped" during the walk.

Is there a limit for the ratio $\frac{m}{2n+1}$ for $n \rightarrow \infty$?

Three examples to clarify:

1) n=15 p= 1/2 Steps = {-1, 2, -1, 2, -1, 2, -1, 2, -1, -1, 2, 2, -1, -1, 2, 2, 2, 2, -1, \ -1, 2, -1, -1, 2, -1, 2, -1, -1, 2, 2}

Positions = {0, -1, 1, 0, 2, 1, 3, 2, 4, 3, 2, 4, 6, 5, 4, 6, 8, 10, 12, 11, 10, \ 12, 11, 10, 12, 11, 13, 12, 11, 13, 15}

Missed (jumped) positions = {-15, -14, -13, -12, -11, -10, -9, -8, -7, -6, -5, -4, -3, -2, 7, 9, 14}

m = 17; r = m/(2 n +1) = 0.548387

2) n= 15 p=1/2 Steps = {2, 2, 2, 2, -1, -1, 2, 2, 2, -1, -1, -1, -1, 2, 2, -1, -1, -1, 2, \ -1, 2, -1, -1, 2, 2, 2}

Positions = {0, 2, 4, 6, 8, 7, 6, 8, 10, 12, 11, 10, 9, 8, 10, 12, 11, 10, 9, 11, \ 10, 12, 11, 10, 12, 14, 16}

Missed positions = {-15, -14, -13, -12, -11, -10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 1, 3, 5, 13, 15}

m =20; r = m/(2 n +1) = 0.645161

3) n=20 p=1/2 Steps = {-1, 2, -1, 2, 2, 2, -1, -1, -1, -1, -1, -1, 2, -1, 2, 2, 2, -1, 2, \ -1, 2, -1, -1, -1, -1, -1, 2, -1, -1, -1, 2, -1, -1, -1, 2, -1, 2, \ -1, 2, 2, -1, -1, -1, -1, -1, -1, -1, 2, 2, -1, -1, 2, 2, -1, 2, -1, \ 2, 2, 2, -1, 2, 2, 2, 2}

Positions = {0, -1, 1, 0, 2, 4, 6, 5, 4, 3, 2, 1, 0, 2, 1, 3, 5, 7, 6, 8, 7, 9, \ 8, 7, 6, 5, 4, 6, 5, 4, 3, 5, 4, 3, 2, 4, 3, 5, 4, 6, 8, 7, 6, 5, 4, \ 3, 2, 1, 3, 5, 4, 3, 5, 7, 6, 8, 7, 9, 11, 13, 12, 14, 16, 18, 20}

Missed positions = {-20, -19, -18, -17, -16, -15, -14, -13, -12, -11, -10, -9, -8, -7, \ -6, -5, -4, -3, -2, 10, 15, 17, 19}

m =20; r = m/(2 n +1) = 0.560976

A simulation with the range {-2000,2000}, iterated 1000 times provides r as 0.572958.

The question is: Is there a limit for n -> Infinity based on: (n, p, base steps {-1,2}) ?

Answer 1

I am not entirely sure what you mean by integers "jumped", so I will provide two different answers:

If by integers jumped you mean the amount of times you jump an integer (i.e., move forward) during the random walk, then irrespective of $n$ (as long as it is greater than or equal to 2), there is the possible scenario of an unbounded number of forward moves: just think of the repeating sequence [backward step, forward step, backward step] repeated over and over. Therefore, even with $n = 2$ you can have an arbitrarily large ratio $m/(2n+1)$. There is no limit for the ratio as $n\rightarrow \infty$.

If on the other hand you mean the amount of integers which remain unstepped in the inverval, then it is easy to determine that the maximum amount of unstepped integers is $n/2 + n = 3n/2$, which is obtained (not exclusively) by the sequence that contains only forward steps. Any backward step executed results at best in the same amount of unstepped integers in the walk (if landing on an unstepped integer and followed by another backward step also landing on an unstepped integer), or in the possible decrease of unstepped integers (if landing on an unstepped integer or if followed by a forward step landing on a previously unstepped integer). Given this value, if follows that the ratio $m/(2n+1) = (3n/2)/(2n+1) = 3n/(4n+2)$ converges to $3/4$ as n approaches infinity.

Answer 2

Assume first that $2p\lt q$ with $q=1-p$, hence the (unstopped) random walk goes to $-\infty$ almost surely. Since negative steps are only $-1$ steps, one visits every negative site and finitely many positive sites, hence the missed sites are, roughly speaking, the positive ones and the asymptotic expected and almost sure proportions of missed sites are both $\mu=1/2$.

Assume now that $2p\gt q$, hence the (unstopped) random walk goes to $+\infty$ almost surely. Let $v$ and $u_k$ denote the respective probabilities that $-1$ and $k\geqslant1$ are visited by the unstopped random walk. The only negative step is $-1$ hence, for every $k\geqslant1$, $v^k$ is the probability that $-k$ is visited by the unstopped random walk. The expected number $s_n$ of sites visited before hitting $\{-n,n,n+1\}$ is such that $s_n\leqslant1+t_n+\sum\limits_{k\geqslant1}v^k$ with $t_n=\sum\limits_{k=1}^{n}u_k$, hence $s_n\leqslant O(1)+t_n$. On the other hand, $s_n\geqslant\sum\limits_{k=1}^{n}u^{(n)}_k$, where $u_k^{(n)}$ is the probability that $k$ is visited by the stopped random walk. Hence $u_k=u_k^{(n)}+(1-u_k^{(n)})v^{n-k}$ and $s_n\geqslant O(1)+t_n$.

We now evaluate $t_n$. The Markov property of the random walk after one step yields the identities $v=pv^3+q$, $u_1=pv+qu_2$, $u_2=p+qu_3$, and $u_k=pu_{k-2}+qu_{k+1}$ for every $k\geqslant3$. Thus, $$ v^2+v=q/p, $$ and the usual translation of these identities in terms of generating functions yields $$ (1-x)\sum\limits_{k=1}^{+\infty}u_kx^{k-1}=\frac{qu_1-pvx-px^2}{q-px-px^2}. $$ Since $v\lt1$, the LHS is well defined for $x=v$. Since $x=v$ is a root of the denominator of the fraction on the RHS, this must also be a root of the numerator, hence $qu_1=2pv^2$. Thus, the RHS is in fact $$ \frac{2pv^2-pvx-px^2}{q-px-px^2}=\frac{x+2v}{x+v+1}, $$ hence the limit of the LHS when $x\to1$ is $w$ and $t_n\sim nw$ when $n\to\infty$, with $$ w=\frac{1+2v}{2+v},\qquad 2v=-1+\sqrt{1+4q/p}. $$ Finally, the expected proportion of sites visited before hitting $\{-n,n,n+1\}$ is $\frac{s_n}{2n+1}\sim\frac12\frac{t_n}n$, hence the expected and almost sure proportions of missed sites both converge to $$ \mu=1-\frac{w}2=\frac3{3+\sqrt{1+4q/p}}. $$ If $p=1/2$, then $\mu\approx0.572949$. The function $p\mapsto\mu(p)$ increases continuously on $(1/3,1)$ from $\mu(1/3)=1/2$ to $\mu(1)=3/4$.