Spectrum of transition matrix for symmetric random walk

Question

I asked this question previously on math.stackexchange.com, where it had little traction.

Consider the symmetric random walk on $\{0,1,…,n\}$ with transition probabilities $P(j→j±1)=1/2$ for $0 < j < n$ and $P(0→0)=P(0→1)=P(n→n)=P(n→n−1)=1/2$. I am interested in the spectrum of the transition matrix (which is symmetric, hence the spectrum is real).

Mathematica suggests that the characteristic polynomial of the transition matrix is of the form $p_n(x)=(1−x)q_n(x)$, where $q_n$ is a polynomial that is odd / even iff $n−1$ is odd / even and that has only simple zeroes. Therefore, the spectrum appears to be a symmetric set of n points from the open unit interval, plus the point $λ=1$.

It occurs to me that this ought to be well known. In particular, the factors $q_n(x)$ in the characteristic polynomials ought to be special.

Does anybody know more?

Answer 1

The previous answer of Pablo Lessa seems to be related to a different problem: with periodic boundary conditions. Your conditions are not periodic.

Your matrix is a special Jacobi matrix, and the characteristic polynomial can be found explicitly.

Let $A$ be your matrix, $x=(x_0,\ldots,x_n)$ an eigenvector with eigenvalue $\lambda$. Then $(A-\lambda)x=0$ gives you $n+1$ linear equations which I enumerate $0$ to $n$. Let us fix arbitrary $\lambda$ and try to solve for $x$. WLOG set $x_0=1$. Then equation $0$ gives $$x_1=2\lambda-1,$$ And the next $n-1$ equations are $$x_{k+2}-2\lambda x_{k+1}+x_k=0,\quad k=0,...,n-2.$$ This is a linear recurrency, and it is solved in the usual way. Let us denote $\lambda=\cos\theta$. The characteristic equation is then $\rho^2-2\cos\theta+1=0$ thus $\rho=\exp(\pm i\theta).$ The general solution is $x_k=c_1\cos k\theta+c_2\sin k\theta$. Substituting $k=0$ and $k=1$ we obtain $c_1=1,c_2=(\cos\theta-1)/\sin\theta$. So $$x_k=\cos k\theta+\frac{\sin k\theta}{\sin\theta}(\cos\theta-1)$$ Or, returning to $\lambda$, $$x_k=T_k(\lambda)+(\lambda-1)U_{k-1}(\lambda),$$ where $T_k$ and $U_k$ are Chebyshev polynomials of the first and second kind, respectively.

Now the equations number $n-1$ and $n$ give two expressions for $x_n$. Equating these two expressions we obtain the characteristic equation: $$(1-2\lambda)(T_n+(\lambda-1)U_{n-1}(\lambda))+T_{n-1}+(\lambda-1)U_{n-2}(\lambda)=0.$$ Probably this can be simplified using the relations between Chebyshev polynomials.

A general reference for Jacobi matrices is the book by Gantmakher and Krein, Oscillation matrices, etc., recently translated by AMS.

Answer 2

This is just a guess more than an answer but I think for large $n$ the $k$-th eigenvalue below $1$ should be more or less

$\lambda_k = 1 - \frac{2\pi}{(n+1)^2}k^2.$

The reasoning behind this guess is that you can consider $2n+2$ evenly distributed points on the unit circle and take the symmetric random walk on them. The projection to the $x$ axis (suppose the points are symmetric with respect to this axis) gives you your random walk.

Let $L_n$ be the operator that acts on functions by averaging the value at the two points at distance $\pi/(n+1)$ from the original point. Then $\frac{2}{\pi}(n+1)^2(L_n - I)$ is a finite difference approximation to the second derivative operator $\Delta$.

The spectrum of $\Delta$ are points the points of the form $-k^2$ for $k \in \mathbb{Z}$ but only the even $k$ should count since we're projecting on the $x$ axis. "Solving for the eigenvalues of $L_n$" (if I did it right) gives the above guess.

Answer 3

The eigenvalues are $$\lambda_j = \cos \left( \frac{j-1}{n} \pi \right), j = 1, \ldots, n$$ I learned this fact from this paper, which gives the following reference for it: Section 16.3, W. Feller. An Introduction to Probability and Its Applications, volume I, Wiley, 1968.

Answer 4

The spectrum of the matrix is computed in the beginning of my preprint:

Rivin, Igor. "Growth in free groups (and other stories)." arXiv preprint math/9911076 (1999).

(there is a published version, too).

Answer 5

You certainly have enough answers by now, but another name for these are the Neumann eigenvalues for the discrete heat equation. You can compute them as you would compute the Neumann eigenvalues for the heat equation on an interval. Consider the even reflection of your random walk about 0. This generates a symmetric random walk on -n,...n with periodic boundary conditions. The transition matrix is circulant and the eigenvalues can be computed directly. Equivalently, one can diagonalize via discrete Fourier transform to obtain the eigenvalues.