Kris's Research Notes

October 12, 2010

The H-Theorem for a Time-Reversible Markov Chain.

Filed under: Stat. Mech for SOS Model — Kris Reyes @ 6:16 pm

For a countable set of states $\mathcal X$ and an evolving distribution $P(t; x)$ on $\mathcal X$, we may define the entropy $S$ at time $t$ by

$\displaystyle S(t) = -\sum_{x \in \mathcal X} P(t;x) \log P(t;x).$

The H-Theorem asserts that (with some assumptions) $\frac{dS}{dt} \geq 0$; the entropy is always non-decreasing. Calculating this quantity, we see

$\displaystyle \frac{dS}{dt} = -\sum_{x \in \mathcal X} \frac{dP(t;x)}{dt}\log P(t;x) + \frac{dP(t;x)}{dt}.$

Since $\sum_{x \in \mathcal X} \frac{dP(t;x)}{dt} = 0$ we see we have

$\displaystyle \frac{dS}{dt} = -\sum_{x \in \mathcal X} \frac{dP(t;x)}{dt} \log P(t;x).$

We assume $P(t)$ describes a Continuous Time Markov Chain. That is, we assume there exists transition rates $R(x,y)$ for distinct $x, y \in \mathcal X$ such that $P(t)$ evolves according to:

$\displaystyle \frac{dP(t;x)}{dt} = \sum_{\stackrel{y\in \mathcal X}{y\neq x}} P(t;y)R(y,x) - P(t;x)R(x,y).$

If we write

$\displaystyle R(x,x) = -\sum_{\stackrel{y\in \mathcal X}{y\neq x}} R(x,y),$

we may write the above as

$\displaystyle \frac{dP(t;x)}{dt} = \sum_{y\in \mathcal X} P(t;y)R(y,x).$

If we consider the $R$ as an infinite dimensional $|\mathcal X| \times |\mathcal X|$ matrix and similarly consider $P(t)$ as an infinite dimensional vector, we may write the above compactly in matrix notation:

$\displaystyle \frac{dP}{dt} = P^TR$.

We also assume the chain is time reversible. That is, there exists a distribution $\pi(x)$ on $\mathcal X$ such that the  detailed balance property holds:

$\pi(y)R(y,x) = \pi(x)R(x,y)$.

For example, suppose $\mathcal X$ was finite and the rates $R$ were symmetric. Then the corresponding chain is time-reversible and the requisite $\pi$ is the uniform distribution on $\mathcal X$. It is easy to see the H-theorem holds in this context, since we have

$\displaystyle \frac{dP(t;x)}{dt} = \sum_{y\neq x \in \mathcal X} R(x,y)(P(t;y) - P(t;x)),$

so that

$\displaystyle \frac{dS}{dt} = -\sum_{\stackrel{x,y\in \mathcal X}{y\neq x}} \log P(t;x) R(x,y)(P(t;y) - P(t;x)).$

Note that in this sum, both the terms

$-R(x,y)\log P(t;x)(P(t;x) - P(t;y)),$

and

$R(x,y)\log P(t;y)(P(t;x) - P(t;y)).$

occur. Grouping them together, and summing over $x,y$, we get:

$\displaystyle \frac{dS}{dt}= \frac{1}{2}\sum_{x,y \in \mathcal X}R(x,y)\left(\log P(t;x)-\log P(t;y)\right)\left(P(t;x) - P(t;y)\right).$

Each term in the sum is non-negative, so that $\frac{dS}{dt} \geq 0$.

We wish to consider the general time reversible case. Instead of being symmetric, we have

$\displaystyle R(y,x) = \frac{\pi(x)}{\pi(y)} R(x,y).$

Then

$\displaystyle \frac{dP(t;x)}{dt} = \sum_{\stackrel{y\in \mathcal X}{y\neq x}}\frac{R(x,y)}{\pi(y)}\left(\pi(x)P(t;y) - \pi(y)P(t;x)\right).$

so that

$\displaystyle \frac{dS}{dt} = -\sum_{\stackrel{x,y\in \mathcal X}{y\neq x}} \log P(t;x)\frac{R(x,y)}{\pi(y)}\left(\pi(x)P(t;y) - \pi(y)P(t;x)\right)$

and as before, we observe the terms

$\displaystyle -\log P(t;x)\frac{R(x,y)}{\pi(y)}\left(\pi(y)P(t;x) - \pi(x)P(t;y)\right),$

and

$\displaystyle \log P(t;y)\frac{R(y,x)}{\pi(x)}\left(\pi(y)P(t;x) - \pi(x)P(t;y)\right) = \log P(t;y)\frac{R(x,y)}{\pi(y)}\left(\pi(y)P(t;x) - \pi(x)P(t;y)\right)$

occur in the above summation. Therefore

$\displaystyle \frac{dS}{dt} = \sum_{\stackrel{x,y\in \mathcal X}{y\neq x}}\frac{R(x,y)}{\pi(y)}\left(\log P(t;x) - \log P(t;y)\right)\left(\pi(y)P(t;x) - \pi(x)P(t;y)\right)$