Measure the distance between two probability transition matrices

Question

I have a probability transition matrix $P$ that contains some values very close to zero. I want to sparsify this matrix by taking the k largest values for each row and setting the others to zero. For instance, taking $k=2$

$$ P = \left( \begin{array}{cccc} 0.9 & 0.0999 & 0.0001 \\ 0.199 & 0.8 & 0.001 \\ 0.199 & 0.001 & 0.8 \end{array} \right)$$

and

$$ P_{\text{sparse}} = \left( \begin{array}{cccc} 0.9 & 0.1 & 0.0 \\ 0.2 & 0.8 & 0.0 \\ 0.2 & 0.0 & 0.8 \end{array} \right) .$$

What is the best way to measure the distance between $P$ and $P_{\text{sparse}}$?

• Euclidean distance between $P$ and $P_{\text{sparse}}$?
• KL divergence between the underlying stationary state distribution?
• ...

I've look already at other questions (for instance https://mathoverflow.net/questions/225749/calculate-the-kl-divergence-between-two-transition-matrices) and articles (https://ieeexplore.ieee.org/document/1291741), but could not find a clear answer until now.

Answer 1

Reduction of Markov Chains using a Value-of-Information-Based Approach

describes a process to measure exactly what you describe

The first is a means of comparing pairs of stationary chains on different state spaces, which is done via the negative Kullback-Leibler divergence defined on a model joint space