Imagine I have some Markov process consisting of a biased random walk on the integers, over some interval $[0, L]$, with $+1$ and $-1$ step probabilities of $p$ and $q$, respectively, s.t. $(p + q) = 1$. Here, the walker is reflected at $X = 0$ with probability $p$ (staying in place with probability $(1-p)$), and the walker is reflected at $X=L$ with probability $q$ (staying in place with probability $(1-q)$). We can also imagine the same process where $p=q$ everywhere except at one position where there is some $p \approx \epsilon$ transition probability.

Clarification: Unlike the random walk from (Levin, Peres, and Wilmer), where there is a probability of $\frac{1}{2}$ to fall back to the origin at any point, the random walk I described above can only fall back a step with probability $\frac{p}{q}$. The regime where $\frac{p}{q} = 1 - C$ for small $C$ is of interest to me. I do not understand how $\Theta(1)$ could be asymptotically tight for this?

I strictly initiate the random walk at a fixed position $X = i$ on the interval. How can I analyze the mixing time for the above process. I.e. after how many steps do we have: $||Prob[X=n] - \pi(n)|| \leq C$ for some steady state distribution $\pi$ and some constant $C$? Clearly it can't be $\Theta(N^2)$ like we would expect for an unbiased random walk, since $p \approx \epsilon$ can arbitrarily increase the time to sample states across some "hurdle". I'd expect that the mixing time would have to be an asymptotic function of the lowest probability transition state(s)?


1 Answer 1


For the biased random walk, you can use a grand coupling: take two copies of the walk and make them move the same way (staying put if they can't move in their respective directions). I'll assume $p$ was meant to be the probability of moving to the right, and that $p<\frac12$. For a fixed $i$ (independent of $N$), you should expect a $\Theta(1)$ mixing time (as the expected time to hit 0 from some stationarily chosen initial point is $\Theta(1)$ and each time you hit 0, you expect to get a reduction in distance).

Even if the second particle starts at $N$, you expect a $\Theta(N)$ time.

For the chain with a hurdle, I think you get a similar $\Theta(1)$ time (I'm assuming you're not allowed to vary $\epsilon$)

See Levin, Peres and Wilmer's book for lots more information.

  • $\begingroup$ @Anthony Quas Shouldn't the time for a walker to cover an interval be at least $\Theta(N^2)$? $\endgroup$
    – user30213
    Dec 26, 2012 at 18:56
  • $\begingroup$ @Anthony Quas The "winning streak" in example 4.15 seems convincing in terms of showing a mixing time of $\Theta(N)$. However, I'm having trouble rectifying this with the notion that we need $\Theta(N^2)$ steps to hit a target some distance $N$ from the starting position. $\endgroup$
    – user30213
    Dec 26, 2012 at 19:17
  • $\begingroup$ And computer simulations show for an unbiased walk, that $\Theta(N)$ steps doesn't yield the uniform distribution we would expect. $\endgroup$
    – user30213
    Dec 26, 2012 at 19:22
  • $\begingroup$ To achieve the mixing time, you don't have to cover the whole interval. As an illustration of this, remember that if $N$ is large (and here I'm only talking about the asymmetric case), that the probability of being in the right half of the interval is exponentially small in $N$. Nothing in my answer applies to unbiased random walk. $\endgroup$ Dec 26, 2012 at 19:33
  • $\begingroup$ @Anthony Quas OK, so the argument is that there is an exponential slope causing us to fall towards $0$ (Levin, Peres, and Wilmer give a probability of $\frac{1}{2}$ to hit $0$ at any step), so an asymptotically tight estimate for the number of steps necessary to reach the stationary distribution for the biased walk I described is $\Theta(N^2)$. Ok, that makes sense to me. However, I still think the (sparse) hurdle example is tricky for large $N$, and not necessarily $\Theta(N)$. I don't see where the $\Theta(1)$ estimate comes from... $\endgroup$
    – user30213
    Dec 26, 2012 at 19:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .