Entropy-Based Similarity¶

An Information-Theoretic Similarity Measure for Markov Chains¶

Introduction¶

The Entropy-Based Similarity measure provides a way to compare Markov chains using principles from information theory. This measure quantifies the similarity between two processes based on their entropy structures, offering insights into their inherent randomness and predictability patterns. It is particularly useful when comparing the underlying uncertainty and information content of different stochastic processes.

Mathematical Foundation¶

The measure combines the concept of entropy, which quantifies the uncertainty in a process, with similarity principles. It considers both the individual entropies of the processes and their joint behavior to create a normalized similarity score.

Formal Definition¶

For two Markov chains P and Q, the entropy-based similarity is defined as:

\[S(P,Q) = \frac{H(P) + H(Q) - H(P,Q)}{max(H(P), H(Q))}\]

where: - H(P) is the entropy of chain P - H(Q) is the entropy of chain Q - H(P,Q) is the joint entropy - The result is normalized to [0,1]

For a Markov chain P, the entropy H(P) is calculated as:

\[H(P) = -\sum_{i=1}^n \pi_i \sum_{j=1}^n p_{ij} \log(p_{ij})\]

Properties¶

Symmetry: S(P,Q) = S(Q,P)
Bounded: 0 ≤ S(P,Q) ≤ 1
Identity: S(P,P) = 1
Monotonicity with respect to entropy differences
Invariance under permutations of equivalent states

Implementation¶

The measure is implemented in the distancia package:

from distancia.metrics import EntropyBasedSimilarity

# Initialize the measure
entropy_sim = EntropyBasedSimilarity()

# Calculate similarity between two Markov chains
similarity = entropy_sim.compute(matrix_p, matrix_q)

Usage Example¶

Here’s a practical example comparing two Markov chains:

import numpy as np
from distancia.metrics import EntropyBasedSimilarity

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

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

# Calculate entropy-based similarity
entropy_sim = EntropyBasedSimilarity()
result = entropy_sim.compute(P, Q)
print(f"Entropy-Based Similarity: {result:.4f}")

# Access individual entropies
h_p = entropy_sim.get_entropy(P)
h_q = entropy_sim.get_entropy(Q)

Computational Complexity¶

Time Complexity: O(n²) where n is the number of states
Space Complexity: O(n²) for storing transition matrices

The implementation includes: 1. Efficient entropy computation 2. Handling of zero probabilities 3. Numerical stability for small values 4. Normalization procedures

Academic References¶

Shannon, C. E. (1948). “A Mathematical Theory of Communication.” Bell System Technical Journal.
Lin, J. (1991). “Divergence Measures Based on the Shannon Entropy.” IEEE Transactions on Information Theory.
Ellerman, D. (2009). “Numeraire-invariant Entropy Measures.” Journal of Mathematical Sciences.
Dehmer, M., & Mowshowitz, A. (2011). “A History of Graph Entropy Measures.” Information Sciences.

Conclusion¶

The Entropy-Based Similarity measure provides an intuitive way to compare Markov chains through their information-theoretic properties. Its implementation in the distancia package offers researchers and practitioners a valuable tool for: - Process comparison - Model selection - Pattern analysis - System characterization

The measure is particularly useful in applications where: - Information content is crucial - Process uncertainty needs to be quantified - Pattern similarity is important - Model discrimination is required