All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Riffling Chance (Posted on 2005-08-30)
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.)

 No Solution Yet Submitted by Sam Rating: 4.3333 (6 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Simulation | Comment 6 of 10 |

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.0606971210    1634        53248 0.0306866011    1993       106496 0.0187143212    4761       212992 0.0223529513   11910       425984 0.0279588014   14900       851968 0.0174889215   37862      1703936 0.0222203216   74158      3407872 0.0217607917  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.0618990410    1922        53248 0.0360952511    3381       106496 0.0317476712    6309       212992 0.0296208313   10334       425984 0.0242591314   21194       851968 0.0248765215   36527      1703936 0.0214368416   70822      3407872 0.0207818817  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.0997596210    4917        53248 0.0923415011    6764       106496 0.0635141212   11135       212992 0.0522789613   21089       425984 0.0495065514   41469       851968 0.0486743615   83129      1703936 0.0487864616  166258      3407872 0.0487864617  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

 Search: Search body:
Forums (0)