5
$\begingroup$

Two people, (call them C and D), decide to play a card game for fun. They use an ordinary fair deck of $52$ cards, shuffled well before each hand is drawn, and randomly draw cards from it one a time without replacement, both using (sharing) the same drawn cards to determine who wins. A win is defined as follows:

C wins if he gets at least one of all $13$ ranks of the cards (regardless of suit as they can be mixed suit or even all the same suit) in a hand.

D wins if he gets either $5$ reds or $5$ blacks in a row (consecutive) for a particular hand. Each new hand starts with $0$ in a row so far so there is no "carryover" from a previous hand.

It is possible that C and D can both "win" on the same card draw so normally that would be a tie but a "twist" in the game is that ties are awarded to C but not just as a single win. Since ties are likely rare, C gets a triple win for ties. That is, if C and D bet even money and they "tied", C would then win $3$ to $1$ odds of whatever D bet him for that particular hand. So let's take an example run so there is no confusion. Suppose they both bet $1$ dollar per hand and the following happens:

D wins game $1$ so he is then up by $1$ dollar.
C wins game $2$ so they are both back to even money.
D wins the next $2$ games so he is then up $2$ dollars over C (C is down $2$ dollars).
The next game is a tie so C is awarded $3$ dollars so is then ahead by $1$ dollar.

Another way to think about it is to not think about money but just count up the number of wins. If there is a tie, C gets awarded $3$ wins for that hand.

So the question is who has the mathematical advantage here and by how much? For example, if it was a rainy day and they played this game for many hands, who would likely be ahead as far as net money gained as a result of playing this game?

Some interesting things to consider are:

  • D can immediately win with only $5$ card draws while C requires $13$ minimum.
  • It is possible that D will not win even if all the cards are drawn, never getting $5$ in a row of either color.
  • A decision can take anywhere from $5$ to $49$ cards. $49$ is the max because imagine if $12$ of each rank (of all $4$ suits) have been chosen but D hasn't won yet for that hand, the next card will complete one of those set of ranks. For example, if the last $4$ cards in the deck are all Kings (K), the $49$th card will give the win to C (assuming D doesn't win or tie).

$$UPDATE$$ I ran a simulation of 1 billion decisions (ties included) and the results are as follows:

C won : $469,102,581$ times. (excluding triple wins for ties).
D won : $514,835,119$ times.
C,D tied : $16,062,300$ times. (C awarded triple win).
C won : $517,289,481$ times. (including triple wins for ties).

Advantage for C: about $0.48$%

Average # of cards drawn to make a decision is $20.579$.

So the triple win award for ties gives C a very slight edge over D but without that D has a decent advantage. So in theory, if they played this game for many hands, they would about break even. However, in the shortrun, someone could take a sizable lead. Sometime I may try about $10$ hands with actual cards and see what I get.

I would like to know how to set this problem up mathematically or if it is even possible. Perhaps we could first solve a simpler variation where we draw exactly $21$ random cards then check for a winner. Perhaps that will give us some insight into how to solve the more general question with a variable # of cards (from $5$ to $49$ is possible.).

Also, can someone tell me how to plot a graph on here because I have data for the # of wins of each # of cards drawn from $1$ to $52$. The numbers show some interesting patterns. Out of $1,000,000$ decisions, $5$ cards drawn accounts for the most wins at about $5$%. Next is very close between $23, 24,$ and $25$ cards which account for about $4.4$% each.

