Consider a random walk on the integers where the probability of transitioning from $n$ to $n+1$ is $p_n$ (and of course, the probability of transitioning from $n$ to $n-1$ is $1-p_n$); we assume all $p_n$ are strictly less than $1$. Note that the probability of going right is position-dependent, and we certainly do not assume that all $p_n$ are the same. Suppose we know that this random walk is pretty well concentrated; for example, let us assume that we know that for all $c \geq 0$ and for all $t$ large enough, $$P(|X(t) - (1/3)t| \geq c \sqrt{t}) \leq e^{-c^2}$$ where $X(t)$ is the state of the walk after $t$ steps.

Now suppose we increase every $p_n$ by $\epsilon$ (and correspondingly decrease the probability of transitioning from $n$ to $n-1$ by $\epsilon$), where $\epsilon$ is some number such that $p_n + \epsilon < 1$ for all $n$. Let $Y(t)$ be the state of the new chain after $t$ steps. My question is: does a similar concentration result hold for $Y(t)$?

It seems very intuitive that $Y(t)$ should concentrate around $(1/3)t + 2 \epsilon t$.

P.S. I asked this math.SE a few days ago without any answer.

  • 2
    $\begingroup$ I recommend a different title. I only clicked on it to vote to close because I assumed you were asking ``what happens if at each $n$, the probability of going right is $p>1/2$'' which is of course well understood. The fact that your probability changes based on which $n$ you're at should probably be highlighted. $\endgroup$ Commented Feb 27, 2013 at 2:19
  • $\begingroup$ I added a sentence emphasizing that all $p_n$ are not the same. About the title, I'm not sure what else captures my question in a pithy way. $\endgroup$
    – yves
    Commented Feb 27, 2013 at 2:22
  • $\begingroup$ Stick the words "position dependent" in there somewhere? $\endgroup$
    – Lee Mosher
    Commented Feb 27, 2013 at 13:36
  • $\begingroup$ Should the assumption hold for all $c$? Is it essential that the walk moves to the right on average (like $(1/3)t$ in your example) our would a movement to the left or a stationary concentration around $0$ be permitted? (In the last cases there would probably be easy counterexamples when some $p_n$ is changed from 0 to $\epsilon$.) $\endgroup$ Commented Feb 27, 2013 at 17:04
  • $\begingroup$ I threw in the words "position dependent" in there, and specified that the assumption should hold for all $c$ and for all $t$ large enough. $\endgroup$
    – yves
    Commented Feb 28, 2013 at 0:36

1 Answer 1


There's no reason to believe that the new speed will be $2 \epsilon$ more then the old speed. To give a concrete example, take $\epsilon=0.01$ and let the environment be $p_n=0.01$ when $n$ is a multiple of 100, and $p_n=0.98$ otherwise.

How does $X_t$ behave? for most $n$'s (but not most of the time!) it has a speed very close to 1, so it takes roughly a 100 steps to cover the gap between multiples of 100. But when $n$ is a multiple of 100, it takes 100 trials, on average, to pass that obstacle, each trial consists of a little over 2 step, on average. Al in all, it takes about 100+100*2=300 steps, on average, to cover each segment of length 100, so the speed is about 1/3, and it should be pretty straightforward to see that there should be concentration.

What happens when we add $\epsilon=0.01$ to all $p_n$? In the non-100-multiples, not much. The speed is slightly closer to 1. But it now takes only 50 trials, on average, to pass each 100-multiple obstacle. So it now takes roughly 100+50*2=200 steps to cover that segment and the speed is now roughly 1/2.

By alternating these kind of "trap segments" with segments consisting of $p_n=2/3$, we can easily get a $Y_t$ which does not have an asymptotic speed at all, or that does have a speed, but the convergences to that speed is rougher then expected.

  • $\begingroup$ The question did not ask for the existence of a speed originally. Maybe $X(t)$ is concentrated around $f(t)$ for some function $f$. If we assume that $f(t)$ increases unboundedly, is there an example where the random walk is concentrated, but the modified random walk is not concentrated (around a different function $f'(t)$)? $\endgroup$ Commented Feb 28, 2013 at 13:24
  • $\begingroup$ You're right. I'll think about it. $\endgroup$ Commented Mar 1, 2013 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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