Consider a 2-state Markov chain with states $X_1$ and $X_2$, and rates $r_{12} = \lambda_2$ and $r_{21} = \lambda_1$:

Let the stationary distribution of the Markov chain be $\pi_1$ and $\pi_2$ satisfying $\pi_1\lambda_2 = \pi_2\lambda_1$. Without loss of generality one can take $\lambda_1 = \pi_1$ and $\lambda_2 = \pi_2$.

Let $p(t) = (p_1(t),p_2(t))$ be the probability density at time t, which evolves as follows $\dot{p_1}(t) = -\dot{p_2}(t) = p_2\lambda_1 - p_1\lambda_2$. The KL-Divergence between the probability density and the stationary distribution is

$D({p_1,p_2}||{\pi_1,\pi_2}) = p_1\log( {\frac{p_1}{\pi_1}}) + p_2\log({\frac{p_2}{\pi_2}}) -p_1 -p_2 + \pi_1 + \pi_2$ $= \pi_1 (\frac{p_1}{\pi_1} \log(\frac{p_1}{\pi_1}) - (\frac{p_1}{\pi_1} - 1)) + \pi_2 (\frac{p_2}{\pi_2} \log(\frac{p_2}{\pi_2}) - (\frac{p_2}{\pi_2} - 1))$

and its time derivative

$$\dot{D}({p_1,p_2}||{\pi_1,\pi_2}) = \dot{p_1}\log( {\frac{p_1}{\pi_1}}) + \dot{p_1}\log({\frac{p_1}{\pi_1}}) = -\pi_1\pi_2\left(\frac{p_1}{\pi_1} - \frac{p_2}{\pi_2}\right)\left(\log\frac{p_1}{\pi_1} - \log\frac{p_2}{\pi_2}\right) \leq 0$$

Notice that $D({p_1,p_2}||{\pi_1,\pi_2}) \rightarrow 0$ as $t \rightarrow \infty$ or $(p_1,p_2) \rightarrow (\pi_1,\pi_2)$

We are interested in the ratio $h(t) = -\frac{\dot{D}({p_1,p_2}||{\pi_1,\pi_2})}{D({p_1,p_2}||{\pi_1,\pi_2})}$ and would like to find a positive lowerbound in order to show exponential decrease of the KL-Divergence.

Consider the limit $\lim_{t \rightarrow \infty}{h(t)}$ where both $\dot{D}({p_1,p_2}||{\pi_1,\pi_2})$ and $D({p_1,p_2}||{\pi_1,\pi_2})$ go to zero. One can verify that all derivatives of $p_1(t)$, $p_2(t)$ and $D({p_1,p_2}||{\pi_1,\pi_2})$ vanish as $t$ approaches $\infty$ hence L’Hôpital’s rule can’t be applied.

To find the above limit let $p_1 = \pi_1(1 + \delta)$ and $p_2 = \pi_2(1 - \delta')$, and using the probability conservation law $p_1 + p_2 = \pi_1 + \pi_2 =1$ we have $\delta'\pi_2 = \delta\pi_1$.

$$h(t) = \frac{\pi_1\pi_2\left(\frac{p_1}{\pi_1} - \frac{p_2}{\pi_2}\right)\left(\log\frac{p_1}{\pi_1} - \log\frac{p_2}{\pi_2}\right)}{ \pi_1 (\frac{p_1}{\pi_1} \log(\frac{p_1}{\pi_1}) - (\frac{p_1}{\pi_1} - 1)) + \pi_2 (\frac{p_2}{\pi_2} \log(\frac{p_2}{\pi_2}) - (\frac{p_2}{\pi_2} - 1))}$$

substitute $\frac{p_1}{\pi_1} = 1 + \delta$ and $\frac{p_2}{\pi_2} = 1 - \delta\frac{\pi_1}{\pi_2}$ in the above equation to get

$$h(t) = \frac{\pi_1\pi_2 \delta (1 + \frac{\pi_1}{\pi_2})(\log(1 + \delta) - \log(1 - \frac{\pi_1}{\pi_2}\delta))}{ \pi_1( (1+\delta)\log(1+\delta) - \delta ) + \pi_2( (1-\frac{\pi_1}{\pi_2}\delta)\log(1-\frac{\pi_1}{\pi_2}\delta) + \frac{\pi_1}{\pi_2}\delta )}$$

Using Taylor series approximation $\log(1+x) = x - \frac{x^2}{2}$, for small values of $\delta$ we get

$$h(t) = \frac{2\pi_1\pi_2(1 + \frac{\pi_1}{\pi_2})^2 (1 - \frac{\delta}{2}(1 - \frac{\pi_1}{\pi_2}) )}{\pi_1(1 - \delta) + \pi_2(\frac{\pi_1}{\pi_2})^2(1 + \delta\frac{\pi_1}{\pi_2})}$$

$$\lim_{t \rightarrow \infty}{h(t)} = \lim_{\delta \rightarrow 0}{h(t)} = \frac{2(\pi_1 + \pi_2)^2}{\pi_1 + \pi_2} = 2$$

---

Share this on → Tweet

---

« What's your go-to joke?