2. NEW AGE SOLITAIRE

In the game New Age Solitaire, you pass through a deck of cards held face down and make two piles, Yin and Yang. The Yin pile will consist of the suits Hearts and Clubs in the order Ace to King of Hearts, followed by Ace to King of Clubs; the Yang pile will have the Diamonds and Spades suits, in the order Ace to King of Spades followed by Ace to King of Diamonds. Cards can only be placed on the piles in this order. You consider the cards in the order of the deck you are given. If you cannot place a card on the Yin or the Yang pile, it is put on a third pile. You win if the Yin pile is finished before the Yang pile. If neither of the piles is finished after all of the cards in the deck have been considered, you pick up the third pile, turn it over, and continue with these cards. Note that turning the pile of remaining cards implies that the order in which you consider these cards is the same as the original order of the cards.

In a new deck of cards, bought in the United States, the cards, when held face down, are in the order Ace to King of Hearts, Ace to King of Clubs, King to Ace of Diamonds, and King to Ace of Spades. Note that the Yang pile has a disadvantage if a new deck is used; in a new deck, the cards for the Yin pile are in such an order that you can add them all in the first pass, whereas for the Yang pile, only one card can be added in each pass through the deck.

Obviously, this game can be played with any deck of cards, not just with a new deck. It is interesting to study this game when a new deck is used, however, to see how an unfavorable ordering of the cards before shuffling can still be noticed even after as many as seven shuffles. It has been shown by simulation that the probability of winning this game is about 80% when using a new deck that has been riffle shuffled seven times.

In one variation of the game, it is assumed that an additional cut is performed after shuffling. Our main focus in this article is on the probability of winning New Age Solitaire when using a new deck that has been riffle shuffled, and we will make a point as to why this is the most interesting situation to be studied. We will, however, also consider the probability of winning after seven shuffles and an additional cut.

Another variation of this game, which can also be found on the Internet, is the making of four piles instead of two, one for each suit. Winning the game is then defined as finishing both the Hearts and Clubs piles, before Diamonds and Spades. We will also consider this game in Section 6, where we will argue that this version of the game also constitutes a less interesting case.

3. GSR SHUFFLE

For ease of notation, we will assume henceforth that the cards are numbered 1,…,n. Moreover, we will assume that the cards are in this order in a new deck (i.e., before shuffling). This implies that the Yin pile will be made by adding the cards 1,…,n/2 in this order, and the Yang pile will be made by adding the cards n,n − 1,…,n/2 + 1 in this order (i.e., in the order that is the reverse of the numbering of the cards).

Notation: We will write π = (π₁ π₂ ··· π_n) for a permutation of length n, where π_j is the number on the card in position j. Inversely, denote by pos(i,π) the position of the card numbered i in permutation π. (pos(i,π) = π_i⁻¹, where π⁻¹ is the algebraic inverse of π.) Where there is no risk of confusion, we will write pos(i).

The most commonly studied model of shuffling is the Uniform Riffle Shuffle, also known as the GSR shuffle, introduced by and named after Gilbert, Shannon, and Reeds [2,4]. When performing a riffle shuffle, a deck is cut into two piles. The piles are taken in the left and right hand, respectively, and the cards from the two hands are then interleaved. The characteristic features of the GSR model are the binomial (n, p = ½) distribution of the position of the cut and the assumption that the probability that the next card comes from the left or right hand is proportional to the number of cards in that hand. For more details, we refer the reader to Bayer and Diaconis [1].

Bayer and Diaconis [1] showed that the probability of obtaining a certain ordering after k GSR shuffles only depends on the number of rising sequences in this ordering.

Definition: A rising sequence is a maximal sequence of card numbers i,i + 1,…, i + j, such that pos(i) < pos(i + 1) < ··· < pos(i + j).

Note that maximal implies that pos(i − 1) > pos(i) for i > 1 and pos(i + j + 1) < pos(i + j) for i + j < n.

We will also use the notion of descending sequence:

Definition: A descending sequence is a maximal sequence of card numbers i,i − 1,…,i − j, such that pos(i) < pos(i − 1) < ··· < pos(i − j).

We have the following “cute” relationship between the number of rising sequences and the number of descending sequences in a permutation.

Lemma: Let r be the number of rising sequences and d be the number of descending sequences in a permutation of length n. We have the relationship r + d = n + 1.

The proof is given in the Appendix.

