From: ph@netcom.com (Peter Hendrickson)
Date: Tue, 19 Nov 1996 20:06:41 -0800 (PST)
To: cypherpunks@toad.com
Subject: Re: Playing Cards - Caution!
Message-ID: <v02140b05aeb82f58b9c5@[192.0.2.1]>
MIME-Version: 1.0
Content-Type: text/plain


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