Skip to main content
grammar/minor edits
Source Link
VSJ
  • 1k
  • 6
  • 18

Convergence of Markov chainchains in terms of relative entropy

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.

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 https://web.cse.msu.edu/~cse842/Papers/CoverThomas-Ch2.pdf).

My question is:

Is $D(p_t || \pi)$ a convex function of $t$?

I simulated for many random matrices using Matlab and did not find a counter example. Any references would be appreciated!

Convergence of Markov chain in terms of relative entropy

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.

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 https://web.cse.msu.edu/~cse842/Papers/CoverThomas-Ch2.pdf).

My question is:

Is $D(p_t || \pi)$ convex?

I simulated for many random matrices using Matlab and did not find a counter example. Any references would be appreciated!

Convergence of Markov chains in terms of relative entropy

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.

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 https://web.cse.msu.edu/~cse842/Papers/CoverThomas-Ch2.pdf).

My question is:

Is $D(p_t || \pi)$ a convex function of $t$?

I simulated for many random matrices using Matlab and did not find a counter example. Any references would be appreciated!

Source Link
VSJ
  • 1k
  • 6
  • 18

Convergence of Markov chain in terms of relative entropy

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.

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 https://web.cse.msu.edu/~cse842/Papers/CoverThomas-Ch2.pdf).

My question is:

Is $D(p_t || \pi)$ convex?

I simulated for many random matrices using Matlab and did not find a counter example. Any references would be appreciated!