Proposition (Bayer and Diaconis [1]): The probability that s GSR shuffles on a new deck result in a permutation π is

where r is the number of rising sequences in π.

Even though the proof gives insight in the mechanics of the GSR shuffle, we will omit it because it is not needed for this article.

To evaluate the “degree of randomness” after s shuffles, the probability distribution on the permutations after s shuffles is compared to the uniform probability distribution on the permutations. The usual way to compare two probability distributions is the variation distance, which is just one-half the L₁-norm:

where Q*^s denotes the probability distribution on the permutations after s shuffles, U denotes the uniform probability distribution, and

is the set of all possible permutations of length n. Note that

, which we will use later.

By the proposition, we can express the variation distance after s GSR shuffles as

where A_n,r is the number of permutations of length n, with exactly r rising sequences. It turns out that A_n,r are the Euler numbers, as shown by Tanny [5].

4. WINNING NEW AGE SOLITAIRE

The main result of this article is the fact that winning New Age Solitaire only depends on the number of rising sequences in the deck. Henceforth, we will assume that the number of cards in the deck, n, is even.

Lemma: Let r be the number of rising sequences in a deck of n cards. Then, you will win New Age Solitaire using this deck if and only if (iff) r ≤ n/2.

Proof: Consider the deck restricted to cards 1,2,…,n/2. Note that the number of rounds needed to complete the Yin pile equals the number of rising sequences in this restricted deck, say r₁. Similarly, the number of descending sequences in the deck restricted to cards n/2 + 1,n/2 + 2,…,n, equals the number of rounds needed to complete the Yang pile, say d₂. Note that you win the game, if r₁ < d₂, or r₁ = d₂ and pos(n/2) < pos(n/2 + 1).

Denote by r₂ the number of rising sequences in the deck restricted to cards n/2 + 1,n/2 + 2,…,n. Note that the total number of rising sequences in the deck is equal to r₁ + r₂ − 1{pos(n/2) < pos(n/2 + 1)}, where 1 is the indicator function. By the lemma in Section 3, r₂ = n/2 + 1 − d₂. Combining these two equalities gives

By the proposition in Section 3, we can now give a closed-form solution for the probability of winning New Age Solitaire, using a new deck that is shuffled s times, using the GSR shuffle.

Corollary: The probability of winning New Age Solitaire with a new deck of size n that is GSR shuffled s times equals

where A_n,r are the Euler numbers.

Plugging in the numbers yields a probability of approximately 0.807 of winning after GSR shuffling a deck of 52 cards 7 times.

5. RELATION TO THE VARIATION DISTANCE

Lemma: Let Q*^s be the distribution on the permutations after s GSR shuffles and let U be the uniform distribution on the permutations. For s “big enough” (Mann [3] suggests s > 2 log₂ n), we have

Proof: Since the function

is nonincreasing in r, there exists a “crossover point” v for which

for all r ≤ v and

for all r > v.

Consequently, the variation distance is equal to

It is easy to see that the crossover point v is nondecreasing in s and will move to n/2 for n even. Following Mann [3], v equals n/2 for s > 2 log₂ n.

Therefore, for s “big enough,” the probability of winning New Age Solitaire after s GSR shuffles is

The first equality uses the symmetry in the Euler numbers (i.e., A_n,r = A_n,n+1−r) and, therefore,

. █

Note that it is impossible to devise a game where the difference between the probability of winning with a nonuniformly distributed deck and a uniformly distributed deck would be greater than the variation distance between the two, as can be seen by the “max set” description of the variation distance: Any deterministic card game can be seen as a partitioning of the permutation space into a winning set and a losing set. It is easy to see that this result can be extended to games with random strategies.

Hence, New Age Solitaire exactly pinpoints the Achilles' heel of the GSR shuffle.

6. VARIATIONS ON CIRCUMSTANCES AND GAME RULES

In this section, we will consider two variations that can be found on the Internet, for example. In the first variation, the game is the same but the deck of cards used is a new deck of cards that has been riffle shuffled seven times followed by an additional cut. The second variation is a variation on the rules of the game. Instead of making two piles of cards, one with the cards Ace to King of Hearts followed by Ace to King of Clubs and one with Ace to King of Spades followed by Ace to King of Diamonds, the player now makes four piles, one for each suit. The player is said to win if the Hearts and Clubs are both finished before the Spades and Diamonds piles.

