Mixing time for a random walk on an interval 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?
 A: 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.   
A: 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.
