Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
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
show 1 more comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
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
    
You're right. I'll think about it. –  Ori Gurel-Gurevich Mar 1 '13 at 7:27
add comment

Your Answer

 
discard

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.