Remarks on the speeds of a class of random walks on the integers

Maher Boudabra, Greg Markowsky
Monash University

Abstract

In recent years, there has been an interest in deriving certain important probabilistic results as consequences of deterministic ones; see for instance [1] and [2]. In this work, we continue on this path by deducing a well known equivalence between the speed of random walks on the integers and the growth of the size of their ranges. This result is an immediate consequence of the Kesten-Spitzer-Whitman theorem, and by appearances is probabilistic in nature, but we will show that it follows easily from an elementary deterministic result. We also investigate the common property of recurrent random walks of having speed zero, and show by example that this property need not be shared by deterministic sequences. However, if we consider the inter-arrival times (times at which the sequence is equal to 0) then we find a sufficient deterministic condition for a sequence to have zero speed, and show that this can be used to derive several probabilistic results.

In many probabilistic settings, the speed of a random walk $X_{n}$ on the integers ${\mathbb{Z}}$ is defined to be $\lim_{n\to\infty}\frac{|X_{n}|}{n}$ , whenever the limit exists. Over time, a number of interesting equivalences have been derived relating the speed with other quantitative aspects of the walk in question. The standard proofs in the literature are probabilistic, however several of these results are actually deterministic ones in disguise. The purpose of this note is to describe several examples of this phenomenon.

1 Equivalence of speeds of the range and of the random walk

Let us refer to a stochastic process of the form

X_{0}=0,\,\,X_{n}=\sum_{k=1}^{n}Z_{k}

where the $Z_{i}$ ’s are i.i.d random variables with $\mathbb{P}(Z_{i}=1)=1-\mathbb{P}(Z_{i}=-1)=p$ , as simple random walk on $\mathbb{Z}$ . We then have the following theorem, which is a special case of the Kesten-Spitzer-Whitman Theorem (see [3, Ch. 1])

Theorem 1.

\underset{{\scriptscriptstyle n\rightarrow+\infty}}{\lim}\frac{R_{n}}{n}=\mathbb{P}\left\{\text{$X_{n}\neq 0$ }\forall n>0\right\}=\mathbb{P}\{\text{$X_{n}$ never returns to }0\}

where

R_{n}=\text{card}\{X_{0},...,X_{n}\}

In other words, the number of distinct values taken by $X_{n}$ up to time $n$ can be used to calculate the probability of never returning to zero. It can also be shown that (see [4])

\mathbb{P}\{\text{$X_{n}$ never returns to }0\}=|2p-1|={\displaystyle\lim_{{\scriptscriptstyle n\rightarrow+\infty}}}\frac{|X_{n}|}{n},

with the final equality being simply the Law of Large Numbers, and therefore

\underset{{\scriptscriptstyle n\rightarrow+\infty}}{\lim}\frac{R_{n}}{n}=\underset{{\scriptscriptstyle n\rightarrow+\infty}}{\lim}\frac{|X_{n}|}{n}

(1.1)

We consider the left side of this equation to be the speed of the range process $R_{n}$ , and as discussed before the right is the speed of the walk $X_{n}$ . The standard proofs of the preceding facts are all probabilistic; however, despite appearances, the equality (1.1) is deterministic in nature, as we now show.

Let $x_{n}$ be an (deterministic) integer valued sequence satisfying

\begin{vmatrix}x_{n+1}-x_{n}\end{vmatrix}\leq 1.

(1.2)

As before set

r_{n}=\text{card}\left\{x_{0},x_{1},...,x_{n}\right\}

We give the following result.

Proposition 2.

\underset{{\scriptscriptstyle n\rightarrow+\infty}}{\lim}\frac{x_{n}}{n}=\ell

then

\underset{{\scriptscriptstyle n\rightarrow+\infty}}{\lim}\frac{r_{n}}{n}=\begin{vmatrix}\ell\end{vmatrix}.

Proof.

Without loss of generality we assume $x_{0}=0$ , and suppose first that $\ell>0$ . Let $0<\varepsilon<\ell$ , as

\underset{{\scriptscriptstyle n\rightarrow+\infty}}{\lim}\frac{x_{n}}{n}=\ell

