I am currently trying to solve the following problem about a discrete Markov chain, and am having some difficulties:
A one dimensional lattice has sites labelled by $n$. There are $N$ sites in total, and we impose periodic boundary conditions. A particle moving on this ring has probability $p_{n}(t)$ to occupy site $n$ at time $t$. When it is at site $n$ at time $t$, it will move to the neighbouring site on its right with probability $r > 0$ and to the neighbouring site on its left with probability $l > 0$, where $l + r < 1$. What is the transition matrix $\mathbf{T}$ for this process?
Construct an appropriate set of right eigenvectors $\mathbf{v}^{(j)}$ of $\mathbf{T}$ using the ansatz: $$\mathbf{v}^{(j)} = \begin{pmatrix}z_{j} & z_{j}^{2} & \dots & z_{j}^{N}\end{pmatrix}^{T}$$
What are the appropriate values of $z_{j}$ and corresponding eigenvalues $\lambda_{j}$ of $\mathbf{T}$. Give an expression for the probability that the particle is at site $n$ at time $t$ if it was at site $1$ at time $t = 0$.
Finding the transition matrix is fairly simple, it should have the form:
$$\mathbf{T}=\begin{pmatrix}1 - l - r & r & 0 & \cdots & l \\ l & 1-l-r & r & \cdots & 0 \\ \vdots & & \ddots & & \vdots \\ r & 0 &\cdots & l & 1-l-r\end{pmatrix}$$
So if we use the ansatz for the right-eigenvector:
$$\mathbf{T}\mathbf{v}^{(j)} = \lambda_{j}\mathbf{v}^{(j)}$$
This implies that:
$$\lambda_{j} z_{j} = (1-l-r)z_{j} + rz_{j}^{2} + lz_{j}^{N} \\ \lambda_{j}z_{j}^{2}=lz_{j} + (1-l-r)z_{j}^{2} + rz^{3} \\ \vdots \\ \lambda_{j}z_{j}^{N} = rz_{j} + lz_{j}^{N-1}+(1-l-r)z_{j}^{N}$$
If we sum each of these equations, we find:
$$\lambda_{j}(z_{j} + \dots + z_{j}^{N}) = z_{j} + \dots + z_{j}^{N} \implies \lambda_{j}(1 + z_{j} + \dots + z_{j}^{N-1}) = 1 + \dots + z_{j}^{N-1}$$
This suggests that either $\lambda_{j} = 1$ or $1 + \dots + z_{j}^{N-1} = 0$. The former implies that $z_{j} = z_{j}^{2} = \dots = z_{j}^{N}$ and so $z_{j} = 1$. The latter can be achieved if $z_{j}$ is an $N-1$th root of unity, so:
$$z_{j} = \exp\left(\frac{i j \pi}{N-1}\right),\qquad j \in \{0,\dots,N-1\}$$
We can find the eigenvalues for these:
$$\lambda_{j}z_{j}^{2} = lz_{j} + (1-l-r)z_{j}^{2} + rz_{j}^{3} \\ \implies \lambda_{j} = lz_{j}^{-1} + (1-l-r) + rz_{j} = l\exp\left(\frac{-ij\pi}{N-1}\right) + (1-l-r) + r\exp\left(\frac{ij\pi}{N-1}\right)$$
In a discrete Markov process we have:
$$\mathbf{p}(t) = \mathbf{T}^{t}\mathbf{p}(0)$$
And so we can easily solve this by moving to the basis where $\mathbf{T}$ is diagonal. However, the eigenvalues look rather complex, and so I think that I have likely done something wrong.
I have not checked the entire derivation, but I would not think the eigenvalues are wrong. It is typical for periodic lattices to have complex exponentials for eigenvalues, as they represent rotation. First term is rotation clockwise with probability $l$, second is staying on the same spot with probability $1 - l - r$, and last rotating counter-clockwise with probability $r$. When you would diagonalize your system and, say, apply two time steps, your eigenvalues will be rised to 2nd power. Lets examine what happens when you rise an eigenvalue to the 2nd power
$$ \lambda_j^2 = l^2 \exp(-2i\omega_j) + 2l(1-l-r) \exp(-i\omega_j) + (2lr + (1-l-r)^2) \\ + 2r(1-l-r) \exp(i\omega_j) + r^2 \exp(-2i\omega_j) $$ where $\omega_j = \frac{jπ}{N−1}$
The terms denote moving clockwise twice, clockwise once and staying or vice versa, staying twice or moving back and forth, moving counter-clockwise and staying or vice-versa, and moving counter-clockwise twice. It can be seen that each eigenvalue represents the probability distribution of a particle originally located at jth node after a few iterations. The position is encoded into the complex phase.