Entropy of a Markov chain (right result?)

Question

Consider the Markov chain with state space $E=\left\{0,1,2,3,4,5,6\right\}$ and transition matrix $$ \begin{pmatrix}1/5 & 3/5 & 0 & 0 & 1/5 & 0 & 0\\0 & 0 & 1 & 0 & 0 & 0 & 0\\0 & 1/3 & 2/3 & 0 & 0 & 0 & 0\\0 & 1 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 1 & 0\\0 & 0 & 0 & 0 & 0 & 0& 1\\0 & 0 & 0 & 0 & 1 & 0 & 0\end{pmatrix} $$ Determine the entropy of this Markov chain!

First of all I determined the adjaceny matrix $$ A=\begin{pmatrix}1 & 1 & 0 & 0 & 1 & 0 & 0\\0 & 0 & 1 & 0 & 0 & 0 & 0\\0 & 1 & 0 & 1 & 0 & 0 & 0\\0 & 1 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 1 & 0\\0& 0 & 0 & 0 & 0 & 0 & 1\\0 & 0 & 0 & 0 & 1 & 0 & 0\end{pmatrix}. $$ Determine the entropy of the Markov chain.

Then I determined the communicating classes, which are $$ C_1=\left\{1,2,3\right\},~~~C_2=\left\{4,5,6\right\},~~~C_3=\left\{0\right\}. $$ Then I considered the graph with vertices $C_1, C_2, C_3$ and for which there is an edge from class $C$ to class $D$ if there is an edge from any state in $C$ to any state in $D$.

Then I ordered the classes such that there can only be an edge from $C_j$ to $C_i$ if $j>0$, getting the matrix $$ \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0\\1 & 0 & 1 & 0 & 0 & 0 & 0\\1 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 1 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 1 & 0\\0 & 0 & 0 & 1 & 0 & 0 & 0\\1 & 0 & 0 & 1 & 0 & 0 & 1 \end{pmatrix} $$ which is in triangular form; on the diagonal I have three square irreducible matrices.

A book says that the entropy is now the logarithm of the maximal eigenvalue (absolute value) of these three matrices. I determined the eigenvalues of the three matrices and the maximal absolut value is 1.325 (rounded).

So I get the result $$ \approx\log_2(1.325)=0.406. $$

So the entropy of the Markov chain is approximately $0.4$.

Am I right? And how can I interpret this result?

Answer 1

The entropy rate of a Markov chain with transition matrix $P$ and stationary distribution $\pi$ is $$h(Q)=-\sum\limits_{i,j}\pi_iP_{i,j}\log P_{i,j}.$$ The specific transition matrix $P$ given in the question yields a Markov chain circling, after a while, deterministically on the states $$4\to5\to6\to4,$$ hence $\pi_i=0$ for every $i$ in $\{0,1,2,3\}$ and $P_{i,j}\log P_{i,j}=0$ for every $i$ in $\{4,5,6\}$ and every $j$.

In particular, $$h(P)=0,$$ as it should be for any essentially deterministic random process.

Answer 2

There seems to be a typo in your initial stochastic matrix though: Looking at your adjacency matrix A and the communicating classes you determined, I guess the entry $2/3$ should be in the same row, but one position to the right.

Your algorithm to compute the TOPOLOGICAL entropy of your Markov chain (subshift of finite type) is correct. You could even take the entire matrix (without finding communicating classes and reordering to get a block-triagonal form), compute its eigenvalues (the characteristic polynomial now is of higher degree, but should factor into smaller ones) and then pick the maximal one of all those eigenvalues. This gives you the same value for topological entropy, as the eigenvalues of the entire matrix seen as a set are the same as the union of all set of eigenvalues of the submatrices that appear in your block-triagonal form.

However what you usually want for a Markov chain given by a stochastic matrix is to compute its measure theoretic entropy and for this there is a different formula. Instead of using the adjacancy matrix of your underlying transition graph you would take the entries of your initial matrix $P$ and first compute a stationary vector $p$ for it: $pP=p$ (as $P$ is stochastic one of its eigenvalues is $1$ and thus there is a probability vector $p$ satisfying this equation).

Now you have $P$ and its normalised eigenvector $p$. Plug those into the following formula:

$\displaystyle h(\mu_{P,p})=-\sum_{i,j=0}^6 p_iP_{i,j}\log P_{i,j}$

and you get the Kolmogorov-Sinai (or measure theoretic) entropy of your Markov chain.

For a proof why this formula give you what you want, look at any of the standard books on ergodic theory like Walters.