3
$\begingroup$

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?

  • 0
    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)2012-04-24
  • 0
    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.2012-04-24
  • 0
    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.2012-04-24
  • 0
    Do you know a simple argument showing that the random walk hits $(0,\ldots,0)$ almost surely?2012-04-25
  • 0
    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..2012-04-25

2 Answers 2