Markov Chain Distances ====================== Introduction ============ Markov chains are widely used to model stochastic processes where the next state depends only on the current state. Comparing two Markov chains can help us understand differences in their behavior, transition probabilities, and steady-state distributions. The **Distancia** package provides various methods for calculating distances between two Markov chains, each capturing different aspects of their structures and dynamics. These measures are useful in fields like statistical modeling, machine learning, and decision-making processes. Markov Chain Distance Measures ------------------------------ Categorized Distance Measures ----------------------------- #. `Euclidean`_ : #. `L1`_ : Computes the element-wise \( L1 \) distance (Manhattan distance) between the transition matrices of two Markov Chains. #. `L2`_ : Computes the element-wise \( L2 \) distance (Euclidean distance) between the transition matrices. #. `Markov Chain Frobenius`_ : Measures the norm of the difference between the transition matrices. #. `Matrix Divergence`_ : A general measure comparing two matrices in terms of divergence metrics. #. `Spectral Norm Distance`_ : Focuses on the spectral properties of the transition matrices. #. `Hamming`_ : Compares the state sequences generated by two Markov chains by calculating the number of positions where the sequences differ. .. _Euclidean: https://distancia.readthedocs.io/en/latest/Euclidean.html .. _L1: https://distancia.readthedocs.io/en/latest/Manhattan.html .. _L2: https://distancia.readthedocs.io/en/latest/Euclidean.html .. _Markov Chain Frobenius: https://distancia.readthedocs.io/en/latest/MarkovChainFrobenius.html .. _Matrix Divergence: https://distancia.readthedocs.io/en/latest/MatrixDivergence.html .. _Spectral Norm Distance: https://distancia.readthedocs.io/en/latest/SpectralNormDistance.html .. _Hamming: https://distancia.readthedocs.io/en/latest/Hamming.html Stationary Distribution-Based Measures ----------------------------- 8. `Markov Chain Kullback Leibler`_ : Measures the information gain or loss between the stationary distributions. #. `Markov Chain Hellinger`_ : Measures the similarity between two stationary distributions using a probabilistic approach. #. `Steady-StateDistribution`_ Compares the steady-state distributions of two Markov chains, evaluating the long-term behavior differences. #. `Markov Chain Wasserstein`_ : Measures the “cost” of transforming one steady-state distribution into another, capturing the distributional differences between two chains. #. `Markov Chain Jensen Shannon`_ : Symmetrized version of the Kullback-Leibler divergence that compares the steady-state distributions of the two chains. #. `Markov Chain Total Variation`_ : Measures the maximum difference between transition probabilities, capturing the largest deviation in state transitions between two chains. .. _Markov Chain Kullback Leibler: https://distancia.readthedocs.io/en/latest/MarkovChainKullbackLeibler.html .. _Markov Chain Jensen Shannon: https://distancia.readthedocs.io/en/latest/MarkovChainJensenShannon.html .. _Markov Chain Hellinger: https://distancia.readthedocs.io/en/latest/MarkovChainHellinger.html .. _Markov Chain Total Variation: https://distancia.readthedocs.io/en/latest/MarkovChainTotalVariation.html .. _Steady-StateDistribution: https://distancia.readthedocs.io/en/latest/SteadyStateDistribution.html .. _Markov Chain Wasserstein: https://distancia.readthedocs.io/en/latest/Wasserstein.html Graph-Theoretic Measures ----------------------------- Structural distances assess the overall architecture of the Markov chains, including how the states are connected and whether there are differences in the structure of the state transitions. 16. `Commute Time Distance`_ : Measures the average time taken for a random walk to move between two states. #. `Hitting Time Distance`_ : The expected time for a random walk to first reach a particular state. #. `Resistance Distance`_ : Interprets the Markov Chain as an electrical network and computes resistances. #. `Graph Laplacian Distance`_ : Uses properties of the Laplacian matrix of the graph induced by the Markov Chain. #. `Graph Edit Distance`_ : Calculates the minimal number of edits (additions, deletions, substitutions) required to transform the state transition graph of one Markov chain into another. #. `Spectral Distance`_ : Compares the eigenvalues of the transition matrices, capturing the differences in the dynamics of the chains, such as mixing times and convergence rates. .. _Commute Time Distance: https://distancia.readthedocs.io/en/latest/CommuteTimeDistance.html .. _Hitting Time Distance: https://distancia.readthedocs.io/en/latest/HittingTimeDistance.html .. _Resistance Distance: https://distancia.readthedocs.io/en/latest/Resistance.html .. _Graph Laplacian Distance: https://distancia.readthedocs.io/en/latest/GraphLaplacian.html .. _Graph Edit Distance: https://distancia.readthedocs.io/en/latest/GraphEditDistance.html .. _Spectral Distance: https://distancia.readthedocs.io/en/latest/SpectralDistance.html Entropy and Information-Based Measures ----------------------------- 22. `Relative Entropy Rate`_ : Measures the divergence between the entropy rates of two Markov Chains. #. `Cross-Entropy Distance`_ : Combines entropy rates to evaluate the distance between chains. #. `Entropy-Based Similarity`_ : Quantifies similarity using entropy principles. .. _Relative Entropy Rate: https://distancia.readthedocs.io/en/latest/RelativeEntropyRate.html .. _Cross-Entropy Distance: https://distancia.readthedocs.io/en/latest/CrossEntropy.html .. _Entropy-Based Similarity: https://distancia.readthedocs.io/en/latest/EntropyBasedSimilarity.html Behavioral or State-Sequence Measures ----------------------------- 25. `Levenshtein Distance on Paths`_ : Measures the edit distance between state sequences generated by two Markov Chains. #. `Dynamic Time Warping (DTW)`_ : Measures alignment between state sequences with different lengths. #. `Sequence Probability Divergence`_ : Compares the likelihood of sequences under two different Markov Chains. .. _Levenshtein Distance on Paths: https://distancia.readthedocs.io/en/latest/Levenshtein.html .. _Dynamic Time Warping (DTW): https://distancia.readthedocs.io/en/latest/DynamicTimeWarping.html .. _Sequence Probability Divergence: https://distancia.readthedocs.io/en/latest/SequenceProbabilityDivergence.html Customized Measures ----------------------------- 28. `Wasserstein Distance`_ : Computes the cost of transforming one stationary distribution into another, using the structure of the state space. #. `Markov Earth Mover's Distance (MEMD)`_ : A variation of Wasserstein designed for Markov Chains. #. `Bhattacharyya Distance for Markov Chains`_ : Measures overlap between stationary distributions. #. `Cosine Similarity on Transition Matrices`_ : Treats the transition matrices as vectors and computes cosine similarity. #. `Markov Chain Spectral`_ .. _Markov Earth Mover's Distance (MEMD): https://distancia.readthedocs.io/en/latest/EarthMoversDistance.html .. _Bhattacharyya Distance for Markov Chains: https://distancia.readthedocs.io/en/latest/Bhattacharyya.html .. _Cosine Similarity on Transition Matrices: https://distancia.readthedocs.io/en/latest/Cosine.html .. _Markov Chain Spectral: https://distancia.readthedocs.io/en/latest/SpectralDistance.html .. _Wasserstein Distance: https://distancia.readthedocs.io/en/latest/Wasserstein.html Conclusion ----------------------------- The **Distancia** package provides an extensive set of tools to compare Markov chains using various distance measures. Whether you're interested in comparing transition probabilities, state distributions, or the overall structure, **Distancia** offers methods tailored to different analysis needs. By understanding these distances, you can gain valuable insights into the behavior of stochastic systems, making **Distancia** a versatile tool for applications ranging from machine learning to operations research. Markov Chain distances provide a versatile toolkit for comparing stochastic processes, whether through transition matrices, stationary distributions, or state-sequence behaviors. Choosing the right distance depends on the specific application, such as analyzing stationary distributions, comparing paths, or investigating graph-based properties. This categorized approach simplifies the selection process and ensures you have access to the most relevant methods for your analysis.