**The problem:**

We have a $n$-state Markov chain with arbitrary initial distribution and transition matrix $P$ that is arbitrary except that we know that $P$ has trace $n-1$. Of course $P$ is also a stochastic matrix.

Let $b(n,k)$ denote the suprememum, over all such matrices $P$ and initial distributions, of the total variation distance between the distribution of this chain after $k$ and $k+1$ time steps. I am primarily interested in bounds for fixed $n$ as $k$ goes to infinity. In the remaining description of partial results I will therefore focus on the following question: what is the largest $\alpha \ge 0$ such that $b(n,k)=O(k^{-\alpha})$, where big-oh hides a function of $n$.

For fixed $n$ all matrix norms are equivalent, so it suffices to bound some matrix norm of $P^{k+1} - P^k$ by $O(k^{-\alpha})$. In particular using the vector $\ell_p$ norm $|\cdot|_p$ and its induced matrix norm $\|\cdot\|_p$ it suffices to bound $|(P^{p+1}-P^k)v|_p$ for all vectors $v$ with $|v|_p \le 1$.

I'm using terminology primarily from Horn and Johnson's *Matrix Analysis* book.

**Partial results and discussion:**

One can use Markov chain couplings to show that $\|P^{k+1}-P^k\|_1 = O(1/\sqrt{k})$. (See Lemma 10 in http://www.cs.brown.edu/~ws/papers/regret.pdf .)

All eigenvalues of a stochastic matrix are at most 1 in absolute value and the trace of a matrix is equal to the sum of eigenvalues, so we conclude that all eigenvalues of $P$ have real part between 0 and 1.

Consider the special case of $P$ symmetric. Then $P$ is symmetric then it is orthogonally diagonalizable with real eigenvalues. For any $0 \le \lambda \le 1$ it is easy to show that $|\lambda^{k+1} - \lambda^k| = O(1/k)$, so therefore for symmetric $P$ we have $\|(P^{p+1}-P^k)\|_2 = O(1/k)$.

Consider the special case of circulant matrices, i.e. matrices $P$ where $P_{ij}$ is a function of $i - j \mod n$. The trace restriction implies that the diagonal entries of $P$ are $(n-1)/n$. By Gersgorin disks it follows that all eigenvalues are within $1/n$ of $1-1/n$ in the complex plane. If my calculations are right the maximum over that circle of $|\lambda^{k+1}-\lambda^k|$ is $\Theta(1/\sqrt{nk})$ for $k \gg n$. Finally the eigenvectors for circulant matrices are orthogonal, so we conclude that $\|(P^{p+1}-P^k)\|_2 = \Theta(1/\sqrt{nk})$.

It turns out that circulant matrices are diagonalized by discrete Fourier transform matrices, i.e eigenvector $v_i$ satisfies $(v_i)_j = \omega^{ij}$ where $\omega=e^{2 \pi i / n}$ is a root of unity. This allows us to sharpen the above bounds a bit. One can show that any eigenvalue of $P$ is of the form $1 - 1/n + (1/n)\cdot\sum_i \alpha_i \omega^i$ where $\sum_i \alpha_i = 1$, $\alpha_i \ge 0$ (convex combination), and $\alpha_0 = 1 - 1/n$. For $k \gg n$ one can show that $|\lambda^{k+1}-\lambda^k|$ is $O(n/k)$ for any $\lambda$ of this form.

Given the above results I have a strong suspicion that for general stochastic $P$ with trace $n-1$ we have $\|P^{k+1}-P^k\| = O(1/k)$. Of course you might say that a better conjecture would be limited to matrices $P$ that are unitarily diagonalizable (a.k.a. normal), but I haven't found examples where non-normality makes things worse so I'm conjecturing $O(1/k)$ holds for non-normal matrices as well. One simple example of a non-normal matrix $P$ with $\|P^{k+1}-P^k\|=\Theta(1/k)$ is $P=\left(\begin{array}{cc}1 - \varepsilon & 0 \\ \varepsilon & 1\end{array}\right)$. (This has trace strictly greater than $n-1$, but that's fine as the trace can be corrected be extended by adding two dummy states without significantly changing the problem.)

Extending the above eigenvalue-based proofs to the general case runs into a huge roadblock: eigenvectors are not in general orthogonal. This is a problem because the initial distribution vector may in general have unboundedly large coefficients when translated into the eigenvector basis.

The mixing time of these Markov chains can be unbounded, so techniques for bounding the mixing time are not obviously helpful.

*Edit*: the following example shows that the eigenvectors can have an arbitrarily small angle.
$$P=\left(\begin{array}{ccc}1-\varepsilon & 0 & 0 \\ \varepsilon & 1-\delta & 0 \\ 0 & \delta & 1\end{array}\right)$$

Its (right) eigenvectors are $(\delta-\varepsilon,\varepsilon,-\delta)^T$ , $(0,1,-1)^T$ and $(0,0,1)^T$. As $\delta$ approaches $\varepsilon$ the first and second eigenvectors become arbitrarily close to parallel.

3more comments