then there is $N>0$ such that

n\left(\ell-\varepsilon\right)\leq x_{n}\leq n\left(\ell+\varepsilon\right)\,\,\,\,\text{for $n>N$ }

(1.3)

Because of (1.2), we get

\lfloor n\left(\ell-\varepsilon\right)\rfloor\leq r_{n}

Furthermore

\text{card}\{x_{N},...,x_{n}\}\leq n(\varepsilon+\ell)

since all terms are positive and bounded above by $n(\varepsilon+\ell)$ . Therefore

r_{n}\leq r_{N-1}+\text{card}\{x_{N},...,x_{n}\}\leq r_{N-1}+n(\varepsilon+\ell)

Hence

\ell-\varepsilon\leq\liminf_{+\infty}\frac{r_{n}}{n}\leq\limsup_{+\infty}\frac{r_{n}}{n}\leq\ell+\varepsilon

The result now follows. The case $\ell<0$ is similar by considering $-x_{n}$ instead. Assume now $\ell=0$ , in this case we get

|x_{n}|\leq r_{N-1}+2\varepsilon n

instead of (1.3) for $n>N$ , and the rest follows as before. ∎

We now present a probabilistic application of this result. It is of interest to define random walks whose increments are no longer i.i.d, but are instead assumed to be ergodic (see [5] for relevant definitions). Let $(\xi_{n})_{n}$ be an ergodic sequence of random variables with values in $\{-1,0,1\}$ , and let $X_{n}=\sum_{k=1}^{n}\xi_{k}$ . As before let $R_{n}=\text{card}\{X_{0},...,X_{n}\}$ . We then have the following proposition, which generalizes Theorem 1, and which is an immediate consequence of Proposition 2.

Proposition 3.

\underset{{\scriptscriptstyle n\rightarrow+\infty}}{\lim}\frac{R_{n}}{n}=|E(\xi_{0})|

If we put the weaker condition $\begin{vmatrix}x_{n+1}-x_{n}\end{vmatrix}\leq m$ where $m$ is an integer greater than $1$ , then we have the following generalization

Proposition 4.

If ${\displaystyle\underset{{\scriptscriptstyle n\rightarrow+\infty}}{\lim}\frac{x_{n}}{n}=\ell}$ then

\frac{|\ell|}{m}\leq\liminf_{+\infty}\frac{r_{n}}{n}\leq\limsup_{+\infty}\frac{r_{n}}{n}\leq\min(1,|\ell|)

(1.4)

The proof is based on the following technical lemma.

Lemma 5.

(Maximal range inequality)

Under the previous assumption we have

\frac{{\displaystyle\max_{0\leq k\leq n}\begin{vmatrix}x_{k}-x_{0}\end{vmatrix}}}{m}+1\leq r_{n}

(1.5)

Proof.

We proceed by induction on $n$ and without loss of generality we may assume $x_{0}=0$ (otherwise replace each $x_{n}$ by $x_{n}-x_{0}$ ). The property holds for $n=0$ since

\underset{=0}{\underbrace{\frac{{\displaystyle\max_{0\leq k\leq 0}\begin{vmatrix}x_{k}\end{vmatrix}}}{m}}}+1\leq 1=r_{0}

For $n>0$ set $V_{n}:=\{x_{0},...,x_{n}\}$ . Since $r_{n+1}=r_{n}+\mathbf{1}_{\left\{x_{n+1}\notin V_{n}\right\}}$ two situation occur:

•

If $|x_{n+1}|>{\displaystyle\max_{0\leq k\leq n}\begin{vmatrix}x_{k}\end{vmatrix}}$ then $x_{n+1}\notin V_{n}$ and so

	$\displaystyle\max_{0\leq k\leq n+1}\begin{vmatrix}x_{k}\end{vmatrix}$	$\displaystyle=\begin{vmatrix}x_{n+1}\end{vmatrix}$
		$\displaystyle\leq\begin{vmatrix}x_{n}\end{vmatrix}+m$
		$\displaystyle\leq{\displaystyle\max_{0\leq k\leq n}\begin{vmatrix}x_{k}\end{vmatrix}}+m$

