# Bounds on $||P^{k+1} - P^k||$ for $n$ by $n$ stochastic matrix $P$ with trace $n-1$ and integer $k>>n$.

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 >> 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)*\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 >> 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 - \epsilon & 0 \\ \epsilon & 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-\epsilon & 0 & 0 \\ \epsilon & 1-\delta & 0 \\ 0 & \delta & 1\end{array}\right)$$

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

-
Your assumptions tell us that such matrices $P$ don't deviate much from diagonal form, thus are "almost normal". Perhaps something could be proved about the angles between eigenspaces. –  Denis Serre Nov 8 '10 at 7:23
Unfortunately the angles between eigenspaces can be arbitrarily small. I just added an example to the bottom of the question showing this. –  Warren Schudy Nov 8 '10 at 18:09
That example suggests the following idea: try to show that the angle between two eigenvectors is at least some function of the difference in the corresponding eigenvalues. Hmmm. –  Warren Schudy Nov 8 '10 at 18:23
I created another question asking for techniques to lower bound the angle between eigenvectors of a non-normal matrix. Hopefully the answer to that question may give me some ideas on what to try next. –  Warren Schudy Nov 8 '10 at 19:12
Here's the link to that question: mathoverflow.net/questions/45342/… –  Warren Schudy Nov 8 '10 at 19:12

OK, I think I have a full answer at this point, so let me post it.

Step 1. (algebra).

If $P$ is an $n\times n$ stochastic matrix and $\lambda$ is an eigenvalue of $P$ with $|\lambda|=1$, then $\lambda^k=1$ for some $k\le n$ and $1,\lambda,\lambda^2,\dots\,\lambda^{k-1}$ are eigenvalues of $P$.

