# Total Variation Distance of probability matrix

How can I calculate the Total Variation Distance of a transition Matrix? is there any built in function? I've searched all documentation and haven;t found anything.

Let me try to explain it better. let's say we have a transition matrix ($P$), $4\times4$ that describes the probability of going from a, b, c and d to a, b, c or d in 1 step.

We can calculate the stationary distribution of $P$, and that's called $\pi$ in the following equation, and $P_{yx}$ is the probability of going from state $y$ to state $x$ (a,b,c,d):

$$\frac12\sum_x\left|P_{yx}^t-\pi(x)\right|$$

What I want to do is calculate the Total Variation Distance of $P$ from $\pi$ after $n$ steps and starting on a given state.

*** This is what I have so far:

M = {{0.3, 0, 0.5, 0.2}, {0, 0.4, 0.3, 0.3}, {0.3, 0.2, 0, 0.5}, {0.4, 0.1, 0, 0.5}}

B = Transpose[M]

N[B] // MatrixForm

{eVals, eVecs} = Eigensystem[B]

eVals // MatrixForm

eVecs // MatrixForm

eigenvector = eVecs[]

Print["Stationary Distribution"];

eigenvector/Total[eigenvector]

Print["M after 1 step"];

M2 = MatrixPower[M, 2]

• And what would that be in the context of markov chains? I would wild-guess the maximum difference (Max[mat1-mat2]) between the probabilities of events in some time given some initial condition (MatrixPower[Q, n].initialVector) versus in the limit should there be any? – Rojo Oct 5 '12 at 3:05
• Have you tried writing your own function? – rm -rf Oct 5 '12 at 4:26
• In the Wikipedia definition, there are two probability distributions P and Q, and the total variation is defined as a function of the two. In your question, what are P and Q? – bill s Oct 5 '12 at 8:49
• Let's say that I have a transition matrix (n x n), called P, and that I calculate its stationary distribution, which is an eigenvector with an eigenvalue of 1 (1 x n), and let'sc all it Q. Those are the two inputs of the equation in Wikipedia. – whynot Oct 5 '12 at 14:11
• Help me see what I'm missing. The eigenvector has the probabilities of being in a certain state. The matrix the probabilities of "going from one to the other". Those aren't the same events, you can't compare them. That's why the matrix has n^2 elements and the vector n – Rojo Oct 5 '12 at 14:29

The terms in the total variation distance need to be probability distributions. Here's one way to do it: take any starting vector $m_0$ (with nonzero entries that sum to $1$). You can interpret $m_0$ as the initial distribution of the states. Then $m_1=m_0\cdot P$ is the distribution of the states after one time step, $m_2=m_0\cdot P\cdot P$ is the distribution of the states after two time steps, etc., where $P$ is the transition matrix of the Markov chain. Now you have several distributions and you can apply the total variation (as in the Wikipedia article). This would be

 Total[Abs[m0 - m1]]/2


for the distance from $m_0$ to $m_1$. This is really just the 1-norm, so a more concise expression would be

Norm[m0 - m1, 1]/2


You could also take the distance between any of these distributions and the stationary distribution, as was calculated in stationary distribution of a transition matrix

• Of course, Norm[m0 - m1, 1]/2 is equivalent to ManhattanDistance[m0, m1]/2. – J. M.'s technical difficulties Oct 6 '12 at 3:16

You can get the stationary distribution by getting the first eigenvector. Or, if I'm mistaken with this, just use eigensystem and filter by the eigenvector 1.

pi[p_] := Normalize[First@Eigenvectors[p, 1], Norm[#, 1] &]

totVar[m1_, m2_] := Total@Abs[m1- m2]/2


So if p is your transition matrix, m the vector with initial states and n the time

totVarMarkov[p_, m_, n_] := totVar{[pi[p]}, {Flatten@m}.MatrixPower[p, n]]


(Code untested)