# Understanding total variation distance formula in relation to card shuffling.

• Oct 12th 2012, 10:06 AM
CBauer00010010
Understanding total variation distance formula in relation to card shuffling.
I am creating some JavaScript probability calculators related to magic the gathering deck building. While doing so I wondered what the best way to randomize a players deck is. I was able to find good information on 52 card decks stating that at-lest 7 riffle shuffle are needed according to TRAILING THE DOVETAIL SHUFFLE TO ITS LAIR pdf and HOW MANY TIMES SHOULD YOU SHUFFLE A DECK OF CARDS? pdf. But these papers are a bit over my head.

I was able to find this webpage that shows a table similar to witch I wish to include in my calculator.

 Cards\Shuffles 1 2 3 4 5 6 7 8 25 1 1 0.999 0.775 0.437 0.231 0.114 0.056 32 1 1 1 0.929 0.597 0.322 0.164 0.084 52 1 1 1 1 0.924 0.614 0.334 0.167

I would like help understanding how to calculate these numbers, which I believe came from using this formula, which I can not make sense of.

http://www.math.cornell.edu/~numb3rs...season5/tv.png

Could anyone please show me a step by step breakdown of how to calculate the total variation distance with say 32 cards and 6 shuffles?
• Oct 12th 2012, 04:28 PM
chiro
Re: Understanding total variation distance formula in relation to card shuffling.
Hey CBauer00010010.

A permutation just takes a set of things and shuffles them in an arbitrary order. So if you have four elements (1,2,3,4) one shuffling might be (2,3,1,4) and another might be (4,3,2,1). This is all a permutation is.

Now P and Q are functions: they take the input and give an output. In this scenario though, P and Q are not just any function: they are probabilities (according to the website).

So P(x) calculates the probability of getting x and same for Q(x).

So what is really saying is that x is a permutation from an initial state to a shuffled state and P(x) is the probability of that happening. So as an example if I start off with (1,2,3,4) in that order and I do a shuffle x where I go to (4,3,2,1) then P(x) is the probability of going from (1,2,3,4) to (4,3,2,1).

P and Q are different probability spaces and if P is the same as Q then the distance will be 0. Think of each probability space being a vector with each permutation type being an independent element of the vector and you are finding the "distance" between the two vectors.