At 6:59 PM 11/19/1996, Ian Goldberg wrote:
I studied the "imperfect shuffle" thing in my Randomized Algorithms class last year. If I remember correctly, an "imperfect shuffle" is something like this:
Cut the deck into two piles, left and right. The number of cards in (say) the left pile is distributed binomially.
Drop one card at a time to form the new deck. A card is dropped from the left or right pile, with probability proportional to the number of cards remaining in that pile.
- Ian "someone else can figure out the entropy of this..."
This is the approach described by Diaconis. I think his book will show you how to calculate the entropy, too. (It's a cool book. The same section shows how to do a magic trick using three riffle shuffles. A member of the audience inserts the mystery card in the deck after the three riffle shuffles. Then the magician spreads the cards on the table and looks for one which does not line up with one of the several interleaved sequences in the deck.) However, it is not obvious to me that this is how it works every time, for sure, guaranteed, no doubt at all, in the real world. Diaconis mentions that the amount of entropy varies very substantially by shuffler. I also judged his experimental data to be limited. Furthermore, I am suspicious of the model itself. A binomial distribution is convenient to use, but I don't think that's how people cut cards in practice. I think that it is a much more "pointy" distribution with lower entropy. When I cut the deck there are less than 4 bits of entropy. But, I have to admit that if I worked my way through the book and learned a little related math, I might be convinced. But, even then I would probably judge it to be too tenuous for security applications. Incidentally, some big names have worked on this problem, like Graham and Shannon. Peter Hendrickson ph@netcom.com