Understanding total variation distance formula in relation to card shuffling.
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.000 ||1.000 ||0.999 ||0.775 ||0.437 ||0.231 ||0.114 ||0.056 |
|32 ||1.000 ||1.000 ||1.000 ||0.929 ||0.597 ||0.322 ||0.164 ||0.084 |
|52 ||1.000 ||1.000 ||1.000 ||1.000 ||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.
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?
Re: Understanding total variation distance formula in relation to card shuffling.
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.