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

Home > Probability
Riffling Chance (Posted on 2005-08-30) Difficulty: 5 of 5
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.)
Some Thoughts 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.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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information