From: iang@cs.berkeley.edu (Ian Goldberg)
Date: Tue, 19 Nov 1996 19:05:53 -0800 (PST)
To: cypherpunks@toad.com
Subject: Re: Playing Cards - Caution!
In-Reply-To: <v02140b00aeb6e056bb78@[192.0.2.1]>
Message-ID: <56ts6f$2t9@abraham.cs.berkeley.edu>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

In article <EMgky8m9Lkmb085yn@netcom.com>,
Alan Bostick <abostick@netcom.com> wrote:
>Note: I haven't read Diaconis's work; just some reports of it in the news
>section of SCIENCE more than ten years ago, so people should take what
>I say with more than a grain of salt.
>
>
>Here is a (surely oversimplified) model of a less-than-perfect riffle
>shuffle:  the deck is divided into two equal stacks, and the shuffler
>typically introduces some number k of "errors" that result in a pair
>of adjacent cards in the shuffled deck being exchanged (compared to 
>a perfectly-shuffled deck).  In a fifty-two-card deck there are fifty-one
>possible pairs to exchange.  log2(51) = 5.67, so we get 5.67 bits of 
>entropy for each exchange, if the exchanges are distributed uniformly
>through the deck.

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..."

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBMpJ0CkZRiTErSPb1AQHeJQP/c+LDI5dP1FWBb8TrArZYJ/LGTMsCnSIr
TWXEV1ZC7U30aKcXwYcoRh0COg3iSPpwwNCr8qveZz/F4t2nR9J1feu27NE2AqE/
M4CozehsGoX9jW4/zzZu+2M6YK2EhBlRu5JpsKUax7It0VBQCz34BccT+e/8CXMj
Ym+nS0zF7CM=
=s9HO
-----END PGP SIGNATURE-----