When shuffling a deck of cards using a riffle shuffle, one divides the deck in two and lets the two halves riffle down to the table, interleaving as they do so. Assume that a person using this shuffle will always divide a deck of 52 cards exactly evenly, and that the riffle will start equally often from the left as from the right.
The expert dealer that I am, when I perform a riffle shuffle the cards from the two halves always interleave perfectly, the cards alternating from the left and right halves of the deck.
How many times must I shuffle the deck before the probability of correctly guessing the next card down in the deck after seeing a card chosen randomly from some place in the deck will be less than 1.97%? (If the cards were perfectly random, the probability of correctly guessing the next card would be 1/51 = 1.96%)
Bonus: What if there were a 10% chance that, as each card falls during the riffle, the card will be covered by another card from the same half, instead of strictly alternating?
(Assume that the person guessing knows the original order of the cards, the number of times the deck has been shuffled, and the probability of the cards interleaving perfectly.)
I assumed that "the riffle will start equally often from the left as from the right" was intended to represent equally likely, but determined at random. As such, I compared all possible sequences of left/right for any number of riffle shuffles done. The comparison was against a specific sequence that the guesser might choose to take as a reference. In a typical choice,something like the following happens:
L R L R L R L R R R L R R L R L L L L R
1 52 104 0.50000000
2 78 208 0.37500000
3 88 416 0.21153846
4 138 832 0.16586538
5 197 1664 0.11838942
6 218 3328 0.06550481
7 466 6656 0.07001202
8 429 13312 0.03222656
9 1616 26624 0.06069712
10 1634 53248 0.03068660
11 1993 106496 0.01871432
12 4761 212992 0.02235295
13 11910 425984 0.02795880
14 14900 851968 0.01748892
15 37862 1703936 0.02222032
16 74158 3407872 0.02176079
17 157535 6815744 0.02311340
where the first row shows the reference sequence of shuffles. The lines following show the number of shuffles, the number of cases where the card following in the reference deck matches the card following a given card in the trial deck, given both/all the possible shuffles up to that point, followed by the number of cards tested, and the probability (the ratio of these two).
If the riffles in the reference shuffle set are always from the right it still looks typical:
R R R R R R R R R R R R R R R R R R R R
1 52 104 0.50000000
2 78 208 0.37500000
3 90 416 0.21634615
4 148 832 0.17788462
5 281 1664 0.16887019
6 289 3328 0.08683894
7 450 6656 0.06760817
8 840 13312 0.06310096
9 1648 26624 0.06189904
10 1922 53248 0.03609525
11 3381 106496 0.03174767
12 6309 212992 0.02962083
13 10334 425984 0.02425913
14 21194 851968 0.02487652
15 36527 1703936 0.02143684
16 70822 3407872 0.02078188
17 139762 6815744 0.02050576
However, if the riffles in the reference set are always from the left it looks atypical:
L L L L L L L L L L L L L L L L L L L L
1 52 104 0.50000000
2 78 208 0.37500000
3 88 416 0.21153846
4 122 832 0.14663462
5 220 1664 0.13221154
6 426 3328 0.12800481
7 850 6656 0.12770433
8 1700 13312 0.12770433
9 2656 26624 0.09975962
10 4917 53248 0.09234150
11 6764 106496 0.06351412
12 11135 212992 0.05227896
13 21089 425984 0.04950655
14 41469 851968 0.04867436
15 83129 1703936 0.04878646
16 166258 3407872 0.04878646
17 292944 6815744 0.04298049
I can't imagine why it would be different for this sequence of reference shuffles (the ones that go on in the mind of the guesser). But if this difference is real, rather than a bug in the program (shown below), then the guesser would use this to try to maximize guessing ability, and even by the 17th shuffle the probability of a correct guess is over 4%. Carrying the simulation much further would require much more computer time.
DECLARE SUB doLevel (lvl#)
DECLARE SUB shuffle (deck#(), lvl#, side#)
DEFDBL A-Z
CLEAR , , 5000
DIM SHARED randShuf(20, 52)
DIM SHARED fixedShuf(20, 52)
DIM SHARED nextCard(20, 52)
DIM SHARED compCt(20)
DIM SHARED matchCt(20)
DIM SHARED fin(20)
'CLS
RANDOMIZE TIMER
FOR i = 1 TO 52
randShuf(0, i) = i
fixedShuf(0, i) = i
NEXT
FOR i = 1 TO 20
r = INT(RND(1) * 2)
shuffle fixedShuf(), i, r
IF r THEN PRINT "R "; : ELSE PRINT "L ";
FOR j = 1 TO 51
thisCard = fixedShuf(i, j)
nextCard(i, thisCard) = fixedShuf(i, j + 1)
NEXT
thisCard = fixedShuf(i, 52)
nextCard(i, thisCard) = fixedShuf(i, 1)
NEXT
PRINT
fin(0) = 1
doLevel 1
END
SUB doLevel (lvl)
FOR choice = 0 TO 1
shuffle randShuf(), lvl, choice
FOR i = 1 TO 52
compCt(lvl) = compCt(lvl) + 1
j = i + 1: IF j > 52 THEN j = 1
IF randShuf(lvl, j) = nextCard(lvl, randShuf(lvl, i)) THEN
matchCt(lvl) = matchCt(lvl) + 1
END IF
NEXT
IF choice = 1 THEN
IF fin(lvl - 1) THEN
fin(lvl) = 1
PRINT USING "## ####### ############ #.########"; lvl; matchCt(lvl); compCt(lvl); matchCt(lvl) / compCt(lvl)
END IF
END IF
IF lvl < 17 THEN
doLevel lvl + 1
END IF
NEXT
END SUB
SUB shuffle (deck(), lvl, side)
k = 0
FOR i = 1 TO 26
j = i + 26
k = k + 1
IF side THEN
deck(lvl, k) = deck(lvl - 1, j)
k = k + 1
deck(lvl, k) = deck(lvl - 1, i)
ELSE
deck(lvl, k) = deck(lvl - 1, i)
k = k + 1
deck(lvl, k) = deck(lvl - 1, j)
END IF
NEXT
END SUB
For consistently left or right riffle shuffles for the guesser's mental reference, replace
r = INT(RND(1) * 2)
with
r = 0
or
r = 1
respectively.
|
|
Posted by Charlie
on 2005-08-31 19:21:25 |
Simulation
