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.


James M 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!

Anonymous said...

Hello everyone! Who knows where to upload the film Avatar?
I even bought the film Avatar for a SMS to http://rsskino.ru/kinofilm/avatar.html , the link was, but download fails, the system will boot quite strange cocoa something.
Men, advise where to normal as quickly download film avatar?

Anonymous said...

I sell a boat-program which will help you to outwit auction and to win, initially the boat was created for the Scandinavian auction http://internet-aukcion.ru/ but now the program can work with similar auctions: gagen ru, vezetmne ru and with ten.
The program-boat stakes for you, i.e. for this purpose it is not necessary to sit constantly at the monitor. The boat can set time when it is necessary to stake, thus you as much as possible will lower expenses for rates, and as much as possible increase the chances of a victory.

The price of the program a boat for the Scandinavian auctions 20$

For the first 10 clients the price 15$

To all clients free updating and support.

Behind purchases I ask in icq: 588889590 Max.

Anonymous said...

[b]Set software LoveBots v 5.2[/b]

All for a mass mailing dating http://24lux.ru/

The script is written in php5


[i]registration, account activation
manual input captures, or the solution through antikapchu
filling data accounts:
- Gulf desired photo
- Инфы about yourself
- Diary
- Sexual preference[/i]

gulyalka on questionnaires spammer on lichku
- Randomization Posts: replacement of Russian letters in Latin analogues

optimized to work in a continuous loop
check-activation-filling-spam check ..

Updates and support free of charge.

Price per set 100 wmz

For the first 10 buyers price 70 wmz (your feedback on the software).

For shopping I ask in icq: 588889590 Max.

Scrin program:




Flooding in the subject no! Write to feedback after the purchase.