and then

$\displaystyle r_{n+1}$	$\displaystyle=r_{n}+1$
	$\displaystyle\geq\frac{{\displaystyle\max_{0\leq k\leq n}\begin{vmatrix}x_{k}\end{vmatrix}}+2m}{m}$	${\scriptstyle(induction)}$
	$\displaystyle\geq\frac{{\displaystyle\max_{0\leq k\leq n+1}\begin{vmatrix}x_{k}\end{vmatrix}}}{m}+1$

•

If $\begin{vmatrix}x_{n+1}\end{vmatrix}\leq{\displaystyle\max_{0\leq k\leq n}\begin{vmatrix}x_{k}\end{vmatrix}}$ then

r_{n+1}\geq r_{n}\geq{\displaystyle\frac{{\displaystyle\max_{0\leq k\leq n}\begin{vmatrix}x_{k}\end{vmatrix}}}{m}}+1={\displaystyle\frac{{\displaystyle\max_{0\leq k\leq n+1}\begin{vmatrix}x_{k}\end{vmatrix}}}{m}}+1

Thus the property remains true for $r_{n+1}$ , and so (1.5) holds for all $n$ . ∎

Now, we are ready to prove Proposition 4. As usual we assume that $\ell>0$ and $x_{0}=0$ , then there exists $N>0$ such that

n(\ell-\varepsilon)\leq x_{n}\leq n(\ell+\varepsilon)\,\,\,\,\text{for $n>N$ }

where $0<\varepsilon<\ell$ . In particular, by the previous lemma, we obtain

\frac{\lfloor n(\ell-\varepsilon)\rfloor}{nm}\leq\frac{r_{n}}{n}\leq\frac{\lfloor n(\ell+\varepsilon)\rfloor+r_{N-1}}{n}

where $\lfloor\cdot\rfloor$ denotes the ceiling function. Therefore, as $\frac{r_{n}}{n}$ does not exceed $1$ , we conclude the result.

The case $\ell<0$ is similar by considering $-x_{n}$ instead. It is straightforward to verify that if $\ell=0$ then $\frac{r_{n}}{n}\to 0$ with an argument analogous to that in Proposition 2, and the result follows.

A consequence of Proposition 4 is the following.

Proposition 6.

The following statements are equivalent :

1.

$\underset{{\scriptscriptstyle n\rightarrow+\infty}}{\lim}\frac{{\displaystyle\max_{0\leq k\leq n}|x_{n}|}}{n}=0$ .
2.

$\underset{{\scriptscriptstyle n\rightarrow+\infty}}{\lim}\frac{{\displaystyle x_{n}}}{n}=0$
3.

$\underset{{\scriptscriptstyle n\rightarrow+\infty}}{\lim}\frac{{\displaystyle r_{n}}}{n}=0$

Proof.

It follows from

∎

It should be noted that in higher dimensions the Kesten-Spitzer-Whitman theorem still holds, while our Proposition 2 and ensuing results do not. An easy example proves this: take $x_{n}$ to be a sequence which essentially fills the space in ${\mathbb{R}}^{2}$ , for instance one which winds in a spiral shape around the origin; in this case, if no vertices are repeated, then $r_{n}=n$ but $\frac{x_{n}}{n}\to 0$ , and $|x_{n}-x_{n-1}|$ can be taken to be 1. However, we still have a lower bound for ${\displaystyle\liminf_{+\infty}}\frac{r_{n}}{n}$ in terms of $\lim_{n\to\infty}\frac{|x_{n}|}{n}$ . The proof of the following is obtained by the same techniques as for Proposition 4.

Proposition 7.

Let $x_{n}$ be a sequence of $\mathbb{Z}^{d}$ $(d>1)$ such that $\begin{Vmatrix}x_{n+1}-x_{n}\end{Vmatrix}_{2}\leq m$ for some positive integer $m$ . If $\underset{{\scriptscriptstyle n\rightarrow+\infty}}{\lim}\frac{x_{n}}{n}=\ell$ then

