Relative Entropy Rate¶

An Information-Theoretic Distance Measure for Markov Chains¶

Introduction¶

The Relative Entropy Rate provides an information-theoretic approach to comparing Markov chains by measuring the divergence between their entropy rates. This measure captures the fundamental differences in the information content and predictability of the processes, making it particularly valuable for analyzing the complexity and predictability differences between stochastic processes.

Mathematical Foundation¶

The measure is based on the concept of entropy rate, which quantifies the average amount of information produced by a stochastic process per unit time. The relative entropy rate extends this to measure how different two processes are in terms of their information generation.

Formal Definition¶

For two Markov chains P and Q with stationary distributions π_P and π_Q, the relative entropy rate is defined as:

\[h(P||Q) = \sum_{i=1}^n \sum_{j=1}^n \pi_P(i)p_{ij}\log\left(\frac{p_{ij}}{q_{ij}}\right)\]

where: - p_ij and q_ij are transition probabilities - π_P(i) is the stationary probability of state i in chain P - n is the number of states - The logarithm is typically taken with base 2 (for bits) or e (for nats)

Properties¶

Non-negativity: h(P||Q) ≥ 0
Asymmetry: Generally h(P||Q) ≠ h(Q||P)
h(P||Q) = 0 if and only if P = Q
Chain rule decomposition
Convexity in probability space

Implementation¶

The measure is implemented in the distancia package:

from distancia.metrics import RelativeEntropyRate

# Initialize the measure
rer_dist = RelativeEntropyRate()

# Calculate distance between two Markov chains
distance = rer_dist.compute(matrix_p, matrix_q)

Usage Example¶

Here’s a practical example comparing two Markov chains:

import numpy as np
from distancia.metrics import RelativeEntropyRate

# Define two transition matrices
P = np.array([[0.7, 0.2, 0.1],
              [0.1, 0.8, 0.1],
              [0.2, 0.1, 0.7]])

Q = np.array([[0.6, 0.3, 0.1],
              [0.2, 0.7, 0.1],
              [0.1, 0.2, 0.7]])

# Calculate relative entropy rate
rer_dist = RelativeEntropyRate()
result = rer_dist.compute(P, Q)
print(f"Relative Entropy Rate: {result:.4f}")

# Access individual entropy rates
h_p = rer_dist.get_entropy_rate(P)
h_q = rer_dist.get_entropy_rate(Q)

Computational Complexity¶

Time Complexity: O(n³) where n is the number of states
Space Complexity: O(n²) for storing matrices and intermediate calculations

The implementation includes: 1. Efficient computation of stationary distributions 2. Handling of zero transition probabilities 3. Numerical stability for small probabilities 4. Optional base selection for logarithm

Academic References¶

Cover, T. M., & Thomas, J. A. (2006). “Elements of Information Theory.” Wiley-Interscience.
Rached, Z., et al. (2004). “The Relative Entropy Rate of Markov Sources.” IEEE Transactions on Information Theory.
Gray, R. M. (2011). “Entropy and Information Theory.” Springer.
Khudanpur, S. P., & Narayan, P. (2002). “Order estimation for Markov chains and hidden Markov models.” IEEE Transactions on Information Theory.

Conclusion¶

The Relative Entropy Rate provides a sophisticated way to compare Markov chains based on their information-theoretic properties. Its implementation in the distancia package offers researchers and practitioners a powerful tool for analyzing: - Process complexity - Predictability differences - Information generation rates - Model selection

The measure is particularly valuable in applications such as: - Natural language processing - Data compression - Pattern recognition - Time series analysis