Sunday, May 29, 2011

A Simulation of a Card Trick

Following up on a thought-provoking post by Xan entitled All roads lead to science, I thought it would be interesting to run a simulation of the card trick he described. Here's Xan's description of the card trick:
  • I put a deck of cards down face up on the table. Meanwhile you think of a secret number between 1 and 10 -- for exposition let's say you pick 4.
  • One by one, I discard cards from the top of the deck. When we get to the 4th card -- and let's call it your special card -- you look at the number. For exposition, let's say your special card happens to be a 7. Then 7 secretly becomes your new number. Note that I don't know your special card.
  • I keep flipping cards, and 7 cards later, you have a new special card and number yet again. Note that I still don't know your special card.
  • This process continues -- me flipping cards at a constant rate, you secretly updating your special card and counting up to the next one -- until I decide to stop.
But I don't just stop on any card. I stop on your current special card. Which I'm not supposed to know.
What's the trick? After a while, your initial choice of secret number doesn't matter for what your current secret number is. This is because the sequences of secret numbers will eventually overlap (by chance). After this point, you would have the same secret number sequence because you follow the same rules. For this reason, the magician can pick his own secret number and follow the same process as you, eventually following the same sequence of numbers as you.

To verify how robust this logic is, I wrote a little program in R to simulate this process on a randomly generated deck of 150 cards. In the plot below, each pane is a different ordering of the 150 cards. Within each pane, there are 10 line plots that tell how many cards until it is time to update the secret number (one lineplot for each initial secret number).



In each simulation, the secret numbers start out quite different, but after about 100 cards or so, the secret number is the same regardless of where you started. In I playing around with a couple of different runs of this program, there is the possibility that you could end up in a different place after 150 cards (I found one set of cards for which this was true within 2 minutes of playing), but this is usually a lingering possibility that would vanish if we expanded the number of cards.

Even so, the problem with nonconvergence in these special cases is usually that one starting point doesn't conform to the others (yet). Even in this case, the magician's probability of being on the same sequence as you is significantly better than 1/10.

2 comments:

  1. Nice! And thanks for sending me the code.

    Another question is what happens when you loop back to the beginning of the deck. Given a fixed deck size, I can imagine it taking a few times around the same deck to converge, and it's also possible that there will be more than one loop to get stuck in. We can also look at the chance of that happening as the deck size gets larger, or (equivalently?) as the allowable numbers on individual cards get smaller.

    Wikipedia is sort of like a very big deck of cards with small numbers, in the sense that the first link has to be "close" in subject to the article it's in.

    ReplyDelete
  2. Xan:

    My thoughts exactly on your other list of questions. The code was just my first attempt at getting at the intuition of the problem.

    As a fun side project, I want to make the coding experiment a little more "realistic" (i.e., make the cards conform to a real card deck and use something like resample() without replacement to shuffle the deck initially), then I'd like to actually compute the probability of the card trick "working" after one pass through the deck (and two, and so on). When I have something more complete, I'll probably post it on my metrics blog.

    ReplyDelete

Please feel free to share your ideas about this post in the open forum. Be mindful that comments in this blog are moderated. Please keep your comments respectful and on point.