We will show that both of these variations make a less interesting object for analysis. The relationship between the probability of winning and the variation distance between the distribution after GSR shuffles and the uniform distribution (and not so much the amusement value for the player!) is obviously the reason why this game is of interest. We will show that this relationship does not hold for the two variations (i.e., that the probability of winning for these variations is strictly less than the probability of winning for the “basic” game).

6.1. Probability of Winning After s GSR Shuffles and an Additional Cut

The analysis of the probability of winning when the deck is cut after the shuffles are performed is a bit more involved. We can derive the probability of winning, however.

Notation: Let π be a permutation. Denote by π^(c) the permutation that is the result of cutting the permutation right after position c and concatenating the two pieces in opposite order; that is, for π = (1 2 3 ··· n),

From here on, let rs(π) denote the number of rising sequences of π.

The following lemma is proved in the Appendix.

Lemma: Let π be a permutation. Then,

Note that this implies that the number of rising sequences can neither increase nor decrease by more than one, due to a cut.

We will now focus our attention on the GSR shuffle. In this case, we know that the probability of a permutation after shuffling only depends on the number of rising sequences of the permutation. We will derive an expression for the number of permutations with r rising sequences, in which a cut causes an increase or decrease in the number of rising sequences. Next, we will use these to calculate the probability of winning New Age Solitaire (i.e., that the deck after shuffling and an additional cut has n/2 rising sequences or less).

Let us define the following numbers:

By the above lemma, we have for all c,

and

It is not hard to see that we can indeed compute the numbers B_n,r,i,j for all n, r, i, and j, by setting up recursive relations. In the Appendix, we will outline a way to do this.

Corollary: The probability of winning New Age Solitaire with a new deck of size n that is GSR shuffled s times followed by a binomial (n, p = ½) cut equals

where A_n,r are the Euler numbers (the number of permutations of length n with r rising sequences).

Proof: To see the above result, first note that you win New Age Solitaire if the number of rising sequences after the cut is at most n/2. In other words, you win if the number of rising sequences before the cut is at most n/2, except when the number of rising sequences before the cut is n/2 and the cut causes an increase in the number of rising sequences, or if the number of rising sequences before the cut is n/2 + 1 and the cut causes a decrease in the number of rising sequences; that is, let π be the permutation before the cut and let the random variable C be the position of the cut, then

Now, note that B_n,r,i,j = B_{n,n+1−r,j,i}. This can be seen by considering permutations

and remembering that the number of rising sequences in a permutation plus the number of descending sequences add up to n + 1.

Therefore, we can write

Finally, since

and thus

, this is equal to

Using the probability distribution for the binomial cut gives the above equality.

Now, note that all terms, except maybe B_n,n/2,i,j, are strictly positive. Also, it is easy to see that B_n,n/2,1,n = A_n−2,n/2, which is strictly positive for n = 4,6,…. For n = 2, B_2,1,1,2 = 1. Therefore, the above probability is strictly less than

(for all n even), which is the probability of winning without the additional cut. █

Plugging in the same numbers as earlier, gives a probability of approximately 0.793 of winning after GSR shuffling a deck of 52 cards 7 times followed by a binomial (n = 52, p = ½) cut.

6.2. New Age Solitaire with Four Piles

A variation on the rules of New Age Solitaire has the player make four piles instead of just two. Each pile must be made by adding the cards of one suit in the order Ace to King. In this version, the player is said to win if the Hearts and Clubs piles (the Yin piles) are finished before the Diamonds and Spades piles (the Yang piles) are both finished. We will call this version of the game Four-Pile Solitaire.

Lemma: The probability of winning Four-Pile Solitaire with a deck that is shuffled using s GSR shuffles is strictly less than the probability of winning New Age Solitaire with a deck that is shuffled using s GSR shuffles.

Proof: Define W_n,r as the number of permutations with r rising sequences for which you will win Four-Pile New Age Solitaire. Let L_n,r = A_n,r − W_n,r (the number of “losing permutations”). The probability of winning the four-pile version after s GSR-shuffles can then be expressed as

Now, note that L_n,r = W_n,n+1−r, because for each permutation σ = (σ₁ σ₂ ··· σ_n) with r rising sequences, which is losing, there exists a permutation

, which has n + 1 − r rising sequences, which is winning, and vice versa.

where the last inequality follows from the fact that r is at most n/2 and the fact that for all n ≥ 4, there exists an r ≤ n/2 such that L_n,r > 0: for example, the permutation

has n/2 rising sequences and is losing. █