Spitzer’s Lyapunov Ergodicity

We show that relative entropy decreases for continuous time Markov chains.

Consider aan irreducible continuous time Markov chain with state space ${\mathcal X}$ , $Q$ -matrix $Q$ and stationary distribution $\boldsymbol{\pi}$ . The forward equation for this Markov chain is given by

$\label{Spit:Forward} \frac{d}{dt} \bm{p}(t) = \bm{p}(t) Q.$

Throughout this section we assume that $\boldsymbol{p}(t)$ and $\boldsymbol{q}(t)$ are two solutions to the above system of differential equations.

Recall that the relative entropy between distributions $\boldsymbol{p}$ and $\boldsymbol{q}$ is

$D( \bm{p} ||\bm{q}) = \sum_{x\in {\mathcal X} } p_x \log \frac{p_x}{q_x}$

Ex 1. Show that, for positive numbers $a$ and $b$ ,

$a\log \frac{a}{b} + (b-a) \geq 0$

with equality iff $b=a$ .

Ex 2. Show that for any function $f(y)$ ,

$\sum_{y,x} f(y) Q_{yx} =0$

Ex 3. Show that

$\frac{d}{dt} D(\bm{p}(t) || \bm{q}(t) ) = -\sum_{x,y\in {\mathcal X} } \left( a_y \log \frac{a_y}{a_x} + a_x -a_y \right) q_y(t) Q_{yx}$

where we define $a_x= p_x(t)/q_x(t)$ .

Ex 4. Show that

$\frac{d}{dt} D(\bm{p}(t) || \bm{q}(t) ) \leq 0$

with equality iff $\boldsymbol{p}(t) = \boldsymbol{q}(t)$ .

Ex 5. If $\boldsymbol{\pi}$ is the stationary distribution, then

$\frac{d}{dt}D(\bm{p}(t) || \bm{\pi}) \leq 0\quad \text{and} \quad \frac{d}{dt}D(\bm{\pi} || p(t)) \leq 0.$

(From here standard Lyapunov argument can be used to prove ergodicity.)

Answers

Ans 1. The function $a\log a/b$ is strictly convex. The remaining terms are the tangent to this function at $a=b$ .

Ans 2. Trivial since $\sum_x Q_{yx}=0$ .

Ans 3. Define $a_x = p_x /q_x$ .

$\begin{aligned} \frac{d}{dt} D(\bm{p}(t) || \bm{q}(t) ) = & \sum_x \frac{d}{dt} \left\{ p_x(t) \log \frac{p_x(t)}{q_x(t)} \right\} \\ = & \sum_x \dot{p}_x (t) \log \frac{p_x(t)}{q_x(t)} + \dot{p}_x(t) - \dot{q}_x(t) \frac{p_x(t)}{q_x(t)}\\ =& \sum_{x,y} \left( p_y \log a_x + p_y - q_y a_x \right) Q_{yx}\\ =& \sum_{x,y} \left( a_y \log \frac{a_x}{a_y} + a_y - a_x \right) q_y Q_{yx} \; .\end{aligned}$

In the 3rd equality we apply the forward equation . In the 4th equality we apply [2] with $f(y)=-a_y \log a_y$ .

Ans 4. The inequality holds by applying [1] to [3].

For the equality condition suppose that $\frac{d}{dt} D(\boldsymbol{p}(t) || \boldsymbol{q}(t) ) = 0$ . By irreducibility $\boldsymbol{p}(y)>0$ . Take two states that commute $x,y$ i.e. $Q_{xy}>0$ . For this $x$ and $y$ the term in the sum given in [3] can only be zero if $a_x=a_y$ . By irreducibility, this holds for all pairs thus $\boldsymbol{p}=\boldsymbol{q}$ .