NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/rec/games/bridge/6619

Text File | 1992-11-20 | 3.3 KB | 91 lines

Newsgroups: rec.games.bridge
Path: sparky!uunet!zaphod.mps.ohio-state.edu!wupost!eclnews!spot!geppo
From: [e-mail] (Giuseppe Bianchi)
Subject: Re: Which inference is better, WAS - "finesse or play for the drop"
Message-ID: <[e-mail]>
Sender: [e-mail] (News Administrator)
Nntp-Posting-Host: spot
Organization: Washington University, St. Louis MO
References: <[e-mail]> <[e-mail]> <[e-mail]>
Date: Fri, 20 Nov 1992 20:43:25 GMT
Lines: 78

In article <[e-mail]> [e-mail] (Adam Beneschan) writes:
>
>Didn't some researcher just determine recently that if you shuffle the
>cards 7 times (I think), that the result will be close to a perfect
>random shuffle?  I remember reading something about this but I don't
>recall the details.  Perhaps someone out there who's familiar with
>this study can enlighten me.
>

I make a public response because maybe that someone else than Adam is
interested.
The number of shuffle required for a deck of n cards is
k, where k is the smallest exponent that satisfies the rule
      k
     2  >= n

Thus in the case of 52 cards, k=6.  (*** not 7 ***)
This is a well known (old) result mainly used in interconnection network
theory.



How to explain this? suppose, for simplicity, a deck of exactly 64 cards
(the case of 52 can be included - with some work - in this).

At every shuffle, you suppose to operate a PERFECT SHUFFLE permutation,
that is, divide exactly the deck in two parts, and the i-th card of every
sub-deck (starting the numeration with 0) is supposed to have equal
probability to go in one of the two position 2*i, 2*i+1 of the shuffled
deck.
For an example, with 8 cards (A, B, ...H), after a shuffle the possible
deck distributions are (A,E),(B,F),(C,G),(D,H), where every pair can be
taken in both  orders.



Going a little bit further, given an initial card of this 64 card deck
in the position (in binary representation, for simplicity)
   abcdef   (a...f = 0 or 1)
it is easy to see that, after a perfect shuffle, the next position of this
card is
  bcdefx
with x 0 or 1 with equal probability.
After a second shuffle, the next position will be
  cdefxx
and so on up to the 6th shuffle, where a card starting form a given
position can be found in any else position.
  [with 52 cards, this algorithm must be adapted, and loses the simplicity
   of binary representation]



some examples:
1) if you start with an ace as a first card, after the next shuffle it will
   be equally likely in 1th or 2nd pos, after the second shuffle in one of the
   first four, and so on.

2) If the ace is the third card of the dech, after the first shuffle it will
   be 5th or 6th, after the second in 9th, 10th, 11th, 12th, and so on with
   the given permutation rule.




OF COURSE THIS IS THE THEORY!!!!! In reality a hand made shuffle is
FAR to represent a perfect shuffle permutation (clustering, uneven deck
split, etc).
Thus the minimum number of shuffle must be raised to a certain value
depending on the type of pseudo-shuffle permutation used (who knows
what is this permutation for a hand shuffle??!!)



BTW: returning to the shuffle generators, a valid and low computational
     cost shuffle algorithm can be built using 6 runs of perfect shuffle.

Giuseppe.