From: iang@cs.berkeley.edu (Ian Goldberg)
Date: Fri, 30 Oct 1998 01:00:38 +0800
To: cypherpunks@cyberpass.net
Subject: Re: Shuffling (fwd)
In-Reply-To: <199810291325.HAA19001@einstein.ssz.com>
Message-ID: <71a4d9$vsm$1@abraham.cs.berkeley.edu>
MIME-Version: 1.0
Content-Type: text/plain



In article <199810291325.HAA19001@einstein.ssz.com>,
Jim Choate  <ravage@einstein.ssz.com> wrote:
>Forwarded message:
>
>> Date: Wed, 28 Oct 1998 22:10:08 -0800
>> From: Alex Alten <Alten@home.com>
>> Subject: Re: Shuffling
>
>> The concept of swapping to get a random string of bits is very interesting.
>> >From what I understand when one shuffles a deck of 52 cards 7 or more times
>> the card order becomes unpredictable e.g. random.
>
>Only if it is a 'fair' shuffle. There are poker players I've met who could
>put a given card anywhere in the deck after 4-5 shuffles.
>
>>  The shuffle must be
>> what is called a "near perfect" shuffle.
>
>Perfect for who? Idealy the 'perfect' shuffle (if I understand your meaning
>of perfect) would be for each card in each deck-half to interleave 1-to-1.
>This does not produce random anything, it does make it very hard for people
>to count cards, which is why you shuffle - not to create a necessarily
>random ordering of the cards, just so mis-ordered nobody can remember what
>the sequence was and predict reliably what the sequence will be. This is
>incredibly important in games like poker or rummie where the cards pile up
>and players can see the sequence (and if they can remember it use it).

The "7 times" theorem uses the following model of a shuffle:

o The deck is cut into two parts, with the number of cards in each piece
    binomially distributed (with mean 26, of course).
o The resulting deck is then achieved by having cards fall from one or the
    other of the two parts; a card will fall from one of the parts with
    probability proportional to the number of cards remaining in the part.

   - Ian "Who took a course in Randomized Algorithms last year"