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

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.

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. 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 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}$$

• Thanks a lot RaphaelB4, that's really a very nice argument! Commented Jun 16, 2019 at 19:24

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

• This seems to answer the question for $t$ large enough. Correct? Commented Jun 12, 2019 at 13:51
• @GuillaumeAubrun: Ah, right, I did not notice that the question asked for all $t > 0$. Sorry! Commented Jun 12, 2019 at 18:54