most recent 30 from http://mathoverflow.net 2013-05-23T20:52:27Z http://mathoverflow.net/feeds/question/104664 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/104664/convergence-of-markov-chains-in-terms-of-relative-entropy VSJ 2012-08-14T02:30:13Z 2012-09-21T06:56:42Z

<p>Consider a finite state, irreducible Markov chain with a rate matrix $Q$ and a stationary distribution $\pi$. Suppose the chain starts with the initial distribution $p$ at time $0$, then at time $t$ the distribution is given by $$p_t = p*e^{Qt}$$ The relative entropy of $p_t$ with respect to the $\pi$ (also known as the Kullback-Leibler divergence $D(p_t || \pi)$) is given by $$D(p_t || \pi) = \sum_i p_t(i) \log \left(\frac{p_t(i)}{\pi(i)}\right)$$ where $i$ ranges over all the states.</p> <p>It seems well known that $D(p_t || \pi)$ monotonically decreases as $t$ increases. (For instance, section $2.9$ of Cover and Thomas's book here <a href="https://web.cse.msu.edu/~cse842/Papers/CoverThomas-Ch2.pdf" rel="nofollow">https://web.cse.msu.edu/~cse842/Papers/CoverThomas-Ch2.pdf</a>).</p> <p>My question is:</p> <blockquote> <p>Is $D(p_t || \pi)$ a convex function of $t$?</p> </blockquote> <p>I simulated for many random matrices using Matlab and did not find a counter example. Any references would be appreciated!</p>

http://mathoverflow.net/questions/104664/convergence-of-markov-chains-in-terms-of-relative-entropy/107744#107744 VSJ 2012-09-21T06:56:42Z 2012-09-21T06:56:42Z

<p>Turns out $D(p_t||\pi)$ need not always be convex. The following paper demonstrates a counter-example in section $4.2$- <a href="http://arxiv.org/abs/0712.2578" rel="nofollow">http://arxiv.org/abs/0712.2578</a></p>