The Mark of Zeta
The Return of Zeta
Solitaire-y Sequences
The playing cards slip instantly, precisely, and soundlessly into place. No smudges or creases ever mar the crisp, bright faces heading the unnaturally tidy columns and rows. With no deck of cards to handle, shuffle, deal, sort, or position, there's only the point and click of a mouse pushed across a pad beside the computer's keyboard.
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 Canfield, 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 at a probabalistic analysis of solitaire, Harvard student Amy Rabb developed a program that could win about 8 percent of the games. When she played the same cards herself, she won 15 percent of the time.
In general, the computer versions typically 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, statistician Persi Diaconis has remarked.
Diaconis has studied a simple (practically mindless) version of solitaire called Floyd's game, named for computer scientist Bob Floyd, who invented it in 1964. Starting with a shuffled deck, the player turns up cards one by one, placing them in 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 the 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.
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 David Aldous commented in a paper 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 includes 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 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 two 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. Additional analysis shows that the formula works better when it incorporates the extra error term −n(1/6).
Finding the longest increasing subsequence plays an important role in a variety of scientific sorting tasks, including 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 noted.
Jinho Baik, Percy Deift, and Kurt Johansson explored the possible lengths of the longest increasing subsequences associated with random permutations, describing their results in a paper published in the Journal of the American Mathematical Society.
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. 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 noted.
In the end, an 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 remarked. "It allowed me to come in contact with mathematical tools and results ... that I never would have touched if I had not been interested in the original problem."
Originally posted July 5, 1999.
A Song About Pi
Row Your Boat
Juggling By Design
Averting Instant Insanity
Matrices, Circles, and Eigenthings
Lunar Shadows
MSRI Reflections
No comments:
Post a Comment