0
$\begingroup$

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)?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ @Anthony Quas Shouldn't the time for a walker to cover an interval be at least $\Theta(N^2)$? $\endgroup$
    – user30213
    Commented 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
    Commented 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
    Commented 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$
    – Anthony Quas
    Commented 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
    Commented 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 .