Indeed, let $x$ be an eigenvector. WLOG, $\lambda\ne 1$. Let $S=\{j:|x_j|=\max_k|x_k|\}$. Then if $i\in S$ and $p_{ij}>0$, then $j\in S$. Now, if $i\in S$ and $p_{ij}>0$, then $x_j=\lambda x_i$. Thus, if we have some entry in $x$, we also have $\lambda^k$ times this entry for every $k$, but the number of different entries is at most $n$. Moreover, we can assume that one of the entries is $1$ and split the indices in $S$ into groups $S_m$ by the rule $j\in S_m$ iff $x_j$ is in the half-open counterclockwise arc from $\lambda^m$ to $\lambda^{m+1}$ so that $i\in S_m$, $p_{ij}>0$ imply $j\in S_{m+1}$. From here we immediately see that $P-\lambda^qI$ is not invertible for every $q$ (the $S$-block annihilates the vector $y_j=\lambda^{qm}$ for $j\in S_m$ and the full determinant has the determinant of the $S$-block as a factor. Thus, all powers of $\lambda$ are eigenvalues.

Step 2. (compactness argument).

Consider a convergent sequence $P_k$ of $n\times n$ stochastic matrices with the limit $P$. Assume that $P_k$ have eigenvalues $\lambda_k$ and $\lambda_k$ are not contained in any Stolz angle. Then we may assume that $\lambda_k\to\lambda$, $|\lambda|=1$. Clearly, $\lambda$ is an eigenvalue of $P$. If $\lambda\ne 1$, then $P$ has several eigenvalues summing to $0$ (powers of $\lambda$), so $\operatorname{Tr} P\le n-2$, which makes it not a limit point of your set. But If $\lambda=1$, it is even worse, because, if $\lambda_k$ approach $1$ tangentially, then $\lambda_k^{m_k}$ can tend to any point on the unit circle but they are also eigenvalues of $n\times n$ stochastic matrices (powers of $P_k$) and so are their limits. Thus, we have some fixed (but depending on $n$) Stolz angle, containing all the eigenvalues of your matrices.

Step 3. (harmonic analysis)

Let $f(m)=\sum_{k=1}^n c_k\lambda_k^m$ for $m\ge 0$ and $0$ for $m<0$ where $\lambda_k$ lie in some fixed Stolz angle $A$. Then $$Vf=\sum_{m\in\mathbb Z}|f(m+1)-f(m)|\le C(A,n)\max_m |f(m)|$$

Proof:

We begin with a

Complex analysis lemma

Let $F(z)=\sum_{k=1}^n c_k e^{\mu_k}z$ where $\mu_k\in\mathbb C$, $|\mu_k|\le 1$. Then $F$ has at most $C(n)$ zeroes in the unit disk.

Proof: Let $m$ be the maximum of $|f|$ over the unit disk. Then the first $n$ derivatives at the origin are bounded by $C(n)m$. But $\Phi(t)= F(zt)$ ($|z|=1$) satisfies an $n$-th order differential equation $\Phi^{(n)}=\sum_{k=0}^{n-1}b_k\Phi^{(k)}$ with coefficients $b_k$ obtained by expansion of the polynomial $\prod_{k=1}^n (x-z\mu_k)$, which are bounded by $2^n$, say. The standard ODE theory implies that $\Phi$ is bounded by $C'(n)m$ on $[-2,2]$, so the ratio of the maximum of $F$ over the disk of radius $2$ and over the unit disk is bounded, which is enough to control the number of zeroes in the unit disk (each Blaschke factor moves it up fixed number of times). Rescaling and covering, we conclude that if $|\mu_k|<\mu$, then there may be only $C(n,K)$ zeroes in the disk of radius $K/mu$.

Now,

Induction

If $n=1$, the claim is obvious: the maximum is just $c_1$ and $|\lambda_1^k-\lambda_1^{k+1}|\le C(A)(|\lambda_1|^k-|\lambda_1|^{k+1})$

Let $n>1$. Write $\lambda_k=e^{-\mu_k}$ with $|\mu_k|\le C(A)\operatorname{Re\mu_k}$. Let $\mu=\max|\mu_k|=\mu_n$. Note that $f$ is the trace of $F(z)=\sum_{k=1}^n c_ke^{-\mu_k z}$ on integers. The derivative of the real or imaginary part of $F(t)$ can have only $C(2n,K)$ zeroes on $[0,K/\mu]$, so the real and the imaginary parts have a bounded number of intervals of monotonicity there whence $f$ has variation dominated by its maximum on $[0,K/\mu]$. Now, choose $K=K(A)$ so that $\gamma=\lambda_n^N$ is less than $1/2$ in absolute value where $N\approx K/\mu$. The function $g(m)=f(m+N)-\gamma f(m)$ for $m\ge 0$ and $0$ for $m<0$ is bounded by $2\max|f|$ and has one term less. Thus, by the induction assumption, $Vg\le C(n)\max|f|$.

To recover $f$ from $g$, note that $f(m)-\gamma f(m-N)=G(m)$ where $G(m)=g(m-N)$ for $m\ge N$ and $G(m)=f(m)$ for $m\le N$. Note that $VG$ is still under control because we have bounded both $Vg$ and the part of $Vf$ corresponding to the interval $[0,N]$. Now it remains to iterate this recurrence to get $f(m)=G(m)+\gamma G(m-N)+\gamma^2 G(m-2N)+\dots$ and to use the shift invariance of and the triangle inequality for the total variation.

Step 4. (the end)

Each entry of the matrix $P^k$ is of this form (assuming that the eigenvalues are distinct, which is a dense case). Thus, the total variation of each entry is bounded by some $C(n)$ depending on $n$ only. This is equivalent to $\sum_k\|P^k-P^{k+1}\|\le C(n)$ but the sequence of norms ($\ell^\infty$) is non-increasing, so it is $O_n(k^{-1})$.

Feel free to ask questions :). I suspect this all is written in some obscure textbooks but to do the literature search now is beyond my abilities.

-
The Lemma that is step 3 seems like it should assume some upper-bound on the $c_k$ that is a function of $A$ and $n$ only. Is that right? –  Warren Schudy Dec 23 '10 at 19:05
If my previous comment is correct then I don't immediately see how you can say that each entry of matrix $P^k$ can be written in the form $f(m) = \sum c_k \lambda_k^m$ with the $c_k$ bounded by a function of $n$. Diagonalization of $P$ gives such a form but how do you bound the $c_k$ independent of $P$? –  Warren Schudy Dec 23 '10 at 19:11
$c_k$ are not controlled separately, only the full sum, which is just the matrix entry (bounded by $1$). –  fedja Dec 23 '10 at 19:17
Never mind the previous two comments. I had somehow missed the $\max_m |f(m)|$ factor on the right hand side of step 3. –  Warren Schudy Dec 23 '10 at 19:22
Can you suggest somewhere (e.g. a book) I can read about Stolz angles and their uses? I see the definition you gave in a comment but am otherwise ignorant about them. –  Warren Schudy Dec 23 '10 at 19:32