Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$. Suppose we know that this random walk is pretty well concentrated; for example, let us assume that we know that $$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$.

share|cite|improve this question

NOTE: This is totally wrong - see comments.

Let $E(t)$ be the one-way random walk that adds one to its current state with probability $\epsilon$ and remains in its current state with probability $1-\epsilon$. Is it not true that $Y(t) = X(t) + E(t)$ exactly? - that is, the distributions of the random variables $Y(t)$ and $X(t) + E(t)$ are exactly the same?

Assuming I'm right that they are the same, then a concentration result for $Y$ follows from the hypothesized concentration result for $X$ and the standard concentration that can be calculated for $E(t)$: if $Y(t) - (\frac13+\epsilon)t$ exceeds $c\sqrt t$, then one of $X(t) - \frac13t$ or $E(t) - \epsilon t$ must exceed $\frac c2\sqrt t$.

share|cite|improve this answer
There is no reason for the distribution of $Y(t)$ to be the same as the distribution of $X(t)+E(t)$, as far as I can tell. What makes this "obvious" problem difficult for me is the dependency created - depending on whether $E(t)=0$ or $E(t)=1$ the random walk will take a different probability to go right. – yves Feb 23 '13 at 2:06
Sigh. You're totally right. $X(t)$ and $Y(t)$ are both supported on integers with the same parity as $t$, while neither $E(t)$ nor $X(t)+E(t)$ have this property. – Greg Martin Feb 23 '13 at 4:47

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.