Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am looking at a discrete-time random walk on $(\mathbb{Z}^{+})^n$, where $\mathbb{Z}^{+}:=\{0,1,2,\dots\}$ and $n\in\mathbb{N}$. At any time, the random walk chooses a uniformly random co-ordinate and then either walks up (by 1) w.p. $p<\frac{1}{2}$ or tries to walk down (by 1) w.p. $1−p$, so nothing happens if he is already at the boundary. I would like to show that this random walk has exponential ergodicity, that is, $$P(\text{not returned to $(0,...,0)$ by time }t)\leq e^{-\eta t}$$for some constant $\eta$. Any hints on how I might do this?

Thanks for your help, DW

share|improve this question
Maybe try to consider it in one dimension first and then generalize? Each directional movement is independent according to you, so you could multiply together the one dimensional cases n times(with some adjustment for the fact that you "skipped a turn" going in another coordinate direction) –  Andrew Apr 24 '12 at 3:33
This is my initial idea. The result holds for $n=1$ either from standard large deviation arguments (since the increments are independent and have negative drift) or standard birth-death chain results. So I am thinking about the $n=2$ case as induction should be easy. –  Derek Apr 24 '12 at 9:25
I like the first suggestion. The sum of the co-ordinates is a simple random walk with negative drift until you hit the boundary, where you skip a few. The hitting time should be dominated by hitting time of simple plus a sum of geometrics for the skipping. The number of geometrics you sum can't be more than the hitting time, at most one for each step in the process. A sum of geometrics where summand has exponential tails also has exponential tails. –  mike Apr 24 '12 at 12:25
Do you know a simple argument showing that the random walk hits $(0,\ldots,0)$ almost surely? –  Did Apr 25 '12 at 16:52
Hi Didier, I don't quite yet. I'm attempting Mike's suggestion, and will post some thoughts after a good long try at this.. –  Derek Apr 25 '12 at 22:21

2 Answers 2

The $\mathbf{1}$-Dimensional Problem

According to the result here, the number of unilateral walks of type-$k$ (the number of strings of $k\;$ "$+1$"s and $k\;$ "$-1$"s whose partial sums are never negative) is $$ \frac{1}{k+1}\binom{2k}{k}\tag{1} $$ In the same article, it is shown that $$ \frac{1-\sqrt{1-4x}}{2x}=\sum_{k=0}^\infty\frac{1}{k+1}\binom{2k}{k}x^k\tag{2} $$ A walk of length $2k+2$ would be a "$+1$" followed by a walk of type $k$ and finished with a "$-1$" resulting in a probability of $$ \frac{1}{k+1}\binom{2k}{k}p^{k+1}(1-p)^{k+1}\tag{3} $$ Plugging $(3)$ into $(2)$ yields a total probability of $p$, which is exactly as expected since there is only a probability $p$ of an initial "$+1$".

To compute the probability of a walk of length at least $2m+2$, sum $(3)$ for $k\ge m$. For this, we will use Stirling's Approximation to get $$ \begin{align} \binom{2k}{k} &=\frac{4^k}{\sqrt{\pi k}}\left(1-\frac{1}{8k}+O\left(\frac{1}{k^2}\right)\right)\\ &\le\frac{4^k}{\sqrt{\pi k}}\qquad\text{for }k\ge1\tag{4} \end{align} $$ Plugging $(4)$ into $(3)$ and summing for $k\ge m$ yields that the probability of a walk of length at least $2m+2$ is $$ \begin{align} \sum_{k=m}^\infty\frac{1}{k+1}\binom{2k}{k}p^{k+1}(1-p)^{k+1} &\le\sum_{k=m}^\infty\frac{1}{k+1}\frac{4^k}{\sqrt{\pi k}}p^{k+1}(1-p)^{k+1}\\ &\le\frac{p(1-p)}{m\sqrt{\pi m}}\sum_{k=m}^\infty4^kp^{k}(1-p)^{k}\\ &=\frac{p(1-p)m^{-3/2}}{\sqrt{\pi}(1-2p)^2}(4p(1-p))^m\tag{5} \end{align} $$ Bound $(5)$ is in the form desired when $p<\frac12$.

Letting $t=2m+2$ in $(5)$, we get that the probability of a walk of length at least $t\ge4$ is no greater than $$ \frac{1}{4\sqrt{\pi}(1-2p)^2}(4p(1-p))^{t/2}=\frac{1}{4\sqrt{\pi}(1-2p)^2}e^{-\eta\,t}\tag{6} $$ where $\eta=-\frac12\log(4p(1-p))>0$ when $0<p<\frac12$.

As has been pointed out, I need to rework the $n$-dimensional extension.

share|improve this answer
Doesn't $f$ stay the same if the walk tries to walk down and can't? Also, the result seems rather implausible, since one might expect that walks will take longer to return to the origin if they have more directions in which they have to return simultaneously to reach the origin. –  joriki Apr 25 '12 at 5:58
@Joriki: Thanks. I had worried about that part earlier. I was working on the $n$-dimensional case on my walk last night, and forgot about the edge cases. I have removed the $n$-dimensional case for reworking. –  robjohn Apr 25 '12 at 8:21
On your random walk? :-) –  joriki Apr 25 '12 at 9:06

Caveat: This is a partial answer, restricted to the regime $p\lt1/(n+1)$.

For every $x$ in $(\mathbb Z^+)^n$, let $|x|$ denote the sum of the coordinates of $x$ and $z(x)$ the proportion of coordinates $i$ such that $x_i=0$. Let $(X_t)_t$ denote the Markov chain in $(\mathbb Z^+)^n$, starting from $X_0\ne0$, and $T$ the first hitting time of $0$. For every $a\ne0$, $$ \mathrm E(a^{|X_{t+1}|}\mid\mathcal F^X_t)=a^{|X_t|}\cdot n^{-1}\sum_{i=1}^n\left(pa+(1-p)a^{-1}[X_t^{(i)}\ne0]+(1-p)[X_t^{(i)}=0]\right), $$ thus, $\mathrm E(a^{|X_{t+1}|}\mid\mathcal F^X_t)=a^{|X_t|}b(X_t)$, where $$ b(x)=pa+(1-p)a^{-1}(1-z(x))+(1-p)z(x). $$ Assume that $a\gt1$, then $b(x)$ is maximal when $z(x)\leqslant1-n^{-1}$ is maximal, that is, for every $x\ne0$, $b(x)\leqslant c(a)$ with $$ c(a)=pa+(1-p)a^{-1}n^{-1}+(1-p)(1-n^{-1}). $$ Hence $(M_t)_{t\leqslant T}$ is a positive supermartingale, where $M_t=a^{|X_t|}c(a)^{-t}$. In particular, $\mathrm E(M_T)\leqslant M_0$, that is, for every $x\ne0$, $$ \mathrm E_x(c(a)^{-T})\leqslant a^{|x|}. $$ If, for some $a\gt1$, $c(a)\lt1$, this yields the exponential control $$ \mathrm P_x(T\geqslant t)\leqslant c(a)^t\mathrm E_x(c(a)^{-T})\leqslant c(a)^ta^{|x|}, $$ hence we are done since one can relate the distribution of $T$ starting from $X_0=0$ to the distribution of $T$ starting from any neighbour $x$ of $0$, namely, $$ \mathrm P_0(T\geqslant t+1)=p\mathrm P_x(T\geqslant t)\leqslant pac(a)^t. $$ Finally, $c(1)=1$ and $c'(1)=p-(1-p)n^{-1}$ hence we are done for every $p\lt1/(n+1)$.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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