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:

.. math::

    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:

.. math::

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

Properties
---------
1. Symmetry: S(P,Q) = S(Q,P)
2. Bounded: 0 ≤ S(P,Q) ≤ 1
3. Identity: S(P,P) = 1
4. Monotonicity with respect to entropy differences
5. Invariance under permutations of equivalent states

Implementation
------------
The measure is implemented in the `distancia` package:

.. code-block:: python

    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:

.. code-block:: python

    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
----------------
1. Shannon, C. E. (1948). "A Mathematical Theory of Communication." Bell System Technical Journal.
2. Lin, J. (1991). "Divergence Measures Based on the Shannon Entropy." IEEE Transactions on Information Theory.
3. Ellerman, D. (2009). "Numeraire-invariant Entropy Measures." Journal of Mathematical Sciences.
4. 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

See Also
--------
- Relative Entropy Rate
- Cross-Entropy Distance
- Information Divergence
- Shannon Entropy Measure