topologicalEntropy: Topological entropy of a Markov chain

In markovchain: Easy Handling Discrete Time Markov Chains

Topological entropy of a Markov chain

Description

Computes the topological entropy of the graph of a discrete-time Markov chain: the exponential growth rate of the number of distinct admissible paths, ignoring their probabilities.

Usage

topologicalEntropy(object, base = 2)

## S4 method for signature 'markovchain'
topologicalEntropy(object, base = 2)

Arguments

object	A markovchain object.
base	A finite numeric scalar strictly greater than one. The default, 2, returns bits, consistently with entropyRate.

Details

If A is the 0/1 adjacency matrix with A_{ij}=1 exactly when p_{ij}>0, the topological entropy is

h_{top} = \log_b \rho(A),

where \rho(A) is the spectral radius (Perron root) of A.

Only the pattern of positive entries matters: the value depends on which transitions are possible, not on how likely they are. It is the upper bound of the entropy rate over all the Markov chains sharing that graph (the variational principle, see Parry, 1964), so entropyRate(object) <= topologicalEntropy(object) for an irreducible chain. The bound is attained by the maximal-entropy (Parry) chain on the same graph, and also, for instance, by a chain whose every row is uniform over a common number of successors. A chain that is a single cycle (deterministic dynamics) has topologicalEntropy = 0.

No irreducibility is needed: for a reducible chain the result is the largest value over its communicating classes. A probability that is positive but numerically tiny counts as a transition, exactly as in is.irreducible.

The cost is one eigenvalue computation, O(n^3) time and O(n^2) memory for a dense chain. It mirrors PyDTMC's topological_entropy, which uses the natural logarithm.

Value

A non-negative numeric scalar in units determined by base.

References

Parry, W. (1964). Intrinsic Markov chains. Transactions of the American Mathematical Society, 112, 55-66.

Cover, T. M. and Thomas, J. A. (2006). Elements of Information Theory, 2nd edition. Wiley.

See Also

entropyRate, normalizedEntropyRate

Examples

statesNames <- c("a", "b")
mc <- new("markovchain",
  states = statesNames,
  transitionMatrix = matrix(c(0.7, 0.3, 0.1, 0.9),
    byrow = TRUE, nrow = 2,
    dimnames = list(statesNames, statesNames)))
topologicalEntropy(mc)

markovchain documentation built on Oct. 10, 2026, 9:07 a.m.