Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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}$. –  mike Sep 28 '12 at 17:26

2 Answers 2

up vote 0 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

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.