# How does changing the transition probabilities affect the concentration of a position-dependent random walk?

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.

-
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. – David White Feb 27 '13 at 2:19
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. – yves Feb 27 '13 at 2:22
Stick the words "position dependent" in there somewhere? – Lee Mosher Feb 27 '13 at 13:36
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$.) – Günter Rote Feb 27 '13 at 17:04
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. – yves Feb 28 '13 at 0:36

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.
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)$)? – Günter Rote Feb 28 '13 at 13:24