$\endgroup$
  • $\begingroup$ Can anyone at least comment on if this problem can be done "on paper" or if it is one of those "pure simulation" type problems because it is difficult "on paper"? $\endgroup$ – David Apr 20 '15 at 0:19
  • 2
    $\begingroup$ No, it probably cannot be done on paper. Even computing the exact probability seems hard, since a DFA would need to remember about $40$ bits of information, making it rather large (that's just for a single game!). One can come up with many different "fun games", so unless there is any other motivation, I don't see why one would bother to spend any more time on it, given that you can satisfy your curiosity using a computer simulation. $\endgroup$ – Yuval Filmus Apr 21 '15 at 4:29
  • $\begingroup$ What about the variation where we fix the number of drawn cards at $21$, would that simplify it at all? A win could only happen with at least $5$ cards drawn so we would only have to check from $5$ to $21$ cards drawn or we could even stop at $20$ to make it a little easier. I was hoping an approximation could be done on paper such as checking independent probabilities of C and D winning solo (not a competition), and somehow using that info to predict who will win when they compete. For example, what if I asked what are the chances of getting $5$ red or black cards in a row out of $20$? $\endgroup$ – David Apr 21 '15 at 5:58
  • $\begingroup$ Your last question seems amenable to analysis. Here the number of states is very reasonable, so the exact probability can be calculated, and perhaps there is even an analytic solution. If all you care about is approximation in the regime $n\to\infty$ (where $n$ is the size of the deck, say) then it is possible that with some effort good approximations can be given to the original problem, depending on the exact model. $\endgroup$ – Yuval Filmus Apr 21 '15 at 6:15
  • 1
    $\begingroup$ When cards are drawn without replacement, the number of states is much larger. That's the source of difficulty. $\endgroup$ – Yuval Filmus Apr 21 '15 at 6:36
1
$\begingroup$

I made an attempt to put it in rigourous mathematical form, I welcome others to review it, point out the mistakes and edit this post to fix it. First, let's look at a few ways as to how D can win: $$ \left( \begin{array}{ccccccccccc} 5 & \text{R} & \text{R} & \text{R} & \text{R} & \text{R} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 6 & \text{R} & \text{B} & \text{B} & \text{B} & \text{B} & \text{B} & \text{} & \text{} & \text{} & \text{} \\ 7 & \text{R} & \text{B} & \text{R} & \text{R} & \text{R} & \text{R} & \text{R} & \text{} & \text{} & \text{} \\ 8 & \text{R} & \text{B} & \text{R} & \text{B} & \text{B} & \text{B} & \text{B} & \text{B} & \text{} & \text{} \\ 9 & \text{R} & \text{B} & \text{R} & \text{B} & \text{R} & \text{R} & \text{R} & \text{R} & \text{R} & \text{} \\ 10 & \text{R} & \text{B} & \text{R} & \text{B} & \text{R} & \text{B} & \text{B} & \text{B} & \text{B} & \text{B} \\ \vdots & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 48 & \ldots & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ \end{array} \right) $$

So, the way $\mathcal{D}$ can win this game with $\mathit{n}$ draws is when he gets last 5 cards of same colour, $\mathcal{C}$ hasn't drawn the full suit of [1,13] cards and there is no tie with $\mathcal{C}$. Hence, first start of by getting the probability of Tie. To tie the game, the number of cards drawn $\mathit{d}\in $[13, 49] since if the game ends before 13 draws, then $\mathcal{D}$ must have won, similarly, if game continues for more than 49 draws, then only $\mathcal{C}$ can win.

$$ \begin{array}{cc} \mathcal{P}\text{}(Tie,\text{Draw}=\mathit{d})= \Bigg\{ & \begin{array}{cc} d-5\frac{\left(\, ^{52-13-1}P_{d-13}\right)\text{}\left(\, ^4P_1\right){}^8\left(\left(\, ^2P_1\right){}^5\times \text{}2\right)\text{}}{\, ^{52}P_d} & d\in [13,49]\\ 0 & otherwise \end{array} \end{array} $$

Let's take a moment to understand this expression. The part about $\left(\, ^2P_1\right){}^5$ means that we are reserving the last 5 draws of cards such that they are of same colour, and they complete the sequence of 9-13, and since the colour does not matter, we multiply it by 2 and get $ \left(\left(\, ^2P_1\right){}^5\times 2\right)$. means that we reserve the penultimate 8 draws such that they complete the sequence 1-8.$\left(\, ^{52-13-1}P_{d-13}\right)\text{}$ means that for the beginning 'd-13' cards we don't care what cards are chosen as long as they don't contain the one card which needs to picked last to have the tie. Now, since the order of picking up the 'd-5' cards does not matter, so we multiply it by (d-5) and divide the whole term by $\, ^{52}P_d$\, ^{52}P_d$ which is the total number of ways in which you can pick 'd' cards out of a deck of cards.

Now, let's go the part where $\mathcal{D}$ wins the game. He can start winning the game from the beginning of fifth draw, upto $48^{th}$ draw, and this can be given by:

$$ \begin{array}{cc} \mathcal{P}(\text{D wins},\text{Draw}=\mathit{d})= \Bigg\{ & \begin{array}{cc} 2\frac{1-P(\text{Tie},d)\left(\, ^{26-\left\lfloor \frac{c}{2}\right\rfloor }P_5\right)\left(\prod _{i=0}^c \frac{\, ^{26-\left\lfloor \frac{c}{2}\right\rfloor }P_5}{\, ^{52-i}P_1}\right){}^m}{\, ^{52-c}P_5} & c=d-5,d\in [5,48],m= \begin{array}{cc} \big\{ & \begin{array}{rl} 0 & c\leq 0 \\ 1 & \text{otherwise} \\ \end{array} \\ \end{array} \\ 0 & otherwise \end{array} \end{array} $$

Now, let's try to understand this expression, first of we are multiplying the whole expression by 2, since the rest the of expression concentrates on only one colour, and since $\mathcal{D}$ can win either by drawing 5 Reds or 5 Blacks in a row. Next, we eliminate the ties by the expression (1-P[Tie, d]). The next expression is $\ ^{26-\left\lfloor \frac{c}{2}\right\rfloor }P_5$ which simply means that the last five cards drawn must be of same colour, and the expression $ \left(\prod _{i=0}^c \frac{\, ^{26-\left\lfloor \frac{c}{2}\right\rfloor }P_5}{\, ^{52-i}P_1}\right){}^m$ shows that we do not care about the initial 'd-5' draws. The expression $\left\lfloor \frac{c}{2}\right\rfloor$ is there because with each draw we eliminate 1 card of either Red or Black colour, so suppose we start with 52 cards and draw red, that means we will have 25 of Red to draw from and 26 Black to draw from, but the overall cards would have reduced to 51. So, for every two draw, we need to maintain the same number of coloured cards, yet decreasing the overall number by one. The denominator is self explanatory.

$$ \begin{array}{cc} \mathcal{P}(\text{Game ends},\text{Draw}=\mathit{d})= \Bigg\{ & \begin{array}{cc} (1-P(\mathcal{D} \text{wins},\text{Null}\text{Draw}=d))\times \text{Null}1-\text{Tie} (\text{Draw}=d) & d\in [13,48]\\ 0 & d<13 \end{array} \end{array} $$

This part is simple, If $\mathcal{D}$ does not win the game and there is no tie, then $\mathcal{C}$ automatically wins the game.

Having established the probabilities, let's look at the probability of game itself ending within the stipulated 'd' draw of cards:

$$ \begin{array}{cc} \mathcal{P}(\text{Game ends},\text{Draw}=\mathit{d})= \Bigg\{ & \begin{array}{cc} \frac{P(\mathcal{D} \text{wins},\text{Draw}=d)+P(\mathcal{C} \text{wins},\text{Draw}=d)+P(\text{Tie},\text{Draw}=d)}{\sum _{i=1}^{52} ((P(\mathcal{D} \text{wins},\text{Draw}=i)+P(\mathcal{C} \text{wins},\text{Draw}=i)+P(\text{Tie},\text{Draw}=i))} & d\in [5,48]\\ 0 & d<5\\ 1 & d>49 \end{array} \end{array} $$

This is nothing but the probability of either $\mathcal{C}$ or $\mathcal{D}$ winning the game or having a tie with 'd' draws, divided by the total probability of the same event for d$\in $[1,52]. With this we can establish the expected gains of both players: $$ E(\mathcal{D})=\sum _{d=1}^{52} (1-\mathcal{P}(\text{Game ends},\text{Draw}=\mathit{d}))[1\times \mathcal{P}(\mathcal{D} \text{wins},\text{Draw}=\mathit{d})-1\times \mathcal{P}(\mathcal{C} \text{ wins},\text{Draw}=\mathit{d})] $$

And similarly,

$$ E(\mathcal{C})=\sum _{d=1}^{52} (1-\mathcal{P}\text{}(\text{Game ends},\text{}\text{Draw}=\mathit{d}))[1\times \mathcal{P}\text{}(\mathcal{C} \text{wins},\text{}\text{Draw}=\mathit{d})\text{}+\text{}3\times \mathcal{P}\text{}(\text{Tie},\text{}\text{Draw}=\mathit{d})\text{}-\text{}1\times \mathcal{P}\text{}(\mathcal{D} \text{wins},\text{}\text{Draw}=\mathit{d})] $$

Running this through, I got expected gains of $\mathcal{C}$ as 3.92 and $\mathcal{D}$ as -3.92.

Please feel free to point out any errors or wrong assumptions which I have made.

$\endgroup$
  • $\begingroup$ It seems like part of the difficulty of solving this problem mathematically is the very ride range of cards ($5$ to $49$ inclusive) that can provide a possible win, and the fact that C and D are competing with each other, thus it is not just computing the probability of each winning solo, but checking that the other person didn't win first or tie. My math skills are weak but if I had to try to solve this "on paper", I would start with "case $5$" ($5$ cards only drawn) and figure out the probability, then "case $6$".... Cases $5$ thru $12$ don't seem that hard but $13$ to $49$ seem to be. $\endgroup$ – David Apr 28 '15 at 6:23
  • $\begingroup$ It is fun to simulate this on a computer because it is easy to see the patterns. I have my program show all the results from $1$ to $52$ cards for C winning, D winning, and ties. Of course from $1$ to $4$ cards drawn and over $49$ cards drawn show up as all $0$s but that helps confirm the program is correct cuz those should be $0$s. $\endgroup$ – David Apr 28 '15 at 7:46
  • $\begingroup$ I agree this is a "nightmare" to solve mathematically because of all the interaction/dependencies between C and D and because of the wide range of cards contributing to wins and ties. When I made this game up, I just tried to pick something so that it would be close to "even/Steven" (50/50). If you take a deck of cards and try a few hands you will see. Even better would be to write a short computer program to play for you like I did. Even with as few as $1,000,000$ hands, some clear patterns show as well as some accurate percentages, probably 99+% accurate to the actual probabilities. $\endgroup$ – David Apr 28 '15 at 8:06
  • $\begingroup$ I would suspect that on a very fast computer using a fast running compiled language, even 1 trillion hands could be simulated in a reasonable amount of time. I don't have that setup so I limit my simulations to 1 billion hands. Depending on how good the random number generator is, the results can be "spot on". $\endgroup$ – David Apr 28 '15 at 8:10
  • $\begingroup$ Also, imagine if instead of just players C and D, I added 1 or 2 more (call them E and F). This "simple" problem of just 2 players (which is already a "bear" to solve mathematically) would likely be even harder because of more interaction between the players, especially if I made it so that each had about an equal chance to win overall. However with a computer it is easy, you simply define the winning conditions for each of C,D,E, and F and "let 'er rip". Perhaps I will try to find a condition for E to make it a fair 3 way competition. $\endgroup$ – David Apr 28 '15 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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