Slowest initial state for convergence of finite birth-and-death Markov chains

Question

Consider the continuous-time birth-and-death Markov chain on $\{1,\cdots,n\}$ with all rates equal to $1$. Is it true that the convergence to equilibrium, in total variation distance, is slowest when the initial state is an endpoint?

Here is a concrete reformulation: consider the matrix $$ L = \begin{pmatrix} -1 & 1 & 0 & \cdots & 0 \\ 1 & -2 & 1 & \cdots & 0 \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & 1 & -2 & 1 \\ 0 & 0 & 0 & 1 & -1 \end{pmatrix}. $$

The question is whether for every $t>0$, among the rows of $\exp(tL)$, the $\ell_1$-distance to $(\frac{1}{n}, \cdots ,\frac{1}{n})$ is maximal for the first (and last) row.

This is true for small enough $t$ (consider the Taylor expansion of the exponential) and for large enough $t$ (see the answer by Mateusz Kwaśnicki) but I would like an argument working for every $t>0$.

It looks obvious but I have no idea how to prove it.

Answer 1

We denote $\mu = (\frac{1}{n},\cdots,\frac{1}{n})$. First remark : because the convexity of $\ell^1$, for any $t$ the maximum of $\|\exp(tL)\nu-\mu\|_{\ell^1}$ is obtain when $\nu = \delta_x$, $x\in \{1,\cdots,n\}$ so we only have to compare these measures. We now consider the following equivalent system: The markov chain is on $\{1,\cdots,2n\}$ with periodic boundary conditions. ie $$\tilde{L}=\begin{pmatrix} -2 & 1 & 0 & \cdots & 0 &1 \\ 1 & -2 & 1 & 0 & \cdots & 0 \\ 0 & 1 & \ddots & & & \vdots \\ \vdots \\ 0 &&&&\ddots &1\\ 1 & & & &1 & -2\end{pmatrix} $$ with symetric initial condition : $\nu(2n+1-y)=\nu(y)$. As the symetry is conserved : for all $t$ $\nu_t := \exp(t\tilde{L})\nu $ stay symetric. This system is indeed similar to the first one. (with the transformation $\phi : \mathbb{P}(\{1,\cdots,2n\})\rightarrow \mathbb{P}(\{1,\cdots n\})$ $\phi (\nu_t)(k) = \nu_t(k)+\nu_t(2n+1-k)$

As the $\tilde{L}$ is translation invariant for all $t$ we have a kernal $K_t$ $$[\exp(t\tilde{L})\delta_x](y) = K_t(x-y)$$ with $K_t(-k)=K_t(k)=K_t(2n-k)$ for all $k$. Moreover we claim that $K_t(k)$ is decreasing for $k$ in $0,\cdots,(n-1)$.

Let $1\leq i\leq n$ and $\nu^i = \frac{1}{2}(\delta_i+\delta_{2n+1-i})$. $$ \|\nu_t^i-\tilde{\mu}\|_{\ell^1} = \sum_{x\leq 2n} \big|\frac{1}{2}(K_t(x-i)+K_t(x+i-1))-\frac{1}{2n}) \big|$$ We divide the sum in two part $$X_1 = [x: K_t(x-i)\leq \frac{1}{2n} \text{,} K_t(x+i-1)\leq \frac{1}{2n}]\cup [x: K_t(x-i)\geq \frac{1}{2n} \text{,} K_t(x+i-1)\geq \frac{1}{2n}]$$ and $X_2 = \{1,\cdots 2n\}/X_1 $. We have then
$$ \|\nu_t^i-\tilde{\mu}\|_{\ell^1} = \frac{1}{2} \sum_{x\in X_1} \big|K_t(x-i)-\frac{1}{2n}\big|+\big| K_t(x+i-1)-\frac{1}{2n}\big|+\frac{1}{2} \sum_{x\in X_2} \big| |K_t(x-i)-\frac{1}{2n}|-| K_t(x+i-1)-\frac{1}{2n}|\big| \\ = \|K_t - \tilde{\mu}\|_{\ell^1} - \sum_{x\in X_2} \min(| K_t(x+i-1)-\frac{1}{2n}|,| K_t(x-i)-\frac{1}{2n}|) $$ As $K_t$ is monotone in the distance $|x-i|$, $X_1$ and $X_2$ are an union of two segment in $\{ 1,\cdots , 2n\}$. In the particular case of $i=1$, there exists $k_0$ such that $K_t(x-1)\geq \frac{1}{2n}$ for all $1 \leq x\leq k_0$ and $K_t(x-1)< \frac{1}{2n}$ for all $k_0<x < 2n - k_0$. Therefore $K_t(x) \geq \frac{1}{2n}$ for all $0 \leq x\leq k_0-1 $ and $K_t(x)< \frac{1}{2n}$ for all $k_0-1<x < 2n - k_0-1$ and then $X_2 = \{k_0 , 2n - k_0\}$, moreover $$K_t(0)\geq K_t(1)\geq \cdots K_t(k_0-1)\geq \frac{1}{2n} \geq K_t(k_0) \geq \cdots \geq K(n-1) $$ and then $$\min(|K_t(k_0-1)-\frac{1}{2n}|,|K_t(k_0)-\frac{1}{2n}|) = \min_{k\leq 2n} |K_t(k)-\frac{1}{2n}|$$ We finally have $$ \|\nu_t^i-\tilde{\mu}\|_{\ell^1} == \|K_t - \tilde{\mu}\|_{\ell^1} - 2 \min_{k\leq 2n} |K_t(k)-\frac{1}{2n}|$$ and we can conclude that $\|\nu_t^1-\tilde{\mu}\|_{\ell^1}=\max_i \|\nu_t^i-\tilde{\mu}\|_{\ell^1} $

Answer 2

The first non-trivial (i.e. corresponding to the smallest in absolute value, non-zero eivenvalue) eigenvector is $$ v_1 = (\cos((k - \tfrac{1}{2}) \tfrac{\pi}{n}) : k = 11, \ldots, n) ,$$ corresponding to eigenvalue $$ \lambda_1 = -2 (1 - \cos \tfrac{\pi}{n}) . $$ Writing out the eigenvector expansion of $\exp(t L)$, one easily sees that the rows converge to the uniform distribution at rate $\exp(\lambda_1 t)$, with constants given by $v_1(k) v_1(l)$ for row $k = 1, 2, \ldots, n$ and column $l = 1, 2, \ldots, n$.