5
$\begingroup$

This question arose in a true Argentine card game called truco. Sometimes we need to choose who will play because we are too much people, so we deal cards and the first to get the king, out of 4 players, will join the group and play. During the game, I was wondering if this way of selecting the player is fair enough. So this is not homework at all!

There is a stack of 40 cards containing 4 kings. 4 participants receive cards, each after another, and we stop as soon as a participant gets a king and wins.

Each card that is dealt stays in the table, it is not returned to the stack. For each participant, what is the probability of winning?

I think the solution is as follows (let me know if I am right):

For the first round of dealing the cards:

First participant:

1/10 of getting a king

Second participant:

(36/40) * (4/39)

Third participant:

(36/40) * (36/39) * (4/38)

Fourth participant

(36/40) * (36/39) * (36/38) * (4/37)

$\endgroup$
3
  • $\begingroup$ I am not sure what you mean by repart. Do you mean you are going to deal them all out so each gets 10 cards? Or deal them out just one to each participant? Or deal them out until either each participant gets exactly one king but count it as a fail when for the first time a participant gets two kings? Or something else? $\endgroup$
    – mdewey
    Apr 24 at 10:37
  • 2
    $\begingroup$ i will deal them until one of them gets a king, the first who gets the king wins $\endgroup$
    – Limbo
    Apr 24 at 10:39
  • 1
    $\begingroup$ Please edit that into your question as not everybody reads the comments. $\endgroup$
    – mdewey
    Apr 24 at 10:41

3 Answers 3

4
$\begingroup$

Provided the cards are well-shuffled, here's a fair version of the game:

One-king game

  1. Only one winning card in the stack ("the king").
  2. Number of cards in the stack is a multiple of the number of players.

In a Spanish-suited deck of 40 cards, you can achieve (1) by declaring only one card, e.g. the king of swords, is "the king". Deck

Standard gameplay has an "early stopping" rule: players immediately declare if they drew a king, and the game ends as soon as someone does. Here's a rule variation that picks the same winner but makes (un)fairness more obvious:

"Simultaneous reveal" game

  1. Players take turns to draw cards, each placing their cards face-down in a row in the order they were received.
  2. Once the whole stack is dealt, all cards are revealed, and the winner identified.

The rows of players' cards make a grid, a rearrangement of the deck photographed above. In this one-king, simultaneous reveal game we discover, once the cards are turned over, player 2 actually won on their 7th draw:

40 cards, 1 king