\frac{\begin{Vmatrix}{\scriptstyle\ell}\end{Vmatrix}_{2}}{m}\leq\liminf_{+\infty}\frac{r_{n}}{n}

2 The zero-speed case

Many random walks which are recurrent are known to satisfy $\frac{X_{n}}{n}\to 0$ a.s. (e.g. simple random walk in ${\mathbb{Z}}$ and ${\mathbb{Z}}^{2}$ ), and it is natural to ask whether this should hold for deterministic sequences as well. However, this common occurance really is a probabilistic one, and not deterministic. To be precise, we have the following proposition.

Proposition 8.

For every $\ell\in(0,1)$ there exists a sequence $x:=(x_{n})_{n\geq 0}$ such that

(i)

$|x_{n}-x_{n-1}|\leq 1$ for all $n$ .
(ii)

$x_{n}=0$ for infinitely many $n$ .
(iii)

$\underset{{\scriptscriptstyle n\rightarrow+\infty}}{\limsup}\frac{x_{n}}{n}\geq\ell$ .

Proof.

We give an explicit construction for $\ell=\frac{1}{2}$ , and then indicate how it may be extended to arbitrary $\ell$ . Define two sequences $\tau_{n}$ and $t_{n}$ by $\tau_{n}=2\cdot 3^{n}$ and $t_{n}=\frac{\tau_{n}+\tau_{n-1}}{2}$ . Now we define our sequence $x_{n}$ as follows (with $\tau_{-1}=0$ )

x_{k}=\begin{cases}k-\tau_{n-1}&\text{if }\tau_{n-1}\leq k<t_{n}\\ \tau_{n}-k&\text{if $t_{n}\leq k<\tau_{n}$}\end{cases}

Clearly $x_{\tau_{n}}=0$ , so $x_{k}=0$ infinitely often. Note also that $x_{t_{n}}=\frac{\tau_{n}-\tau_{n-1}}{2}$ , so that $\frac{x_{t_{n}}}{t_{n}}=\frac{\tau_{n}-\tau_{n-1}}{\tau_{n}+\tau_{n-1}}=\frac{2\cdot 3^{n}-2\cdot 3^{n-1}}{2\cdot 3^{n}+2\cdot 3^{n-1}}=\frac{1}{2}$ . In order to achieve a larger $\ell<1$ , we let $n_{0}$ be an integer so that

\left(\frac{1+\ell}{1-\ell}\right)^{n_{0}}(\frac{2\ell}{1-\ell})>1

(2.1)

Then, we form our sequence in the same manner as before, but with

	$\displaystyle\tau_{n}$	$\displaystyle:=2\lfloor\left(\frac{1+\ell}{1-\ell}\right)^{n+n_{0}}\rfloor$
	$\displaystyle t_{n}$	$\displaystyle:=\frac{\tau_{n}+\tau_{n-1}}{2}$

It can then be shown that $x_{\tau_{n}}=0$ , so $x_{k}=0$ infinitely often, but we also have $\limsup_{n\to\infty}\frac{x_{t_{n}}}{t_{n}}\geq\ell$ . Details are more difficult that for the $\ell=\frac{1}{2}$ case, and are omitted. ∎

On the other hand, there is a sense in which we may interpret the speed of $x_{n}$ as being deterministic, namely that is controlled by the sequence $(\tau_{k})_{k}$ , which we define to be the time of the $k$ -th visit to $0$ by the sequence $x$ . In particular, we have the following result.

Proposition 9.

If $x\in R$ then

\limsup_{n\to\infty}\frac{|x_{n}|}{n}\leq\limsup_{k}\frac{1}{2}\left(\frac{\tau_{k}}{\tau_{k-1}}-1\right)

Proof.

If we denote by $t_{k}$ the time between $\tau_{k-1}$ and $\tau_{k}$ so that $\begin{vmatrix}x_{t_{n}}\end{vmatrix}$ is maximal, then

\begin{vmatrix}x_{t_{k}}\end{vmatrix}\leq\frac{\tau_{k}-\tau_{k-1}}{2}

