| | Ivars Peterson's MathTrek |
July 5, 1999
This is solitaire on the computer screen. Every day, countless people sneak in a game or two (or more) as a break from various chores or to cure a case of writer's block. For a game played with such regularity, it's natural to ask what your chances are of winning.
Called Klondike or Idiot's Delight, this form of solitaire has resisted mathematical analysis. Partly because Klondike involves player choice, no one has yet been able to construct a mathematical model of the game from which it is possible to deduce theoretical odds of winning.
Even computer simulations fail to capture the game's nuances. In one research effort, a Harvard student developed a program that could win about 8 percent of its games. When she played the same cards herself, she won 15 percent of the time.
In general, the computer versions now available do no more than let you play solitaire, showing you the cards and letting you move them around.
When confronted with a difficult problem, it's often useful to tackle a simpler problem that has some of the ingredients of the more complex situation, says statistician Persi Diaconis of Stanford University.
Diaconis has studied a simple (practically mindless) version of solitaire called Floyd's game, named for computer scientist Bob Floyd, who discovered it in 1964. Starting with a shuffled deck, the player turns up cards one by one, placing them into piles according to the rule that only a lower card can be played on top of a card already on the table (aces count as 1). When cards have the same face value, clubs beat hearts, which beat spades, which beat diamonds. The object is to end up with as few piles as possible.
Suppose the first card is a 6. The next card is a 5, so it goes on top of the 6. An 8 follows; it starts a new pile to the right of the first pile. A jack starts off a third pile to the right of the existing piles. A 9 goes on top of the jack, a 2 goes on top of the 5, a queen starts off a fourth pile, and so on, until the deck is exhausted.
The best strategy is to place each turned-up card on a pile as far to the left as possible. Once an ace appears atop a pile, no more cards can be added to that pile.
How many piles would you expect to get in a typical game? Here are the results from 10,000 games played by a computer.
| Piles | 18 | ||||||||||
| Games | 54 | 525 | 1746 | 2791 | 2503 | 1518 | 632 | 186 |
The average number of piles is 11.6. You would get only one pile if the cards were perfectly arranged to begin with.
Playing this game of solitaire also serves as a quick way to sort a deck of cards. It doesn't take long to lay out the cards in piles, each of which is strictly ordered. It's then easy to pick them up in sequence, starting with the aces. Indeed, the game is sometimes called patience sorting, where patience is the British term for solitaire.
"Whether this is the fastest practical method for sorting real cards (or alphabetizing final exams) is an interesting topic for coffee-room conversation," Diaconis and Stanford colleague David Aldous comment in a paper to be published in the Bulletin of the American Mathematical Society.
Mathematically, playing the game involves constructing increasing subsequences. For example, suppose you have just 9 cards numbered from 1 to 9. One possible shuffling, or permutation, of those cards is 5 2 1 3 6 9 7 4 8. This sequence contains various increasing subsequences, such as 5 6 9 or 1 3 6 7 8. The longest increasing subsequence consists of 5 cards. It turns out that the number of piles you get in the solitaire game equals the length of the longest increasing subsequence in the card sequence of the original shuffled deck.
Suppose you start with a shuffled deck. It contains a longest increasing subsequence of some length. Eventually, you play the first card of this subsequence. Cards that come later will have to go in different piles. Whatever that first card is, cards that are played on top of it have a lower value. As soon as a card of higher value comes up, it must start off a new pile. Hence, the cards in the longest increasing subsequence must go into different piles.
Mathematical analysis indicates that the most likely number of piles for a shuffled deck of n cards is roughly 2 times the square root of n. For n equal to 52, the average number of piles is 14.4, which is reasonably close to the computer simulation results. Additonal analysis shows that the formula works better when it incorporates the extra correction term -n(1/6).
Finding the longest increasing subsequence plays an important role in a variety of scientific sorting tasks, including the determination of matches between DNA strands. In such cases, the fastest way to identify that subsequence is, in effect, to play the solitaire game, Diaconis notes.
Mathematicians Jinho Baik and Percy Deift of the Courant Institute of Mathematical Sciences in New York and Kurt Johansson of the Royal Institute of Technology in Sweden have recently taken a fresh look at the possible lengths of the longest increasing subsequences associated with random permutations.
For example, suppose you start with five cards, numbered from 1 to 5. One possible permutation of those cards is the sequence 5 1 3 2 4. In this case, the longest increasing subsequences are 1 2 4 and 1 3 4. The length of that subsequence is 3. Other permutations of the five cards can give different values for the longest increasing subsequence.
Baik and his colleagues proved that the resulting distribution of lengths fits a relationship that can be derived from so-called random matrix theory to describe the quantum behavior of large atoms (see The Return of Zeta, June 21, 1999). Moreover, the formula for the average length of the longest increasing subsequence (or average number of piles in simplified solitaire) emerges naturally from their analysis.
Why there should be a connection between playing solitaire and random matrix theory, however, remains a mystery, Diaconis says.
In the end, the effort to solve a "wimpy" card-game problem--a highly simplified version of standard solitaire--led into all sorts of deep mathematics, from complex analysis to random matrix theory.
"The mathematics that came out in analyzing solitaire is just beautiful," Diaconis says. "It allowed me to come into contact with mathematical tools and results. . .that I never would have touched if I had not been interested in the original problem."
Copyright 1999 by Ivars Peterson
References:
Aldous, D., and P. Diaconis. In press. Longest increasing subsequences: From patience sorting to the Baik-Deift-Johansson theorem. Bulletin of the American Mathematical Society. Also available as Technical Report No. 1999-4, April 1999, Department of Statistics, Stanford University.
Baik, J., P. Deift, and K. Johansson. Preprint. On the distribution of the lengths of the longest increasing subsequence of random permutations. Available at http://xxx.lanl.gov/abs/math.CO/9810105.
Kuykendall, C. 1999. Analyzing solitaire. Science 283(Feb. 5):794.
Mackenzie, D. 1998. From solitaire, a clue to the world of prime numbers. Science 282(Nov. 27):1631.
Peterson, I. 1998. The Jungles of Randomness: A Mathematical Safari. New York: Wiley.
Rabb, A. 1988. A probabilistic analysis of the game of solitaire. Undergraduate Honors Thesis, Harvard University.
An online video of Persi Diaconis's lecture on mathematics and solitaire is available at http://www.msri.org/publications/video/fall98/mandm.html.
Comments are welcome. Please send messages to Ivars Peterson at ipeterson@maa.org.