With early stopping, this game would end after the 26th card in the stack is drawn. But the king was equally likely to be in any of the 40 positions in the stack, so equally likely to be allocated to any position in the grid. Since all rows have the same number of cards, the king is equally likely to end up in any row — hence any player is equally likely to win, and the one-king game is fair. (We needed the "number of cards is multiple of number of players" rule, or else the grid isn't a rectangle and the first player unfairly draws one more card than the last player.)

What if there are multiple kings in the stack? Although the king of swords, king of cups, king of coins, and king of clubs are each distributed uniformly through the grid, just like in the one-king game, the distribution of the first-drawn king is not uniform. It is more likely to appear in an earlier draw (left of grid more likely than right) and drawn by an earlier player (top of grid more likely than bottom). This is clear from the way we determine the simultaneous reveal game's winner:

Simultaneous reveal game: rules for multiple kings

  1. The "winning draw" is the leftmost column of the grid which contains a king. If only one player received a king in the winning draw, they are the winner.
  2. When there are multiple kings in the winning draw, the players who received them go into a tie-breaker to decide who wins: -player 1 beats all 3 other players, -player 2 beats 2 other players (players 3 and 4), -player 3 beats 1 other player (player 4), -player 4 always loses.

That's obviously unfair — but these rules pick the same winner as early stopping does, so standard rules are biased in favour of early players when there are multiple kings in the stack! In the grid below, the first-drawn king was the 10th card in the stack. The 3rd draw is the winning draw; player 2 wins by rule (3) as no other player got a king in that draw. Under early stopping, we'd stop after drawing 10 cards and player 2 still wins on their 3rd draw.

king 10th in stack

In the arrangement of the stack below, the earliest kings are the 17th and 20th cards. Both appear in the winning (5th) draw. Under simultaneous reveal rule (4), player 1 beats player 4 by the tie-breaker "player 1 beats all other players". Under early stopping, player 1 beats player 4 because the game ends once the 17th card is drawn — player 4 never even gets the chance to see if they would get a king on their 5th draw, as player 1 has won already! Clearly early stopping and simultaneous reveal rules are equivalent.

kings 17th/20th

Rule (3) is actually fair. Imagine all arrangements of the stack with 1 king in the winning draw. We group similar-looking grids together if they agree in all columns except the winning draw. The arrangement we saw with 1 king in the 3rd draw is part of this set of 4:

arrangements with 1 king in 3rd draw

There are 4 ways to allocate 1 king between 4 players in the winning draw, so all such sets contain 4 arrangements. Each player wins exactly one arrangement in each set, as similar arrangements only differ in who gets the winning king. So each player wins in one quarter of the arrangements which have one king in the winning draw, as is fair.

The simultaneous reveal game's unfairness is entirely due to the rule (4) tiebreaker applying when multiple kings are in the winning draw. Our example with two kings in the winning draw is part of a set of six similar arrangements of the stack because there are ${4 \choose 2}=6$ ("4 choose 2") ways to allocate 2 kings between 4 players in the winning draw.

arrangements with 2 kings in 5th draw

In each such set of 6 equally likely arrangements, player 1 wins 3 grids, player 2 wins 2 grids, player 3 wins 1 grid, and player 4 wins 0 grids. Each set contains all possible pairings of which two players get kings in the winning draw, and the tiebreak (or early stopping) rule means player $i$ wins the $4-i$ of their match-ups that come against later players. Given that the winning draw contains 2 kings, player $i$ wins with conditional probability$\frac{4-i}{6}$, and these probabilities decline linearly in the order players take their turns: $\frac 3 6=\frac 1 2$, $\frac 2 6=\frac 1 3$, $\frac 1 6$, and $\frac 0 6=0$ for players 1, 2, 3, and 4 respectively. This also biases players' overall probabilities of winning, in a linear way: i.e. player 1's advantage over player 2 equals player 2's advantage over player 3, and so on.

Similarly, three kings in the winning draw can happen in ${4 \choose 3}=4$ ways, or all four kings can appear but only in ${4 \choose 4}=1$ way. Possible arrangements of the winning draw are:

3 or 4 kings

Given that there are 3 kings in the winning draw, the conditional probabilities of winning are $\frac{3}{4}$ for player 1, $\frac{1}{4}$ for player 2, and 0 for the others. If instead we are given that there are 4 kings in the winning draw, player 1 is certain to win. The possibility of three or four kings being allocated to the winning draw biases the players' overall winning probabilities in a non-linear way: player 1 gets a particular boost, but these cases are equally bad for players 3 and 4.

Let's write the event "player $i$ wins" as $W_i$, and the number of kings in the winning draw as the discrete random variable $K$. In summary:

Table 1: Probability of each player winning, given number of kings in winning draw

\begin{array}{|c|c|c|c|c|} \hline k&\Pr(W_1|K=k)&\Pr(W_2|K=k)&\Pr(W_3|K=k)&\Pr(W_4|K=k)\\ \hline 1&\frac{1}{4}&\frac{1}{4}&\frac{1}{4}&\frac{1}{4}\\ \hline 2&\frac{1}{2}&\frac{1}{3}&\frac{1}{6}&0\\ \hline 3&\frac{3}{4}&\frac{1}{4}&0&0\\ \hline 4&1&0&0&0 \\ \hline \end{array}

To find how likely each player is to win overall, we need the probability distribution of $K$, i.e. the probabilities of $K=1,2,3,4$. Let's start by finding the probability of the first king appearing in the third draw (which I'll denote by $D=3$), and this being the only king in that draw ($K=1$). In our grid, we want the probability of no kings in the first two columns (which I've coloured black), one king in the third column (red) and the remaining three kings in the seven remaining columns (blue).

urn

Overall there are ${40 \choose 4}=91\,390$ ways to arrange the four kings in the stack of forty cards. Out of these, the number of arrangements we want is ${8 \choose 0}{4 \choose 1}{28 \choose 3}$. There's only ${8 \choose 0}=1$ way to arrange the black section of the grid: all eight cards must be non-kings. But there are ${4 \choose 1}=4$ ways to ways to arrange one king (and three non-kings) in the red section of the grid, and ${28 \choose 3}=3\,276$ ways to arrange three kings in the blue section. The three coloured sections can be arranged independently of each other: if we wrote separate lists of the possible arrangements of each section, then we create a valid arrangement of the whole grid by picking one arrangement from the black list, one from the red list, and one from the blue list. The number of ways we can "mix and match" from the three lists is found by multiplying together the number of choices in each list: $1 \times 4 \times 3\,276 =13\,104$.

$$\Pr(D=3, K=1) =\frac{{8 \choose 0}{4 \choose 1}{28 \choose 3}}{{40 \choose 4}}=\frac{13104}{91390}\approx 0.143385 $$

(We can see this as an urn problem: imagine a jar containing balls labelled 1 to 40, representing positions in the stack of cards. We pull out, without replacement, four balls to tell us where to place the kings in the stack. Paint each ball the colour of the grid position it represents. We must select none of the 8 black balls, 1 of the 4 red balls, and 3 of the 28 blue ones. The probability can be found by the multivariate hypergeometric distribution formula.)

If the earliest kings are allocated to the fifth draw, in which two kings appear:

urn2

$$\Pr(D=5, K=2) =\frac{{16 \choose 0}{4 \choose 2}{20 \choose 2}}{{40 \choose 4}}=\frac{1140}{91390}\approx 0.012474 $$

To write a general formula for the probability that $D=d$ and $K=k$, we want none of the first $4(d-1)$ cards to be kings, $k$ of the $4$ cards in draw $d$ to be kings, and the remaining $4-k$ kings all to be in the remaining $4(10-d)$ cards:

urn3 $$\Pr(D=d, K=k) =\frac{{{4(d-1)}\choose 0}{4 \choose k}{{4(10-d)}\choose {4-k}}}{{40 \choose 4}}=\frac{{4 \choose k}{{4(10-d)}\choose {4-k}}}{{40 \choose 4}}$$

Note "anything choose zero makes one", so ${{4(d-1)}\choose 0}=1$. (There's only one way to arrange the black section so it has no kings: make each black card a non-king.)

Using Excel's COMBIN() function, and conditional formatting to add a simple heat map, I get this table for the joint probability distribution of $D$ and $K$ (click image to zoom).

Table 2: $\Pr(D=d, K=k)$ D,K table

The total row and column, which I plotted at the side, are the marginal distributions of $D$ and $K$.

The distribution of $D$ shows why the game is useful to quickly select one person from a group of four: over a third of the time, the process is completed in the players' first draws, and over 60% of the time in the first or second draws. The expected value $\mathbb{E}(D)=\sum_{d=1}^{10}d\Pr(D=d)$ shows the winning player makes, on average, 2.46 draws.

The distribution of $K$ shows the winning king is the only king in that draw about 85% of the time. When this happens we know each player has an equal chance of winning. As this is the case most of the time, our game should be "mostly fair". If, by coincidence, multiple kings were allocated to the winning draw, it's usually only two of them: triple coincidences are very rare, quadruple coincidences even rarer (about a one in nine thousand chance). While our game is biased in favour of earlier players, it's usually by two kings in the winning draw, so the bias should be "mostly linear".

By the law of total probability:

$$\Pr(W_i)=\sum_{k=1}^4 \Pr(W_i | K=k)\Pr(K=k)$$

The first player's probability of winning is: \begin{align} \Pr(W_1) &=\frac{1}{4}\times 0.848233\dots+\frac{1}{2}\times 0.143779\dots \\ & \quad+\frac{3}{4}\times 0.007878\dots+1 \times 0.000109\dots \\ \implies \Pr(W_1) &\approx 0.290 \\ \end{align}

Similarly $\Pr(W_2)\approx 0.262$, $\Pr(W_3)\approx 0.236$ and $\Pr(W_4)\approx 0.212$. Although these are all quite near a fair 0.25, the game is biased in favour of earlier players: the first player is 1.37 times more likely to win than the fourth. Each player's winning probability is about 0.025 higher than the next player, so the bias is indeed nearly linear:

P(Wi)

General formula

Suppose we have positive integer values of

  • $n_p$ players (number of grid rows when laid out like the simultaneous reveal game),
  • $n_c$ cards in the stack per player (number of grid columns; the stack has $n_p n_c$ cards overall),
  • $n_k$ "kings" in the stack (number of cards that win the game; not necessarily the 4 cards in a standard deck with a rank of king, as you might restrict only certain suits of king to win, or expand the number of winning cards by allowing other ranks to win).

As before, define

  • $W_i$ as the event that player $i$ wins, for $1 \le i \le n_p$,
  • $D$ as the number of cards drawn by the winning player, up to and including their first king, for $1 \le D \le n_c$,
  • $K$ as the number of kings in the $D$-th grid column, for $1 \le K \le \min(n_p, n_c)$ as there are only $n_p$ cards in the winning draw, and only $n_k$ kings in the stack.

To find the conditional probability $\Pr(W_i | K=k)$, consider the $n_p \choose k$ ways that $k$ kings in the winning draw can be allocated among the $n_p$ players. Out of these, the ways that lead to player $i$ winning require no kings for the first $i-1$ players, one king for player $i$, and $k-1$ kings for the remaining $n_p-i$ players:

$$\Pr(W_i | K=k) =\frac{{{i-1}\choose 0}{1 \choose 1}{{n_p-i}\choose {k-1}}}{n_p \choose k}=\frac{{n_p-i}\choose {k-1}}{n_p \choose k}$$

For our table of the joint distribution of $D$ and $K$: general urn

$$\Pr(D=d, K=k) =\frac{{{n_p(d-1)}\choose 0}{n_p \choose k}{{n_p(n_c-d)}\choose {n_k-k}}}{{{n_p n_c}\choose n_k}}=\frac{{n_p \choose k}{{n_p(n_c-d)}\choose {n_k-k}}}{{{n_p n_c}\choose n_k}}$$

As before, find the marginal distribution of $K$:

$$\Pr(K=k) =\sum_{d=1}^{n_c}\Pr(D=d, K=k) =\sum_{d=1}^{n_c}\frac{{n_p \choose k}{{n_p(n_c-d)}\choose {n_k-k}}}{{{n_p n_c}\choose n_k}}$$

Then by the law of total probability:

\begin{align} \Pr(W_i) &=\sum_{k=1}^{\min(n_p, n_c)}\Pr(W_i | K=k)\Pr(K=k)\\ &=\sum_{k=1}^{\min(n_p, n_c)}\left(\frac{{n_p-i}\choose {k-1}}{n_p \choose k}\sum_{d=1}^{n_c}\frac{{n_p \choose k}{{n_p(n_c-d)}\choose {n_k-k}}}{{{n_p n_c}\choose n_k}}\right)\\ \implies \Pr(W_i) &=\sum_{k=1}^{\min(n_p, n_c)}\left(\frac{{n_p-i}\choose {k-1}}{{{n_p n_c}\choose n_k}}\sum_{d=1}^{n_c}{{n_p(n_c-d)}\choose {n_k-k}}\right)\\ \end{align}

Fairer versions of the game

All the game's unfairness is due to the tiebreaker (equivalent to the early stopping rule) used when multiple kings are allocated to the winning draw. We can address that in several ways.

Ensure there's only one king in the winning draw

We already saw the game's fair if we only use one "king" in the stack.

Alternatively, replace early stopping with an equal draws rule: the game can only stop once every player has drawn the same number of cards. If only one player got a king in the most recent draw, they win. If zero or several kings appeared, players just continue drawing from the stack (or the stack is reshuffled and play starts again, if all kings have already been found).

These rules are fair, but slow down play. It takes longer to find the only king than the first of four, and the potential need to reshuffle is inconvenient.

Make multiple kings in the winning draw rarer

Try a larger deck: a 48-card Spanish deck or 52-card French deck spreads the 4 kings across more columns of the grid ($n_c$ is 12 and 13 respectively, instead of 10), so it's less likely two or more are in the same column. This makes the game fairer, but $\Pr(K=2)$ and the bias in winning probabilities fall only slowly as $n_c$ rises:

Table 3: effect of increasing $n_c$ vary n_c

Similarly we can reduce bias by using fewer "kings", e.g. only count kings of swords and coins as winning cards. This slows play but not as much as using only one king: on average the number of draws made by the winning player, $\mathbb{E}(D)$, is 2.46, 2.96, 3.81, 5.5 with 1, 2, 3, 4 kings in a 40-card stack.

Reverse direction of play after every round of drawing

Players 1, 2, 3, 4 draw their first cards in that order; their second draws are made in order 4, 3, 2, 1; the direction of play continues to switch after each draw is completed. This reduces the biasing effect of early stopping when multiple kings are in the same draw, by favouring early players if the winning draw $D$ is odd and late players if $D$ is even. Our table of $\Pr(D=d,K=k)$ shows when $K\ge2$, it's more likely $D$ is odd than even, so early players still have a slight advantage: the players' winning probabilities are 0.2571, 0.2510, 0.2470, 0.2449. The bias was slashed by about 80%, far more effective than reducing the number of kings to 2 or 3:

compare bias

This lets us keep the fast gameplay of early stopping (winning player still only needs a mean of 2.46 draws) while removing most unfairness. Alternatively, the following variant is totally fair:

Two-king game with early stopping and direction-switching

  1. Two winning cards in the stack ("the kings": e.g. use kings of swords and coins; kings of cups and clubs don't count).
  2. Number of cards in the stack is double a multiple of the number of players (so grid has even number of columns, $n_c$).
  3. Players take turns to draw cards, switching direction of play after all have drawn a card (first player to draw a card is last to draw their 2nd card, but first to draw their 3rd, etc).
  4. First player to draw a king wins.

When $K=1$ the game is fair. When $K=2$ the winning draw is equally likely to be in an odd or even column: group "similar" grids based on which rows the kings are in, and each set will have $n_c$ grids with different winning draws, half even and half odd.

2 kings table 2 kings, switching

In all $n_p \choose 2$ pairings of which 2 players got kings in the winning draw, each player has an equal number of ways to win. So the game is fair when $K=2$ too.

Approximate formula

Writing combinations in terms of factorials,

$${n \choose r}=\frac{n!}{r!(n-r)!}=\frac{n(n-1)\dots(n-(r-1))}{r!}$$

This lets us write polynomial approximations for combinations. Consider:

$$\Pr(K=k)=\frac{n_p \choose k}{n_p n_c \choose n_k}\sum_{d =1}^{n_c}{n_p(n_c-d)\choose n_k-k}$$

This depends on $n_c$ only in the sum and denominator. Treating $n_p$, $n_k$ and $k$ as constants, the denominator is polynomial in $n_c$ with degree $n_k$:

$${n_p n_c \choose n_k}=\frac{1}{{n_k}!}(n_p n_c)(n_p n_c-1)\dots (n_p n_c-(n_k-1))$$

In big O notation,

$${n_p n_c \choose n_k}=\frac{n_p^k}{{n_k}!}n_c^k+O(n_c^{k-1})$$

In $\sum_{d =1}^{n_c}{n_p(n_c-d)\choose n_k-k}$ we sum over the index $d =1, 2, \dots, n_c$. But the summand only depends on $d$ via $n_c-d$, which will run down through the values $n_c-1,n_c-2,\dots,0$. It's convenient to take this sum in reverse order, and run through the values $m-1$ over $m=1,2,\dots,n_c$ where $m-1=n_c-d$ so $m=n_c+1-d$. \begin{align} \sum_{d =1}^{n_c}{n_p(n_c-d)\choose n_k-k}&=\sum_{m=1}^{n_c}{n_p(m-1)\choose n_k-k}\\ &=\sum_{m =1}^{n_c}\frac{(n_p(m-1))(n_p(m-1)-1)\dots(n_p(m-1)-(n_k-k-1))}{(n_k-k)!}\\ &=\sum_{m=1}^{n_c}\left(\frac{n_p^{n_k-k}}{(n_k-k)!}m^{n_k-k}+O(m^{n_k-k-1})\right)\\ \end{align}

A consequence of Faulhaber's formula is that when we sum a polynomial of degree $d$, we increase the power on the leading term by one, divide by the new power, and substitute in the upper limit (quite like integration in calculus), followed by lower order terms:

$$\sum_{m=1}^n \left(a_d m^d+a_{d-1}m^{d-1}+\dots+a_1 m+a_0 \right) =\frac{a_d}{d+1}n^{d+1}+O(n^d)$$

Well-known examples are triangular and square pyramidal numbers: \begin{align} \sum_{m=1}^n m &=1+2+\dots+n=\frac{n(n+1)}{2}=\frac{1}{2}n^2+O(n)\\ \sum_{m=1}^n m^2 &=1^2+2^2+\dots+n^2 =\frac{n(n+1)(2n+1)}{6}=\frac{1}{3}n^3+O(n^2)\\ \end{align}

We get: \begin{align} \sum_{d=1}^{n_c}{n_p(n_c-d)\choose n_k-k}&=\sum_{m =1}^{n_c}\left(\frac{n_p^{n_k-k}}{(n_k-k)!}m^{n_k-k}+O(m^{n_k-k}-1)\right)\\ &=\frac{n_p^{n_k-k}}{(n_k-k)!(n_k-k+1)}n_c^{n_k-k+1}+O(n_c^{n_k-k})\\ &=\frac{n_p^{n_k-k}}{(n_k-k+1)!}n_c^{n_k-k+1}+O(n_c^{n_k-k}) \end{align}

To approximate the probability distribution of the number of kings in the winning draw, \begin{align} \Pr(K=k) &=\frac{n_p \choose k}{n_p n_c \choose n_k}\sum_{d =1}^{n_c}{n_p(n_c-d)\choose n_k-k}\\ &={n_p \choose k}\left(\frac{n_p^{n_k-k}}{(n_k-k+1)!}n_c^{n_k-k+1}+O(n_c^{n_k-k})\right)\bigg{/}\left(\frac{n_p^{n_k}}{n_k!}n_c^{n_k}+O(n_c^{n_k-1}) \right)\\ \Pr(K=k) &={n_p \choose k}\frac{{n_k}!}{(n_k-k+1)! n_p^k n_c^{k-1}}+O\left(\frac{1}{n_c^k}\right)\\ \end{align}

So $\Pr(K=k)$ is itself of order $O(1/n_c^{k-1})$, and the first term above gives an estimate with error of order $O(1/n_c^k)$. It makes sense $\Pr(K=1)$ is $O(1)$, since as we increase the stack size (without adding any king cards) $n_c \to \infty$, our kings are stretched across more columns, the chance of two or more kings coincidentally allocated to the winning column falls to zero, and $\Pr(K=1)\to 1$. As expected, $\Pr(K=2)\to0$ as $n_c \to \infty$ since it is $O(1/n_c)$, but this decay is rather slow — hence, in Table 3, expanding the stack from $n_c=10$ to $n_c=13$ only slightly reduced $\Pr(K=1)$ and did little to make the game fairer. Since $\Pr(K=3)$ is $O(1/n_c^2)$ and $\Pr(K=4)$ is $O(1/n_c^3)$, the chances of a triple or quadruple coincidence of kings in the winning draw drop off to zero much faster, again seen in Table 3.

With the standard $n_p=4$, $n_k=4$, $n_c=10$, the first term of this approximation estimates the probabilities of 1, 2, 3, 4 kings in the winning draw as 1, 0.15, 0.0075, 0.0000938 respectively; the correct values are 0.848 , 0.144, 0.00788, 0.000109. Obviously these approximations are not very accurate — their errors were of order $O(1/n_c)$, $O(1/n_c^2)$, $O(1/n_c^3)$ and $O(1/n_c^4)$ respectively. But they do explain why bias in players' winning probabilities, i.e. deviation from a "fair" $1/n_p$ for each player, was mostly driven by the case $K=2$:

\begin{align} \Pr(W_i)-\frac{1}{n_p}&=\sum_{k=1}^{\min(n_p, n_k)}\Pr(W_i | K=k)\Pr(K=k)-\frac{1}{n_p}\\ &=\sum_{k=1}^{\min(n_p, n_k)}\Pr(W_i | K=k)\Pr(K=k)-\frac{1}{n_p}\left(\sum_{k=1}^{\min(n_p, n_k)}\Pr(K=k)\right)\\ &=\sum_{k=1}^{\min(n_p, n_k)}\left(\Pr(W_i | K=k)-\frac{1}{n_p}\right)\Pr(K=k)\\ &=\sum_{k=\color{red}{2}}^{\min(n_p, n_k)}\left(\frac{{n_p-i}\choose {k-1}}{n_p \choose k}-\frac{1}{n_p}\right)\Pr(K=k)\\ \end{align}

where we used $\sum_{k=1}^{\min(n_p, n_k)}\Pr(K=k) =1$ and the summation can start at $k=2$, since $\Pr(W_i | K =1) =1/n_p$ so the summand is zero for $k=1$. Note that if $\min(n_p,n_k)=1$, this means the entire sum vanishes so the bias is zero.

If $\min(n_p,n_k)\ge 2$, the summand depends on $n_c$ only via $\Pr(K=k)$, which is of order $O(1/n_c^{k-1})$. Hence only the $k=2$ term can make a contribution of order $O(1/n_c)$; other terms are $O(1/n_c^2)$ or smaller, so can be neglected provided the number of cards per player in the stack, $n_c$, is reasonably large:

\begin{align} \Pr(W_i)-\frac{1}{n_p}&=\left(\frac{{n_p-i}\choose {2-1}}{n_p \choose 2}-\frac{1}{n_p}\right)\Pr(K=2)+O\left(\frac{1}{n_c^2}\right)\\ &=\left(\frac{{n_p-i}\choose 1}{n_p \choose 2}-\frac{1}{n_p}\right)\left({n_p \choose 2}\frac{{n_k}!}{(n_k-2+1)! n_p^2 n_c^{2-1}}\right)+O\left(\frac{1}{n_c^2}\right)\\ &=\left(n_p-i-\frac{1}{n_p}{n_p \choose 2}\right)\left(\frac{{n_k}!}{(n_k-1)! n_p^2 n_c}\right)+O\left(\frac{1}{n_c^2}\right)\\ &=\left(n_p-i-\frac{1}{n_p}\cdot \frac{n_p(n_p-1)}{2}\right)\left(\frac{{n_k}}{n_p^2 n_c}\right)+O\left(\frac{1}{n_c^2}\right)\\ &=\frac{1}{2}\left(2n_p-2i-(n_p-1)\right)\left(\frac{{n_k}}{n_p^2 n_c}\right)+O\left(\frac{1}{n_c^2}\right)\\ \Pr(W_i)-\frac{1}{n_p}&=\frac{{n_k}}{2 n_p^2 n_c}(n_p+1-2i)+O\left(\frac{1}{n_c^2}\right)\\ \end{align}

We see that in general the bias is an approximately linear and decreasing function of $i$, i.e. the bias favours early players with relatively even steps between consecutive players.

Whether $i$ is "early" or "late" depends on $n_p$. The third player was relatively late if there are 4 players, which decreased their probability of winning, $\Pr(W_3)$. But player 3 would be in the middle if $n_p=5$ and gets a slight advantage from being an early player if $n_p=8$. We can define the relative positional advantage of player $i$ so that $a(1) =+1$ for the first player, $a(n_p) =-1$ for the last player, and $a((n_p+1)/2) =0$ if there's a "middle" player (when $n_p$ is odd). Other players should be assigned their advantage in a linear manner, in the range $-1 \le a(i)\le 1$. We can do this by finding the ratio between how far player $i$ is from the middle position, compared to how far player 1 is:

$$a(i)=\frac{(n_p+1)/2-i}{(n_p+1)/2-1}=\frac{n_p+1-2i}{n_p+1-2}=\frac{n_p+1-2i}{n_p-1}$$

Writing bias in terms of $a(i)$:

\begin{align} \Pr(W_i) &=\frac{1}{n_p}+\frac{n_k}{2 n_p^2 n_c}(n_p-1) a(i)+O\left(\frac{1}{n_c^2}\right)\\ \Pr(W_i) &=\frac{1}{n_p}+\frac{1}{2}\left(\frac{n_k}{n_p n_c}\right)\left(1-\frac{1}{n_p}\right) a(i)+O\left(\frac{1}{n_c^2}\right)\\ \end{align}

Here $n_k/(n_p n_c)$ is the fraction of cards in the stack which are kings, and $(1-1/n_p)$ is a proportionate reduction by the reciprocal of the number of players: 25% reduction for 4 players, about 33% for 3 players, 50% for 2 players. Half their product is, approximately, the maximum bias for or against a player; their product itself is the approximate difference in winning probability between first and last players:

$$\Pr(W_1)-\Pr(W_{n_p})\approx \left(\frac{n_k}{n_p n_c}\right)\left(1-\frac{1}{n_p}\right)$$

Under standard rules, 10% of cards are kings and there are 4 players so a 25% reduction, hence the gap between first and last players' winning probabilities should be about about 0.075; this is reasonably close to the true value of about 0.0779. Estimated winning probabilities of players 1, 2, 3, 4 are 0.2875, 0.2625, 0.2375, 0.2125 respectively; compared to true values 0.2900, 0.2620, 0.2360, 0.2121 we see these are accurate to 2 decimal places and not far wrong in the 3rd digit.

The error is $O(1/n_c^2)$ so is small when $n_c$ is reasonably large — even for 10 cards per player it's quite good, but the graph below shows it's even better when $n_c$ is 15 or 20. We could improve the accuracy of our approximations by calculating, rather than neglecting, the $O(1/n_c^2)$ terms. This would help our approximation capture the extra boost the first player gets from the case $K=3$, which is the most notable error in the approximation in the graphs below. Reducing the error from $O(1/n_c^2)$ to $O(1/n_c^3)$ would also improve the fit for lower values of $n_c$, for which the players' winning probabilities are less linear in $i$.

approx error

A 40-card deck can be equally shared between 2, 4, 5, 8 or 10 players. Our approximation works quite well for varying $n_p$, but when many players share the same deck, the number of cards per player drops, so the $O(1/n_c^2)$ error becomes larger:

40 cards, different np

Increasing the number of players also makes $(1-1/n_p)\to1$, so the linear bias we approximated will rise towards half the proportion of kings in the stack, 0.05 for a 40-card stack with 10 kings. And with more players drawing in each round, $K\ge3$ becomes more likely, increasing the nonlinear bias in favour of early players (which drove the error we saw in the graph above):

bias for np

So while it's straightforward to expand the game from 4 to 5, 8 or 10 players sharing the same deck, the game gets less fair. You can switch direction of play after each round of draws to counteract this.

$\endgroup$
2
  • 2
    $\begingroup$ thank you very much, the explanation (even I could not follow to the end...) is amaizing $\endgroup$
    – Limbo
    Apr 30 at 14:09
  • $\begingroup$ @Limbo I've tried to rewrite so there's a "high school"/Excel way of calculating the winning probabilities, and moved the higher level maths to the end. I finished with a proof that the bias is mostly driven by the % of cards in the stack which are kings. I also discovered you can get rid of 80% of the game's bias if you switch the direction of play each the time the players have drawn a card! So, draw the 1st card in order player 1, player 2, player 3, player 4; 2nd card in order 4,3,2,1; 3rd card in order 1,2,3,4 etc. Interesting how powerful such a simple rule change would be :) $\endgroup$
    – Silverfish
    May 9 at 14:30
3
$\begingroup$

Let's generalize slightly by assuming we have $n$ kings and $N$ total cards. On the first round, we have:

$$\begin{eqnarray} P(\text{player 1 wins}) &=& {n \over N} \\ P(\text{player 2 wins}) &=& {N-n \over N}{n \over N-1} &< {n \over N} \text{ if } n > 1\\ P(\text{player 3 wins}) &=& {N-1-n\over N-1}{N-n \over N}{n \over N-2} &< {n \over N} \text{ if } n > 1\\ P(\text{player 4 wins}) &=& {N-2-n\over N-2}{N-1-n\over N-1}{N-n \over N}{n \over N-3} &< {n \over N} \text{ if } n > 1\\ \end{eqnarray}$$

where the inequalities can be verified by substituting $n=1$ and cancelling terms.

Assuming we reach the second round, we have exactly the same situation, only with $N = N - 4$. Since, on every round, the probability of player 1 winning is greater than the probability of any other player winning (if $n > 1$), we can conclude that overall the probability of player 1 winning is greater than the probability of any other player winning, and the game is unfair.

Also note that we can analyze a two-player game between players 3 and 4 conditional upon neither player 1 nor player 2 having won in a round; clearly, this is the same as player 1 vs player 2, just with $N = N - 2$. We can extend this analysis to show that, for $n > 1$, the probability that a player wins is strictly greater the earlier in the round they draw.

$\endgroup$
2
  • 1
    $\begingroup$ A really nice feature of this approach is that we don't need the number of cards to be a multiple of the number of players! (It is "obvious" that when $N$ is not a multiple of $n$ this can only disadvantage later players - they may have one less card to draw than earlier players - but it's convenient you don't need to be handle it by caving out a special case in the algebra. At the final draw, those players unfortunate enough to miss out just get a zero in the numerator of their victory probability.) $\endgroup$
    – Silverfish
    Apr 29 at 3:52
  • $\begingroup$ @Silverfish - I hadn't actually thought of that! (+1) $\endgroup$
    – jbowman
    Apr 29 at 14:44
0
$\begingroup$

Let's look at the probability for player 1:

$P(n = 1) = 4/40 $ (probability that player 1 wins in the 1st round)

$P(n = 2) = (36/40) \times (35/39) \times (34/38) \times (33/37) \times (4/36) $ (probability that player 1 wins in the 2nd round)

Generalizing for n = k {k=2,3,...9,10}

$$p(n = k) = \dfrac{36 \times 35 \times 34 \times \cdots (41 - 4k))}{40 \times 39 \times 38 \times \cdots(45-4k)} \times \dfrac{1}{11 - k}$$

Therefore, probability that player 1 wins is:

$$P(\text{player 1 wins}) = \left(\dfrac{1}{10} + \sum_{k=2}^{k=10} \dfrac{36 \times 35 \times 34 \times \cdots (41 - 4k)}{40 \times 39 \times 38 \times \cdots (45-4k)} \times \dfrac{1}{11 - k}\right)$$

Probabilities for other players can be calculated similarly.

$\endgroup$
1
  • 2
    $\begingroup$ So, the probability of player 1 will win is greather than for the rest of the players? $\endgroup$
    – Limbo
    Apr 27 at 6:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.