# Spectrum of transition matrix for symmetric random walk

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?

-
This doesn't answer your question, but here is a paper discussing random walks (including your example) and eigenvalues of the graph, among other things: cs.elte.hu/~lovasz/erdos.pdf . – Brian Rushton Nov 30 '12 at 14:48
Thank you, this is very useful indeed. – Hans Engler Nov 30 '12 at 15:33

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.

-
@Alexandre: We're talking about the same problem. My point is that if $x = (x_0,\ldots, x_n)$ is an eigenvector for your matrix then $(x_0,\ldots,x_n,x_n,\ldots,x_0)$ is an eigenvector for a more symmetric matrix having 0's on the diagonal an $0.5$ above an below, the first row has a $0.5$ in the last entry and the last row has a $0.5$ in the first entry. The matrix is invariant under cyclic permutations of the variables. Reciprocally, eigenvectors of the big matrix which are of the symmetric form above correspond to eigenvalues of the small matrix. – Pablo Lessa Nov 30 '12 at 19:41
Thanks, Pablo, I understand now. But then you have an additional task of deciding whether each given eigenvalue of the big matrix corresponds to an eigenvector of the special symmetric form? – Alexandre Eremenko Nov 30 '12 at 20:24
Thank you, just what I hoped for. – Hans Engler Nov 30 '12 at 22:18

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.

-
Very interesting approach. – Hans Engler Nov 30 '12 at 22:18

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.

-
Thank you, this is a very helpful reference. – Hans Engler Nov 30 '12 at 22:14

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).

-
Thank you for providing a wider context. – Hans Engler Nov 30 '12 at 22:18

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.

-
Interesting approach, thank you. – Hans Engler Nov 30 '12 at 22:18
For the record, I am saying nothing that Pablo Lessa had not already said earlier. Had I read more carefully before posting I would have realized this. – Aaron Hoffman Nov 30 '12 at 23:22