5
$\begingroup$

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.

$\endgroup$
3
+200
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks a lot RaphaelB4, that's really a very nice argument! $\endgroup$ – Guillaume Aubrun Jun 16 at 19:24
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This seems to answer the question for $t$ large enough. Correct? $\endgroup$ – Guillaume Aubrun Jun 12 at 13:51
  • 1
    $\begingroup$ @GuillaumeAubrun: Ah, right, I did not notice that the question asked for all $t > 0$. Sorry! $\endgroup$ – Mateusz Kwaśnicki Jun 12 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.