Re: shuffling algorithm

From: Michael Amling (nospam_at_nospam.com)
Date: 11/23/04 

Date: Tue, 23 Nov 2004 05:51:32 GMT

Joe Soap wrote:
> In response to what Paul Tomkins <tomkinsp@iinet.net.au> posted in
> news:41a0a186$0$25785$5a62ac22@per-qv1-newsreader-01.iinet.net.au:
>
>
>>There are three methods of shuffling cards that I can think of. When
>>done on a computer, they are all based on numbers generated by a
>>random or pseudo random number generator.
>
>
> You missed the easiest one:
>
> For i = 1 to 52, swap card #i with a randomly chosen card [of 52].

   This doesn't work. The smallest deck it fails for is a deck of three
cards.

Start with a deck ABC.
For i=1, there are three possible swaps,
ABC; BAC; CBA each have probability 1/3.

For i=2, there are three possible swaps,
BAC, ABC, ACB; ABC, BAC, BCA; BCA, CBA, CAB each have probability 1/9,
which combines to
BAC, ABC, ACB, BCA, CBA, CAB
2/9 2/9 1/9 2/9 1/9 1/9

Finally for i=3, there are three possible swaps, resulting in
  CAB BCA BAC, CBA ACB ABC, BCA ABC ACB,
2/27 2/27 2/27, 2/27 2/27 2/27, 1/27 1/27 1/27,

  ACB BAC BCA, ABC CAB CBA, BAC CBA CAB
2/27 2/27 2/27, 1/27 1/27 1/27, 1/27 1/27 1/27

which combine to give the final probabilities
  ABC ACB BAC BCA CAB CBA
4/27 5/27 5/27 5/27 4/27 4/27

--Mike Amling

Relevant Pages
Loading