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)$$


$$ 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.

  • $\begingroup$ How about absolute difference? $\endgroup$ Jul 23, 2019 at 6:55
  • $\begingroup$ I thought of it also, but I don't know if it makes sense when comparing these stochastic matrices. $\endgroup$ Jul 23, 2019 at 12:18
  • $\begingroup$ can you put the question in a maximum likelihood framework? then the metric might become more obvious $\endgroup$
    – seanv507
    Dec 27, 2020 at 14:16

1 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.