Kruskal Count and Kangaroo Method

The Kruskal Count is a probabilistic concept discovered by Martin Kruskal and popularized by Martin Gardner. It has applications ranging from magic tricks to code-breaking.

For instance, deal out a deck of cards on a table. Start at the first card, and whatever number is on it "walk" this many cards to the right, treating Ace as a 1 and face cards as 5. Repeat the "walk" from the new card, continuing until you near the end. Place a dollar there, and bet your friend that if they pick one of the first 10 cards and do this walk then they will end on the card you just put the money on. You will win about 80% of the time. If you count cards for the walk as you deal them out then your friend won't know how you decided where to put the dollar.

Why does this work? At each step your friend's walker has 10 cards it can reach, at least one of which appeared in your walk. Their walker is equally likely to be on any type of card from the deck (it was shuffled), so there is at least a 1/13 chance of stepping to the spot your walk visited. Since you both use the same rule for taking steps then they will subsequently continue along the same route as your walker and so end at the same card. This gives the key idea: each step they have a chance to reach a card your walker had visited, so eventually this will happen (if your deck is large enough), and from then on they follow the same walk.

John Pollard came up with the same concept independently and applied it to an important problem in cryptography, finding the Discrete Logarithm. For this problem the "deck" is a cyclic group, with elements ordered as they appear when listed from a generator, and the step size given by a hash function. The algorithm was amusingly called "The Lambda Method for Catching Kangaroos."

Together with a student, Alexander Frieden, we have put together a few online demonstrations of this phenomenon:

• Kruskal count card trick: A neat trick with a probabilistic motivation.
• Pollard's Kangaroo Method: The most efficient means of breaking certain codes and digital signature schemes.

Here are a few mathematical papers analyzing the notion of Kruskal Count:

• How long does it take to catch a wild kangaroo?
        R. Montenegro and P. Tetali.
        Proc. of 41st ACM Symposium on Theory of Computing (STOC 2009).
  
• The Kruskal Count.
        Jeffrey C. Lagarias, Eric Rains, and Robert J. Vanderbei.
        The Mathematics of Preference, Choice and Order (2009), pp. 371--391..