6
$\begingroup$

Given a finite Markov chain, how do I find the topological entropy $h_T$? Furthermore, I should compare it with the Shannon entropy $h_S$ and show that $h_T\leq h_S$. Is this a general fact?

This actually comes from an exercise, the specific Markov chain used there is defined by: $$\Omega=\{1,2,3\}$$ with transition probabilities $$p_{1\rightarrow 1}=1-q \quad p_{1\rightarrow 2}=p_{1\rightarrow 3}=\frac{q}{2}$$ $$p_{2\rightarrow 2}=1-q\quad p_{2\rightarrow 3}=q$$ $$p_{3\rightarrow 1}=1$$

$\endgroup$
1
  • 1
    $\begingroup$ Does the book the exercise comes from not define what the topological entropy is? $\endgroup$
    – Martino
    May 2, 2018 at 18:36

1 Answer 1

5
+50
$\begingroup$

I strongly recommend two references:

  • Young's paper (e-print), an illuminating conceptual review of entropy in dynamical systems;
  • Pekoske's Master thesis, for its examples with step by step calculations.
    (Beware of the typo in page 36, though: $h_\mu(\sigma)\approx .075489$ should read $h_\mu(\sigma)\approx 0.32451$.)

Topological Entropy $h_T$

how do I find the topological entropy $h_T$?

From a compatible topological Markov shift.

The given transition probabilities correspond to the (left) transition matrix: $$ P = \begin{pmatrix} 1-q & 0 & 1\\ q/2 & 1-q & 0\\ q/2 & q & 0 \end{pmatrix}. $$

We obtain a topological Markov shift (i.e., a subshift of finite type) from the original Markov chain by considering the adjacency matrix $A$ compatible with $P$ (see the posts here and this talk): $$ A = \begin{pmatrix} 1 & 0 & 1\\ 1 & 1 & 0\\ 1 & 1 & 0 \end{pmatrix}. $$

The topological entropy of the topological Markov shift is given (see also this book (e-print)) by the logarithm of the spectral radius (i.e., largest eigenvalue modulus, $|\lambda|$) of the adjacency matrix: $$h_T = \log_2|\lambda|.$$

For $A$ above we have $\lambda=2$ and, thus $$h_T = 1.$$

Kolmogorov-Sinai (KS) entropy $h_{KS}$

If $\pi$ is the steady state of the Markov chain given by $P$, then

$$ h_{KS} = - \sum_{i,j} \pi_i P_{ij} \log_2 P_{ij}. $$

The steady state vector $\pi$ of the Markov chain is the eigenvector associated with the unit eigenvalue of $P$, normalized so that $\sum\pi_i=1$ (see these examples). For $P$ above we have

$$ \pi = \frac{1}{2q+3}\begin{pmatrix} 2\\ 1\\ 2q \end{pmatrix}. $$

That yields, e.g.:

$$ h_{KS}(q=1/2) \approx 1,$$ $$ h_{KS}(q=1/5) \approx 0.75464.$$

Shannon Entropy $h_S$

show that $h_T\le h_S$. Is this a general fact?

Yes, I think so.

The Shannon entropy $h_S$ depends on the chosen partition and is unbounded, so I'd expect the statement (1) $h_T < h_S$ to be correct. Also, it's possible to have (i) $h_S=h_{KS}$ (e.g., for the Bernoulli shift) and we have (ii) $h_T \ge h_{KS}$: from (i) and (ii) we see it's possible that (2) $h_T = h_S$ holds; finally, from (1) and (2) we have: $h_T\le h_S$.

In terms of probabilities $p_i$, we can write

$$ h_S = - \sum_{i} p_{i} \log_2 p_{i}. $$

Calculating the Shannon entropy using $P$'s steady state probabilities, $\pi_i$, we obtain, e.g.:

$$ h_{S}(q=1/2) \approx 1.5.$$ $$ h_{S}(q=1/5) \approx 1.3328.$$

$\endgroup$
3
  • $\begingroup$ Nice answer! Can I ask what's the prescription for writing the transition matrix? (and why?) Naively, I'd write down $p_{ij} = p_{i\to j}, which is triangular with largest eigenvalue 1, thus giving zero entropy $\endgroup$
    – John Donne
    May 6, 2018 at 18:45
  • $\begingroup$ @JohnDonne, Thanks. The largest eigenvalue you need for $h_T$ is of the adjacency matrix $A$, not from the transition matrix $P$. About how to write $P$, it's a matter a convention: the one you mention is the right transition matrix, the most usual in mathematics (see here), and then the stochastic vectors are rows; for dealing with matrices I'm more used to column vectors, which I'd guess are common in physics, and that corresponds to a left transition matrix $P_{ij}=p_{i\leftarrow j}$. $\endgroup$
    – stafusa
    May 6, 2018 at 20:52
  • $\begingroup$ Yes, of course, my mistake. I copied down the wrong transition matrix. Thanks! $\endgroup$
    – John Donne
    May 6, 2018 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.