3
$\begingroup$

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?

  • 0
    i 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 2

1

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.

1

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.