[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Playing Cards - Caution!
-----BEGIN PGP SIGNED MESSAGE-----
In article <[email protected]>,
Alan Bostick <[email protected]> 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-----