Now, every $n$ lies inside some $[\tau_{k_{n}-1},\tau_{k_{n}})$ and therefore

\begin{vmatrix}\frac{x_{n}}{n}\end{vmatrix}\leq\begin{vmatrix}\frac{x_{t_{k_{n}}}}{\tau_{k_{n}-1}}\end{vmatrix}\leq\frac{1}{2}\left(\frac{\tau_{k_{n}}}{\tau_{k_{n}-1}}-1\right),

and the result follows. ∎

Corollary 10.

If a sequence $x\in R$ hits zero at times $\tau_{0}<\tau_{1}<...<\tau_{k}<...$ such that $\frac{\tau_{k}}{\tau_{k-1}}$ converge to $1$ , then $x$ has zero speed.

This shows that if the speed of $x$ is not zero then necessarily $\frac{\tau_{k}}{\tau_{k-1}}$ does not converge to $1$ . As an example, the explicit sequence constructed in Proposition 8 has $\frac{\tau_{k}}{\tau_{k-1}}=3$ for all $k$ .

We now present a final application of these ideas. For the purpose of the next proposition, we consider a random walk to be any stochastic process taking values on the integers.

Proposition 11.

Let $(X_{n})_{n}$ be any recurrent random walk with increments taking values in $\{0,\pm 1\}$ and which returns to zero at times $\tau_{0}<\tau_{1}<...<\tau_{k}<...$ . If the the sequence $(\tau_{k}-\tau_{k-1})_{k}$ is ergodic, then $(X_{n})_{n}$ has zero speed.

Proof.

We have

\begin{vmatrix}\frac{X_{n}}{n}\end{vmatrix}\leq\begin{vmatrix}\frac{X_{t_{k_{n}}}}{\tau_{k_{n}-1}}\end{vmatrix}\leq\frac{1}{2}\left(\frac{\tau_{k_{n}}-\tau_{k_{n}-1}}{\tau_{k_{n}-1}}\right)\leq\frac{1}{2}\left(\frac{\tau_{k_{n}}-\tau_{k_{n}-1}}{\left[{\displaystyle\frac{1}{k_{n}}\times\sum_{j=1}^{k_{n}-1}\tau_{j}-\tau_{j-1}}\right]\times k_{n}}\right)

(2.2)

Now, ${\displaystyle\frac{1}{k_{n}}\times\sum_{j=1}^{k_{n}-1}\tau_{j}-\tau_{j-1}}$ converges a.s. to $E\left(\tau_{1}-\tau_{0}\right)$ which is positive (possibly infinite) by Birkoff’s ergodic theorem, and since the distribution of the r.v $\tau_{k_{n}}-\tau_{k_{n}-1}$ does not depend on $n$ then the right hand side in 2.2 goes to zero as $n$ goes to $\infty$ . ∎

We recover a classical result ([6, p.8]) illustrated by the following corollary.

Corollary 12.

If $(X_{n})_{n}$ is a recurrent Markov chain on ${\mathbb{Z}}$ with increments $0,\pm 1$ (eg. a birth-death chain) then its speed is zero.

Proof.

The inter-return times to zero are independent for a Markov chain. ∎

References

Beiglböck and Siorpaes [2015] M. Beiglböck and P. Siorpaes, “Pathwise versions of the Burkholder–Davis–Gundy inequality,” Bernoulli, vol. 21, no. 1, pp. 360–373, 2015.
Acciaio et al. [2013] B. Acciaio, M. Beiglböck, F. Penkner, W. Schachermayer, and J. Temme, “A trajectorial interpretation of Doob’s martingale inequalities,” Annals of Applied Probability, vol. 23, no. 4, pp. 1494–1505, 2013.
Spitzer [2013] F. Spitzer, Principles of random walk. Springer Science & Business Media, 2013, vol. 34.
Norris [1998] J. Norris, Markov chains. Cambridge University Press, 1998, no. 2.
Shiryaev [1996] A. Shiryaev, Probability. Springer, 1996, vol. 95.
Solomon [1975] F. Solomon, “Random walks in a random environment,” Annals of Probability, vol. 3, no. 1, pp. 1–31, 1975.