Suppose our cards have values $\{1,2,\dots,n\}$ and the deck contains $m_i$ cards with value $i$. The total number of cards in the deck is equal to $m = m_1 +\dots+m_n$, and we assume $m$ is even so that the deck can be evenly split in half. In a standard deck of playing cards, we have $n=13$ and $m_1=m_2=\dots=m_n = 4$.
Rather than thinking about “how many games we would expect to play before I had a flawless game”, let’s instead work out the probability that a game of War will be flawless for me (I wins in $m/2$ turns with no ties). This is a counting problem: how many ways are there of arranging the cards in the deck so that I win flawlessly?
To this effect, define $f(m_1,\dots,m_n)$ to be the number of ways I can win flawlessly if the cards remaining have distribution $(m_1,\dots,m_n)$. We will develop a recursive formulation of $f$.
If I pick “$i$” in the first round, I will win the round with no tie if my opponent picks “$j$” with $j \lt i$. This can happen in $m_i m_j$ ways, and then I can win the remaining rounds flawlessly in $f(\dots)$ ways, where the arguments $m_i$ and $m_j$ are each decremented by $1$. Therefore, we can write:
\[
f(m_1,\dots,m_n) = \sum_{1 \leq j \lt i \leq n} m_i m_j f(m_1,\dots,m_j-1,\dots,m_i-1,\dots,m_n)
\]We also have the terminal condition $f(0,\dots,0)=1$, for if we ever achieve this condition, there are no cards left and we have won!
We can make two critical observations that will greatly simplify computation of $f$:
- We can prune out any zero entries. For example, $f(0,2,0,4,0,0) = f(2,4)$. This follows because when a particular card number is not present in the deck, we may relabel the numbers on the cards and simply skip over the missing number.
- We can rearrange arguments. For example, $f(6,4,1,7) = f(1,4,6,7)$. This is due to the fact that our recursive equation is symmetric in the arguments (all pairs of indices are included in the sum and contribute similarly to the count) and our base case $f(0,\dots,0)$ is symmetric as well.
Equipped with these tools, we can write very efficient code to compute the solution for the case of a standard deck of cards. Here is an efficient recursive implementation in Python that computes the solution for a standard deck of cards.
from itertools import combinations
def memoize(f):
memo = {}
def helper(x):
# prune zeros and sort!
y = tuple( sorted([z for z in x if z > 0]) )
if y not in memo:
memo[y] = f(y)
return memo[y]
return helper
@memoize
def winning_hands(counts):
N = len(counts)
if N == 0: # base case (no cards left in the deck)
return 1
out = 0
for i1,i2 in combinations(range(N),2):
tmp = list(counts)
tmp[i1] -= 1
tmp[i2] -= 1
out += counts[i1] * counts[i2] * winning_hands(tmp)
return out
winning_hands( 13 * [4] )
The code took about 100ms to compute the answer:
\[
252656585660288881535364185959261220490470307542335488000000
\]
We can divide this by the total number of hands (which is $m!$) to obtain the probability of winning flawlessly.
from math import factorial
from fractions import Fraction
Fraction( winning_hands(13 * [4]), factorial(52) )
And the result is:
\begin{align}
p &= \mathrm{Prob}(\text{flawless win}) \\
&= \frac{93686147409122073121}{29908397871631390876014250000} \\
&\approx 3.132436\times 10^{-9}
\end{align}
This is a very small number, but the more we play, the likelier we are to win. To quantify this, suppose we play $N$ games. The probability that we win flawlessly at least once is $1-(1-p)^N$. We can plot this as a function of $N$ to see how it grows:
So to have a $50\%$ chance of winning flawlessly at least once, I would have to play around 220 million times. To have a $95\%$ chance of winning flawlessly at least once, I would have to play around 1 billion times. Needless to say, that’s a lot of war.
Minor quibble.
This appears to be calculated as a one sided probability (winning all hands). As I read the Riddler for this week, losing all hands is also a 26 turn game. So, do you need to multiply the probability you found by 2? (I am wondering how long it will be until I see a 26 turn game, not how long it will be to see myself get a 26 turn game).
Thanks again for all of your wonderful write-ups! Clear illustration of what’s going on every time!
That is correct. To compute the probability that the game will last 26 turns with no wars, you would simply multiply my result by 2. The problem statement talks about a person claiming that they won a flawless game. So I wanted to assess the probability of that exact event occurring. i.e. how many games would that person have to play before they had a flawless win. I did not want to include the events where they would lose to an opponent that won flawlessly.
Nice write up of a complicated problem. With regard to the number of games before the probability hits 50% or 95%, you can use the approximation that 1 – 1/x = e^(-1/x) as another way to calculate these with less computation. Using the 50% prob, you solve for (1-1/x)^n = 0.5. Using the approximation, you could say (1-1/x)^n = (e^(-1/x))^n = e^(-n/x) = 0.5.
After some rearranging, you get n = -ln(0.50)*319,240,361 = 221,280,556.
For the 95% case, you could set n = -ln(0.05) * 319,240,361 = 956,358,653.
Great write up! I have a bit of trouble understanding the second observation of the rearrangement of f… although the coefficients are symmetric, the actual functions seem not to be… i.e. f(3, 2, 1) results in 3*f(2, 2, 0) + 2*f(3, 1, 0) + 6*f(1, 2, 1) while f(1, 2, 3) results in 3*f(0, 2, 2) + 6*f(1, 1, 2) + 2*f(0, 1, 3). It does not seem obvious to me that these two expressions should be equal, so I feel I must be missing something. Are you able to help me out?
Let’s use your example of a 6-card deck and say we want to show that $f(3,2,1) = f(1,2,3)$. The coefficients multiplying the $f$’s after we decompose each side are 3, 2, 6. Matching up the terms on both sides with equal coefficients, the equality will be true so long as $f(2,1,1) = f(1,1,2)$ and $f(2,2,0) = f(0,2,2)$ and $f(3,1,0) = f(0,1,3)$. Note that these three equalities all involve 4-card decks.
More generally, any $f(\ldots)$ for an $m$-card deck will decompose into a sum of terms involving $(m-2)$-card decks. We can continue recursively matching coefficients as far as possible, and we will end up with a bunch of terms that have all cards of the same type, e.g. $f(0,4,0,0,0)$ or $f(0,0,2,0)$, in which case the answer is zero (if the deck looks like that, games will always end in ties, not wins), or a term with no cards in the deck at all, e.g. $f(0,0,0)$, in which case the answer is 1.
More formally, you can prove the rearrangement property by using induction. First by showing that it holds for all 0-card decks (trivial), then all 2-card decks, then all 4-card decks, etc. When you get to $m$, applying the recursion reduces to the $m-2$ case, which you’ve already shown.
Something looks wrong! I tried it with n = 3 and m = 4.
I tried the simulation with 12 cards, n = 3 and 4 suits. Result is 2,903,040 wins over 12! = 479,001,600 games.
The answer by the above program is 1,244,160.
===========================================================================
import math win = 0 tot = 0 NUM_SUITS = 4 for i1 in range(12): for i2 in range((int(i1/NUM_SUITS) - 1) * NUM_SUITS): if i2 == i1: continue for i3 in range(12): if i3 in (i1, i2): continue for i4 in range((int(i3/NUM_SUITS) - 1) * NUM_SUITS): if i4 in (i1, i2, i3): continue for i5 in range(12): if i5 in (i1, i2, i3, i4): continue for i6 in range((int(i5/NUM_SUITS) - 1) * NUM_SUITS): if i6 in (i1, i2, i3, i4, i5): continue for i7 in range(12): if i7 in (i1, i2, i3, i4, i5, i6): continue for i8 in range((int(i7/NUM_SUITS) - 1) * NUM_SUITS): if i8 in (i1, i2, i3, i4, i5, i6, i7): continue for i9 in range(12): if i9 in (i1, i2, i3, i4, i5, i6, i7, i8): continue for i10 in range((int(i9/NUM_SUITS) - 1) * NUM_SUITS): if i10 in (i1, i2, i3, i4, i5, i6, i7, i8, i9): continue if int(i9/NUM_SUITS) > int(i10/NUM_SUITS): win += 1 for i11 in range(12): if i11 in (i1, i2, i3, i4, i5, i6, i7, i8, i9, i10): continue for i12 in range((int(i11/NUM_SUITS) - 1) * NUM_SUITS): if i10 in (i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11): continue win += 1 print(win, math.factorial(12))Hi S Kumar,
I reformatted your post because the tabs got lost and they’re rather important!
In any case, I tried running your code and I get win==0. Did I make a mistake in where I put the tabs?
If you want to preserve tab structure, post your code inside of a “pre” tag, i.e.
Thank makes a lot of sense! Thank you very much.