Sequence Probability Divergence¶

A Likelihood-Based Distance Measure for Markov Chains¶

Introduction¶

The Sequence Probability Divergence measures the difference between Markov chains by comparing how they assign probabilities to sequence realizations. This measure is particularly valuable when the primary interest lies in comparing how different models explain or generate observed sequences of states, making it especially useful in applications like pattern recognition and sequence analysis.

Mathematical Foundation¶

The measure is based on comparing the likelihood of observing specific sequences under different Markov chain models. It quantifies how differently two Markov chains would generate or explain the same sequence of states, providing insights into their generative behaviors.

Formal Definition¶

For two Markov chains P and Q, and a sequence of states s = (s₁, s₂, …, sₖ), the sequence probability divergence is defined as:

\[D(P||Q) = \mathbb{E}_P\left[\log\frac{P(s)}{Q(s)}\right]\]

where: - P(s) is the probability of sequence s under model P - Q(s) is the probability of sequence s under model Q - The expectation is taken over sequences generated by P - For a sequence s, P(s) = π_{s₁}∏ᵢp_{sᵢ,sᵢ₊₁}

Properties¶

Non-negativity: D(P||Q) ≥ 0
Asymmetry: Generally D(P||Q) ≠ D(Q||P)
Identity of indiscernibles: D(P||Q) = 0 if and only if P = Q
Sequence length sensitivity
Initial distribution dependence

Implementation¶

The measure is implemented in the distancia package:

from distancia.metrics import SequenceProbabilityDivergence

# Initialize the measure
seq_div = SequenceProbabilityDivergence()

# Calculate divergence between two Markov chains
divergence = seq_div.compute(matrix_p, matrix_q, sequence_length=100)

Usage Example¶

Here’s a practical example comparing two Markov chains:

import numpy as np
from distancia.metrics import SequenceProbabilityDivergence

# 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 sequence probability divergence
seq_div = SequenceProbabilityDivergence()
result = seq_div.compute(P, Q, sequence_length=100)
print(f"Sequence Probability Divergence: {result:.4f}")

# Generate and compare specific sequences
sequence = seq_div.generate_sequence(P, length=10)
p_prob = seq_div.sequence_probability(P, sequence)
q_prob = seq_div.sequence_probability(Q, sequence)

Computational Complexity¶

Time Complexity: O(kn²) where k is sequence length and n is number of states
Space Complexity: O(n²) for storing transition matrices
Monte Carlo estimation: O(mn²) for m sample sequences

The implementation includes: 1. Efficient sequence generation 2. Monte Carlo estimation for long sequences 3. Numerical stability for small probabilities 4. Optional sequence length specification

Academic References¶

Rabiner, L. R. (1989). “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition.” Proceedings of the IEEE.
Durbin, R., et al. (1998). “Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids.” Cambridge University Press.
Viterbi, A. (1967). “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm.” IEEE Transactions on Information Theory.
Baum, L. E. (1972). “An Inequality and Associated Maximization Technique in Statistical Estimation for Probabilistic Functions of Markov Processes.”

Conclusion¶

The Sequence Probability Divergence provides a powerful way to compare Markov chains based on their sequence generation properties. Its implementation in the distancia package offers researchers and practitioners a valuable tool for analyzing: - Sequence modeling - Pattern recognition - Time series analysis - Model selection

The measure is particularly useful in applications such as: - Biological sequence analysis - Speech recognition - Text generation - Anomaly detection