Commute Time Distance¶

A Random Walk-Based Distance Measure for Markov Chains¶

Introduction¶

The Commute Time Distance provides a dynamic approach to comparing Markov chains by measuring the expected time for random walks to travel between states. This measure is particularly valuable for understanding the accessibility and connectivity structure of states within stochastic processes, offering insights into both local and global chain properties.

Mathematical Foundation¶

The measure is based on the concept of commute time in random walks, which is the expected number of steps needed to go from state i to state j and return to state i. This captures both the direct and indirect connections between states, providing a robust measure of their relative “closeness” in the Markov chain.

Formal Definition¶

For two states i and j in a Markov chain with transition matrix P, the commute time distance is defined as:

\[c(i,j) = h(i,j) + h(j,i)\]

where: - c(i,j) is the commute time between states i and j - h(i,j) is the hitting time from state i to j - h(j,i) is the hitting time from state j to i

For comparing two Markov chains P and Q, we use:

\[d_{ct}(P,Q) = \left(\sum_{i=1}^n \sum_{j=1}^n (c_P(i,j) - c_Q(i,j))^2\right)^{1/2}\]

Properties¶

Non-negativity: d_ct(P,Q) ≥ 0
Symmetry: d_ct(P,Q) = d_ct(Q,P)
Identity of indiscernibles: d_ct(P,Q) = 0 if and only if P = Q
Captures global chain structure
Robust to local perturbations

Implementation¶

The measure is implemented in the distancia package:

from distancia.metrics import CommuteTimeDistance

# Initialize the measure
ct_dist = CommuteTimeDistance()

# Calculate distance between two Markov chains
distance = ct_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 CommuteTimeDistance

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

Q = np.array([[0.5, 0.4, 0.1],
              [0.3, 0.4, 0.3],
              [0.1, 0.3, 0.6]])

# Calculate commute time distance
ct_dist = CommuteTimeDistance()
result = ct_dist.compute(P, Q)
print(f"Commute Time Distance: {result:.4f}")

# Access individual commute times
commute_times_p = ct_dist.get_commute_times(P)
commute_times_q = ct_dist.get_commute_times(Q)

Computational Complexity¶

Time Complexity: O(n³) where n is the number of states, due to matrix operations
Space Complexity: O(n²) for storing distance matrices and intermediate results

The implementation includes: 1. Efficient computation of fundamental matrix 2. Optimized hitting time calculations 3. Handling of reducible chains 4. Numerical stability considerations

Academic References¶

Aldous, D., & Fill, J. (2002). “Reversible Markov Chains and Random Walks on Graphs.”
Lovász, L. (1993). “Random Walks on Graphs: A Survey.” Combinatorics, Paul Erdős is Eighty.
Fouss, F., et al. (2007). “Random-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation.” IEEE TKDE.
Pons, P., & Latapy, M. (2005). “Computing Communities in Large Networks Using Random Walks.”

Conclusion¶

The Commute Time Distance provides a sophisticated way to compare Markov chains based on their random walk properties. Its implementation in the distancia package offers researchers and practitioners a powerful tool for analyzing: - Network accessibility - State connectivity patterns - Community structure - Mixing properties

The measure is particularly valuable in applications where the dynamic behavior and connectivity structure of the processes are of primary interest.