16 January 2008

Shuffling cards and total variation distance

David Speyer asks: what is total variation distance? Total variation distance is defined as follows: given two measures f and g on a space X, of total mass 1, the total variation distance is the maximum (strictly speaking, the supremum) of f(A) - g(A) over all subsets A of X. But this is only really enlightening if you're one of those people who buys the whole "probability theory is the study of measures of total mass 1" (I first heard this from Robin Pemantle but I don't know if it's original to him), which makes it sound like probability is strictly a subset of measure theory. It's not, because when you restrict to measures of total mass 1 a whole host of probabilistic intuition is valuable. Speyer gives an interpretation of the total variation distance in terms of gambling.

Speaking of gambling, you should shuffle a deck of cards seven times before using it; this comes from the famous paper of Bayer and Diaconis (Dave Bayer and Persi Diaconis, "Trailing the Dovetail Shuffle to its Lair". Ann. Appl. Probab. Volume 2, Number 2 (1992), 294-313), which Speyer was reading. (This was in the January 9, 1990 New York Times. Had this blog existed eighteen years ago, I surely would have mentioned this article. But there were no blogs back then, and I was not old enough to be reading mathematics journals.) I had incorrectly believed that this means that seven shuffles gave a uniform distribution over all possible arrangements of cards, but in fact the distribution isn't uniform; it's just "close enough", in the sense that the total variation distance is small.

I suspect I confused this with the result that "if a deck is perfectly shuffled eight times, the cards will be in the same order as they were before the shuffling"; thus you should stop at seven shuffles because on the eighth shuffle all your work will be for nought! But nobody shuffles perfectly.

2 comments:

Anonymous said...

re your last line: Diaconis certainly does shuffle perfectly (when he wants to)!

He came out with a nice line in a talk I saw him give a while back. Talking about the Gilbert-Shannon-Reeds shuffling model (the one analysed in the paper you cited): "This is actually a good model for how you shuffle cards. It's not a good model for how _I_ shuffle cards, but it's a good model for how _you_ shuffle cards." :)

Anonymous said...


I suspect I confused this with the result that "if a deck is perfectly shuffled eight times, the cards will be in the same order as they were before the shuffling"


For the Riffle Shuffle, that is!