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)

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: