I take a random walk on a bounded one-dimensional interval of length $N$, with possible walker positions $1$ through $N$. If I start at position $1$, how many steps should it take before my walker is approximately uniformly distributed on the interval? Perhaps we could call this a "mixing" time? Does it require $\Theta(N^2)$ steps, similar to the cover time?
Mixing time for a random walk on an interval
-
0i assume nearest neighbor, all neighbors equally probable. This can be solved exactly, i.e., transition matrix diagonalized fairly neatly, I think the solution is in Feller vol 1. I know the absorbing case was published by kac in the 40's or 50's. i can't remember if second eigenvalue is like $ 1 - \frac 1 n$ or $1 - \frac 1 {n^2}$. – 2012-09-28
2 Answers
Let $t_{ij}$ be the probability of going from position $j$ to position $i$ in one step. Then the distribution of the walker will converge over time to an eigenvector of $T=[t_{ij}]$ with eigenvalue $\lambda_1=1$. The rate at which this happens is governed by $\lambda_2$, the second largest (in absolute value) eigenvalue of $T$: non-uniformity in the initial distribution will decay as $\exp(-(1-\lambda_2)n)$ after $n$ steps.
The bounded walk you describe has $t_{2,1}=1$, $t_{N-1,N}=1$, and $t_{ij}=\frac{1}{2}\delta_{i,j+1}+\frac{1}{2}\delta_{i,j-1}$ for $i\neq 1,N$. As you might expect (since it's translation-independent except at the boundaries), the eigenvectors of this matrix are standing waves with wavelengths compatible with the box: $u_{k}(x)=\cos\left(\pi k \frac{x-1}{N-1}\right),$ where $k=0,1,2,...,N-1$, with corresponding eigenvalues $\lambda_{k}=\cos(\pi k/(N-1))$. The second-largest absolute value is $\cos(\pi/(N-1))$, which is approximately $\frac{1}{2}\pi^2/(N-1)^2$ away from $1$, giving a decay time that is in fact $\Theta(N^2)$.
You should note, however, that there are two eigenvalues of magnitude $1$ for this random walk: one ($+1$) corresponds to uniform distribution, while the other ($-1$) corresponds to an alternating even-odd distribution. Since the walker can never return to its initial position after an odd number of steps, you never achieve true "mixing" with this random walk.
Look into Chapter 12 of the book Markov Chains and Mixing Times by Levin, Peres, and Wilmer, available online here. For a symmetric random walk on the circle of size $n$, the second eigenvalue is $\cos(2\pi/n)\approx 1-({2\pi^2/ n^2})$. They also look at random walks on the line with various boundary conditions.