9
$\begingroup$

Two people, call them $A$ and $B$, decide to play a card game. They take 2 standard decks of playing cards and combine them into a "superdeck" of 104 cards, shuffle them well, and then draw 1 card at a time randomly without replacement. $A$ immediately wins if 13 cards of any single suit are drawn. $B$ immediately wins if at least 18 black and at least 18 red cards are drawn. If they both "win" on the same card draw it is a tie (no decision) and they start over with all 104 cards after reshuffling. They bet even money—dollar for dollar matching. Who, if anyone, has the advantage of winning and by how much?

Note that all cards are shared "community" cards so the players are not drawing their own set of cards.

If someone would like to comment on if and how the probability changes if they draw their cards in tandem, that would be very interesting and informative. For example, two cards would be drawn at a time, giving one to $A$ and one to $B$, and then checked if anyone won or if they tied. This is an optional bonus question and not required to earn the checkmark for best answer.

Simulating 1,000,000,000 (1 billion) decisions (including ties) of the original question (shared cards), I got the following winning percentages: $$ A\quad 38.7855918\%\\ B\quad 59.7770491\%\\ \textrm{Tie}\quad 1.4373591\% $$

Minimum # of cards : $14$ (A disappointment as I was expecting it to be $13$)
Maximum # of cards : $42$
Average # of cards : $37.1902$

Note that at "first glance", some people might think that $A$ has the advantage because $A$ can win with as few as 13 cards but B needs 36 cards at a minimum to win. However, look at how much $B$ is actually favored to win. Another thing that somewhat surprised me is the average number of cards for someone to win (or tie) is about 37, only about 1 card more than $B$'s minimum needed to win. That might also imply that $A$ has an advantage. What if I reworded the question to also state that the average number of cards for a decision is slightly over 37, would most people then think at first glance that $A$ has an advantage, possibly a huge one? Yet another thing that might mislead people into thinking that $A$ has a large advantage is that $A$ is guaranteed not to lose if at least 42 cards are drawn. At that point either $A$ has won or tied. Kudos to the person that suspected that $B$ was the favorite from the start because he didn't let these false biases sway him towards $A$ being the favorite.

UPDATE:

I ran the alternate simulation giving each player their own cards and got some interesting results. $B$ remains the favorite at about $57.1\%$ to $A$'s $36.8\%$ which means the ties more than quadrupled to about $6.1\%$. The average number of cards slightly more than doubled from about 37 to about 75 with a low of 28 and a high of 94 (in ten million decisions).

Perhaps one way to simplify getting the answer to this original problem is to start the game by immediately turning over 35 cards since $B$ cannot win with less than 36 cards. Check if $A$ won at 35 cards. If not, then draw cards 36 thru 42 one at a time checking for a winner. By draw 42 someone will have won or there is a tie. So would the prob of $A$ winning on a 35 card draw be: $$ \large \frac{4\times {26 \choose 13} \times {78 \choose 22}}{{104 \choose 35}} $$

That is about $10\%$. There may be two 13 card flushes in that but we don't care as long as there is at least 1.

Also it is interesting to note that in the original game with shared cards, $42$ cards is the max for a win or tie because of the $25+17$ situation but with separate hands, that doesn't happen so the max # of cards drawn can exceed $84$ (which is $2$ * $42$) and in my simulation is did exceed it as it maxxed out at $94$ cards, not $84$. For example, B could get $29$ black cards and $17$ red cards but A could have $12, 12, 11,$ and $11$ of each suit (respectively) so at that point, neither is a winner and $2$ more cards would be drawn (almost exhausting the deck of $104$). The max number of cards ever for the separate card variation of this game seems like $94$ but I am not certain yet.

Another interesting point is that simulation of the separate card variation is considerably slower because the average approximate number of cards needed is about double ($75$ vs. $37$) and can go as high as $94$ which is almost the entire deck so it becomes "harder" (slower).

$\endgroup$
  • $\begingroup$ I'm just curious. Did you get this problem from a book, or did you make it up? $\endgroup$ – Joel Reyes Noche Apr 8 '15 at 3:43
  • $\begingroup$ I made this one up from "scratch". $\endgroup$ – David Apr 8 '15 at 3:44
  • 1
    $\begingroup$ What have you tried? The chance that A wins on turn $n$ is that there have been $12$ cards of a suit drawn before, the new card is the same suit, and there haven't been $13$ cards of any other suit drawn. The chance that B wins on a turn is that $17$ cards of the color have already been drawn, the new draw is that color, and that at least $18$ cards of the other color have been drawn. As with many of these problems, the challenge is clearly expressing the conditions $\endgroup$ – Ross Millikan Apr 8 '15 at 3:55
  • 2
    $\begingroup$ @RossMillikan Both are conditioned on the other player not having won first, though - the two players' win conditions aren't independent. $\endgroup$ – Steven Stadnicki Apr 8 '15 at 3:56
  • 1
    $\begingroup$ @StevenStadnicki: Amusing. My impression was the opposite. This is evidence the constants were well chosen. $\endgroup$ – Ross Millikan Apr 8 '15 at 4:02
4
+150
$\begingroup$

Set $T_A, \ T_B$ the stopping times of getting the winning sequence for A and B. We are interested in $T_A=T_B,\ T_A<T_B,\ T_A>T_B$. Set $K(i) =$"the suit of the i-th card" and $X(i)=(X_1(i),...,X_4(i))=$"the number of cards of the four suits up to the i-th extraction".

So, after a bit of playing with the events, we get $P(T_A=T_B)=4 \sum_{i=1}^N P(T_A=T_B,\ K(T_A)=1,\ X(T_A-1) = x_n)$.

A bit of understanding of the formula. The variable $K(T_A)$ is the suit of the card that makes A close the sequence he is looking for. It can be each of the four suits, so $K(T_A) = 1, 2,3,4$. So $P(T_A=T_B)=P(T_A=T_B \ \bigcap \ (\cup_{i=1}^4 K(T_A)=i))=4\ P(T_A=T_B \ \bigcap \ K(T_A)=1)$.

This step basically says that, since the four suite are interchangeable, we can reduce the complexity, by fixing the suite of the last card and multiply by 4 (as the probability that the extraction will finish with 1 is the same as it will finish with 2, 3 or 4).

The variable $X(T_A-1)$ represents the numbers of cards extract, for each suite (is a 4 dimensional variable), before the last extraction. This variable will assume a finite number of 4-tuple (that I enumerated from 1 to N). Applying the same rule as before, we get the formula above.

An example might explain better. Considering the situation where we extract 12 cards of suit 1, 5 cards of suit 2, 9 cards of suit 3 and 9 cards of suit. Then we extract the next card and it is a 1. In this example, i have considered $x=(12,5,9,9)$. Note also that is not relevant the order the first 35 cards have occurred.

The point here is: what are all the 4-tuple which are compatible with: "the game ends with a tie" and "the last card is 1"? They satisfy the conditions:

$x_1 = 12 ,\ x_2=5,\ x_3+x_4 \geq 18,\ x_3,x_4 \leq 12$.

For the event $T_A<T_B,\ K(T_A)=1,\ X(T_A-1) = x_n$

the admissible $x_n$ are the one such that: $x_1=12,\ x_2\leq12,\ x_3\leq12,\ x_4\leq12$ so that A has not won yet and will win with the next 1. Also B has not to have won yet and has not to win with the next (final 1). This translate in (in conjunction with the above): $x_1+x_2<17 \text{ or } x_3+x_4<18$.

Finally $T_A>T_B,\ K(T_B)=1,\ X(T_B-1) = x_n$. In this case A has not to win: $x_1<12, \ x_2\leq12,\ x_3\leq12,\ x_4\leq12$ and B has to win on the next 1 meaning: $x_1+x_2=17, x_3+x_4 \geq 18$.

Now, given any $x_n=x$, all those probabilities are equal:

$$\frac{\binom{26}{x_1}\binom{26}{x_2}\binom{26}{x_3}\binom{26}{x_4}}{\binom{104}{\text{sum }x}} \frac{26-x_1}{104- \text{sum }x}.$$

So, given the numbers are small enough, I wrote the following R-code to calculate these probabilities:

f <- function(x){
choose(26,x[1])*choose(26,x[2])*choose(26,x[3])*choose(26,x[4]) /                
choose(104,sum(x)) * (26-x[1])/(104-sum(x))}

x <- 0:12
X <- expand.grid(x,x,x,x)

XTie <- X[ ((X[,1]==12) & (X[,2]==5) & (X[,3]+X[,4]>=18)),]
XA   <- X[ ((X[,1]==12) & ((X[,1]+X[,2]<17) | (X[,3]+X[,4]<18))),] 
XB   <- X[ ((X[,1] <12) & (X[,1]+X[,2]==17) & (X[,3]+X[,4]>=18)),]

pTie <- sum(apply(XTie,1,f)) * 4
pA   <- sum(apply(XA  ,1,f)) * 4
pB   <- sum(apply(XB  ,1,f)) * 4

pTie*100; pA*100; pB*100
[1] 1.441632
[1] 38.78894
[1] 59.76943
pTie + pA + pB
[1] 1

In this case the sum of the probability is 1 if numbers are rounded to 15 digits.

I have seen you have update the game. When I'll have a chance i will take a look.

I have made some amendments to improve the answer. I hope it is clear enough.

$\endgroup$
  • $\begingroup$ @David Well, of course if your probabilities comes from a simulation they will add up to 1. How big is your simulation? Can you repeat a couple of times so we can look at the probabilities to see how they compare with my calculations (and perhaps sharing the code). Also, I have seen you were analysing the time to make a decision. I think this should not be difficult from my code above. $\endgroup$ – Kolmo Apr 12 '15 at 8:19
  • $\begingroup$ I ran a simulation of 100 million decisions (including ties). I think your results, since they are very close to mine, are just some type of roundoff error. I disagree that numbers from a simulation will add up to 100% because someone could have a coding error. Rather than show my code, I will just explain it cuz that is clearer. It is super simple. I choose a random number from 1 to 104 without replacement, I count up how many of each suit and how many of each color I encounter and check for a winner after each card. Simulation is great cuz the computer actually "plays" the game. $\endgroup$ – David Apr 12 '15 at 10:50
  • $\begingroup$ I think pseudocode is better than showing actual code because different languages have different constructs and features that may make it hard for the viewer to read and understand. The idea is to get across the algorithm, not necessarily working code. In this case the game is so simple that showing code is not really necessary. A random # from 1 to 104 (or 0 to 103) simulates the card draws, mod 4 of that is the suit, and mod 2 is the color. The rest is just checking for a winner and looping. There are other ways to code it to such as 0 to 51 are black and 52 to 103 are red... Flexibility. $\endgroup$ – David Apr 12 '15 at 11:30
  • $\begingroup$ Also this problem works especially well in computer simulation because the suit is mod 4 and the card color is mod 2 and in many languages that have bitwise operators, these can be done efficiently or a table of the desired mod values can be prepopulated and then just referenced. $\endgroup$ – David Apr 13 '15 at 10:16
  • $\begingroup$ I am rerunning the simulation for 1 billion decisions. Reason is I want to get slightly more accurate percentages but also to see if I can get the case where I get a $13$ card decision (a quick win for A). This is rare but should happen. I think the probability if getting it is about $1$ in $294$ million decisions so in theory I should get about $3$ of those with $1$ billion decisions. I calculated the probability based on this formula: $$\frac {4 * {26 \choose 13}} {104 \choose 13}$$. Someone please tell me if it is wrong. Actually since it is $2$ identical decks mixed, it might be wrong. $\endgroup$ – David Apr 14 '15 at 9:56
6
$\begingroup$

The Python code below simulates matches with or without replacement. Based on one million matches with replacement, player A wins $56.8 \pm 0.1 \%$ of the time (and ties occur about $2\%$ of the time), consistent with the two existing answers. Based on one million matches without replacement, on the other hand -- which is OP's actual question -- player B wins $59.8 \pm 0.1 \%$ of the time (and ties occur about $1\%$ of the time). So drawing without replacement hurts player A enough to throw the advantage over to player B.

To see why this might be true, note that player A needs half the cards of some suit, while player B needs about a third of the cards of both colors... so if the draws are even across suits, player A needs to see $1/2$ of the deck, while player B only needs to see $1/3$. Drawing without replacement is "self-correcting", and tends to keep the number of cards drawn from different suits closer together (giving the edge to B). Drawing with replacement is not, allowing one suit to more easily random-walk into a big lead (giving the edge to A).


import random

rng = random.Random()

def getShuffledDeck(m, n, x):
  deck = []
  for i in xrange(m):
    for j in xrange(n * x):
      deck.append((i, j%n))
  rng.shuffle(deck)
  return deck

def playGame(repl=False, m=13, n=4, x=2, aa=13, bb=18):
  deck = getShuffledDeck(m, n, x)
  suitCts = [0 for suit in xrange(n)]
  colorCts = [0, 0]
  pos = -1
  while True:
    if repl: pos = rng.randrange(0, len(deck))
    else: pos += 1
    (rank, suit) = deck[pos]
    suitCts[suit] += 1
    colorCts[suit % 2] += 1
    awin = (max(suitCts) >= aa)
    bwin = (min(colorCts) >= bb)
    if (awin or bwin): return (awin, bwin)
  return (False, False)

def playGames(num, repl=False):
  ret = {}
  for i in xrange(num):
    win = playGame(repl)
    ret[win] = ret.get(win, 0) + 1
  return ret

$\endgroup$
  • $\begingroup$ I ran a simulation (but not using Python), and I also get about 59.8% (slightly in favor of B). Ties are rare at about 1.4%. This seems like another one of those problems where simulation is much easier than pencil and paper method. $\endgroup$ – David Apr 8 '15 at 6:30
  • $\begingroup$ I can also easily change my code to simulate replacement or not and the results are consistent with those of mjqxxxx. It is interesting how replacing cards makes a difference, giving the advantage to A, but not replacing them gives the advantage to B. The other interesting variation is does it make any difference if instead of sharing the "community cards", each player gets their own cards and bases their potential win on only their own cards? $\endgroup$ – David Apr 8 '15 at 6:37
3
$\begingroup$

I ran a Python simulation for an infinite deck, which is the same as if the draws are with replacement. Out of $10,000$ games I got $5728$ victories for A, $4069$ victories for B, and $203$ ties, close to David's calculation. I verified one game counted the individual cards correctly and twenty games counted the winner based on the card counts. A slight win for A. Here is the code if you care. plev is just the diagnostic print level.

import random  
def game(plev=0):  
    counta=[0,0,0,0] #count of cards in each suit#  
    countb=[0,0] #count of black and red#  
    awin=False  
    bwin=False  
    while True:  
        i=random.randint(0,3) #pick a suit#  
        counta[i]+=1 #add 1 to the proper suit#  
        countb[i/2]+=1 #add 1 to the proper color#  
        if max(counta)==13: awin=True  
        if min(countb)==18: bwin=True  
        if plev > 19:  
            print i, counta, countb, awin, bwin  
        if awin and not bwin: #a has wone and b has not#  
            if plev > 9: print counta, countb, awin, bwin  
            return 'a'  
        if bwin and not awin: #b has won and a has not#  
            if plev > 9: print counta, countb, awin, bwin  
            return 'b'  
        if awin and bwin: #it is a tie#  
            if plev > 9: print counta, countb, awin, bwin  
            return 'tie'  
def match(games,plev=0):  
    awins=0  
    bwins=0  
    ties=0  
    for i in range (games):  
        result=game(plev)  
        if result=='a': awins+=1  
        if result=='b': bwins+=1  
        if result=='tie': ties+=1  
    print awins, bwins, ties  
$\endgroup$
  • $\begingroup$ It appears to me your check for b winning is not correct. $\endgroup$ – David Apr 8 '15 at 5:38
  • $\begingroup$ @David: I realized I was just asking for one color to be at least $18$, not both. Fixed now, and in agreement with you. Slight edge to A. $\endgroup$ – Ross Millikan Apr 8 '15 at 5:52
  • $\begingroup$ You might want to fix your wording that states "A big win for B" since in your example A is actually the winner more than B. $\endgroup$ – David Apr 9 '15 at 7:40
  • $\begingroup$ @David: thanks. I had fixed the numbers, but missed that. $\endgroup$ – Ross Millikan Apr 9 '15 at 14:41
2
$\begingroup$

While this is only heuristic, we can get an interesting first take by considering how many cards of the 'larger' color B will have when they first satisfy the win condition. We treat the red vs. black cards as heads vs. tails coin flips (i.e., simplifying to draw with replacement); then after $N$ 'flips' the expected number of red cards is $\frac12N$ and the variance is $\sigma^2=\frac14N$ (i.e. $\sigma=\frac12\sqrt{N}$). The next approximation is to treat this as approximately normal, and to use results on the Half-normal distribution to figure out what the expected value of min(red, black) is (since min(red,black) and max(red,black) are symmetric). Since the expectation of a half-normal variate is $E=\frac{\sigma\sqrt{2}}{\sqrt{\pi}}$, we should figure on min(red,black) being approximately $\frac{N}{2}-\frac{\sqrt{N}}{\sqrt{2\pi}}\approx .5N-.4\sqrt{N}$. Setting this equal to 18 and solving suggests $N\approx 41$; in other words, when B gets 18 of their 'minimum' color they'll have (on average) approximately 23 of their 'maximum' color. Then there need to be no more than 13 cards in any individual pile, or else A has already won; we can use a normal approximation to the binomial again to figure out these probabilities. For $N=18$, $\sigma=\frac32\sqrt{2}\approx2.12$; this means that $A$ wins on the 'small' side if the result is more than approximately 1.9 standard deviations from the norm; the probability of this is (very approximately) 5%. Similarly, on the $N=23$ 'side', $\sigma \approx 2.4$ and so the extremal result is approximately .625 SDs from the mean; the probability of A winning on this 'side' is then about 53%.

Combined, these suggest that A possibly has a small edge, but of course the lack of replacement throws a wrench into the work here; overall, the odds look remarkably even.

$\endgroup$
  • $\begingroup$ I ran a simulation of 100,000,000 "decisions" and got the following results: A winning: 38.784257%, B winning 59.778720%, tie 1.437023%. The program is about 20 lines of code and if fun to play with cuz I can easily change it to simulate replacement or no replacement and/or change parameters such as 19 blacks and 19 reds required for B to win which then gives the advantage back to A but only very slightly and increases the ties up to about 2.25%. $\endgroup$ – David Apr 8 '15 at 13:12
  • $\begingroup$ The $100$ million decision rerun range widened to $14$ on the low end but stayed at $42$ on the high end but the average stayed at $37.19$ cards. It is somewhat surprising to me because it takes at least $36$ cards drawn for B to even have a chance at winning which is very close to $37.19$, yet B is the favorite to win by a "healthy" margin. $\endgroup$ – David Apr 9 '15 at 13:43
  • 1
    $\begingroup$ If there are more than $24$ cards of one color, then A's winning condition has been met. If there are at least $18$ cards of both colors, then B's winning condition has been met. Once $42$ cards have been played, if B hasn't won, then one color has less than $18$ cards, and so the other color has more than $24$, and A must have won. $\endgroup$ – mjqxxxx Apr 10 '15 at 1:31
  • 1
    $\begingroup$ @David So far as I know, there is no reasonable means to approach this problem mathematically - there are simply too many variables involved and too much coupling, particularly given the sampling-without-replacement nature of the problem. If the sampling were with replacement then at least there's a slightly more concrete version of my heuristic argument here to be had, but AFAIK what you're after simply doesn't exist $\endgroup$ – Steven Stadnicki Apr 10 '15 at 4:20
  • 1
    $\begingroup$ @David: I don't think you should be surprised. What you are calling mathematical solutions thrive on regularity-that is why it is easier to solve the with replacement case (because the deck doesn't change) than the without replacement case. Simulation doesn't care so much, because if you can describe the situation you can throw a bunch of random numbers very quickly. Two approaches, each solve some problems, some are still insoluble. $\endgroup$ – Ross Millikan Apr 13 '15 at 3:27
2
$\begingroup$

From 13 to 35 cards, player A has a chance of winning while player B does not. From 36 to 48 cards, both players have a chance to win or tie. On the 49th card, player A wins for sure (as opposed to the 42nd that you claim). This is due to the pigeonhole principle: a 48 card hand could include 12 of each suit, so the 49th card must make one suit count 13. On the 70th card, player B wins for sure (B could have 52 of one color, and 17 of the other. The 70th draw guarantees 18 of each). Finally, as the data shows, a hand of size 42 guarantees that either A or B will win (or tie).

To calculate the probability that A has not won at some point up to $H$ draws, we can think about a hand as a count of how many of each suit is in it. If we let $h,c,d,s$ represent the count of each suit in the hand, then the number of hands with that count is $\binom{26}{h} * \binom{26}{c} * \binom{26}{d} * \binom{26}{s}$. The total number of hands would be the sum of this expression for all $h,c,d,s <=26$ such that $h+c+d+s = H$ -- this is equal to $\binom{104}{H}$. The total number of hands where A does not win is the same formula restricted to $h,c,d,s < 13$. Then we subtract this from the total to get the number of winning hands.

Similarly for B, we can think about a hand as the distribution of red and black cards, but with only two variables $r,b$ and 52 of each to choose from: ie $\binom{52}{r} * \binom{52}{b}$. We want to sum all these values such that $r,b \ge 18$ and $r+b = H$.

Since A and B share hands, we also need to count the number of overlapping non-winning hands. To do this, we use the same formula for notA, but with the additional constraint that $h+d < 18$ and $c+s < 18$. We can also count the number of overlapping winning hands by negating our constraints.

Note that these results mean the probability that the event occurred at some point up to hand H. The probability that player A wins on exactly hand H is equal to the conditional probability that neither won on hand $H-1$, player A won on hand $H$, and both did not win on hand $H$. The probability of a tie is equal to the conditional probability that niether won on hand $H-1$, but both won on hand $H$.

Hand size: 35
A winning hands:    875816935792799067913677520
B winning hands:    0
AB both win:    0
AB do not win:  5824466077910326344645212520
Total hands:    5824466077910326344645212520
Probability A wins: 0.15036862
Probability B wins: 0
Probability both win: 0
Probability neither wins: 1

Hand size: 36
A winning hands:    2187651178880365105675308580
B winning hands:    1820897651953170094890722500
AB both win:    142265392956675598133160000
AB do not win:  7297276544784599224803786250
Total hands:    11163559982661458827236657330
Probability A wins: 0.19596358
Probability B wins: 0.16311084
Probability both win: 0.01274373
Probability neither wins: 0.65366931

Hand size: 37
A winning hands:    5140562828655596541853267120
B winning hands:    6516896859621871918556270000
AB both win:    777662543946706376569520000
AB do not win:  9637015796776783868919245000
Total hands:    20516812941107545952759262120
Probability A wins: 0.25055367
Probability B wins: 0.31763690
Probability both win: 0.03790367
Probability neither wins: 0.46971310

Hand size: 38
A winning hands:    11371534640110716298280913080
B winning hands:    16583787534879868803273455500
AB both win:    2937240057516237287701068000
AB do not win:  11156298594478430576538030000
Total hands:    36174380711952778390391330580
Probability A wins: 0.31435326
Probability B wins: 0.45844012
Probability both win: 0.08119669
Probability neither wins: 0.30840331

Hand size: 39
A winning hands:    23690714827333517325560337520
B winning hands:    35627336140083180992347849000
AB both win:    9013637288502121383132024000
AB do not win:  10913769064390124956655320000
Total hands:    61218182743304701891431482520
Probability A wins: 0.38698821
Probability B wins: 0.58197311
Probability both win: 0.14723791
Probability neither wins: 0.17827659

Hand size: 40
A winning hands:    46487893830302959963647058470
B winning hands:    68284216792403753485577822225
AB both win:    23655062504574195829192021600
AB do not win:  8362498839737622953543300000
Total hands:    99479546957870140573576159095
Probability A wins: 0.46731107
Probability B wins: 0.68641463
Probability both win: 0.23778820
Probability neither wins: 0.08406249

Hand size: 41
A winning hands:    85910617153854265768625366880
B winning hands:    119811369879258352469125806400
AB both win:    54462253713125886387171266400
AB do not win:  4025413150834950995978000000
Total hands:    155285146470821682846557906880
Probability A wins: 0.55324427
Probability B wins: 0.77155718
Probability both win: 0.35072417
Probability neither wins: 0.02592272

Hand size: 42
A winning hands:    149469721837112574467943550320
B winning hands:    195312503647991511458210679600
AB both win:    111854505778871561656317369600
AB do not win:  0
Total hands:    232927719706232524269836860320
Probability A wins: 0.64170002
Probability B wins: 0.83851121
Probability both win: 0.48021123
Probability neither wins: 0

Hand size: 43
A winning hands:    244715045843780655787896274880
B winning hands:    298674073002244768818180828000
AB both win:    207539848571922715193754188000
AB do not win:  0
Total hands:    335849270274102709412322914880
Probability A wins: 0.72864546
Probability B wins: 0.88930988
Probability both win: 0.61795534
Probability neither wins: 0

Hand size: 44
A winning hands:    376860795714204834746281144720
B winning hands:    431385093907717298743442357400
AB both win:    342636674014643377259003097400
AB do not win:  0
Total hands:    465609215607278756230720404720
Probability A wins: 0.80939291
Probability B wins: 0.92649604
Probability both win: 0.73588894
Probability neither wins: 0

Hand size: 45
A winning hands:    545804079983805943178849072960
B winning hands:    591482567719646428297316775840
AB both win:    516474360227080696501871975840
AB do not win:  0
Total hands:    620812287476371674974293872960
Probability A wins: 0.87917731
Probability B wins: 0.95275590
Probability both win: 0.83193321
Probability neither wins: 0

Hand size: 46
A winning hands:    743714191719739507973917271840
B winning hands:    772880007527858837939817663360
AB both win:    720334960962686849751053663360
AB do not win:  0
Total hands:    796259238284911496162681271840
Probability A wins: 0.93401013
Probability B wins: 0.97063867
Probability both win: 0.90464880
Probability neither wins: 0

Hand size: 47
A winning hands:    954779348149106412259124973760
B winning hands:    965300355892586485716310679040
AB both win:    937461920626270200583190679040
AB do not win:  0
Total hands:    982617783415422697392244973760
Probability A wins: 0.97166911
Probability B wins: 0.98237623
Probability both win: 0.95404534
Probability neither wins: 0

Hand size: 48
A winning hands:    1158159106785090614049190906340
B winning hands:    1154952335593086938765629404360
AB both win:    1146252824572363099661529404360
AB do not win:  0
Total hands:    1166858617805814453153290906340
Probability A wins: 0.99254450
Probability B wins: 0.98979629
Probability both win: 0.98234080
Probability neither wins: 0

Hand size: 49
A winning hands:    1333552706063787946460903892960
B winning hands:    1325964631130082475276750299840
AB both win:    1325964631130082475276750299840
AB do not win:  0
Total hands:    1333552706063787946460903892960
Probability A wins: 1.00000000
Probability B wins: 0.99430988
Probability both win: 0.99430988
Probability neither wins: 0

And here is the code:

import java.math.BigDecimal;
import java.math.BigInteger;


public class A {

    public static void main(String[] args) {

        for(int H=35; H<50; H++) {

            BigInteger AWIN = BigInteger.ZERO;
            for(int A=0; A<13; A++) {
                for(int B=0; B<13; B++)
                    for (int C=0; C<13; C++)
                        for (int D=0; D<13; D++)
                            if(A+B+C+D == H) {
                                BigInteger temp = BigInteger.ONE;
                                temp = temp.multiply((choose(26,A)));
                                temp = temp.multiply((choose(26,B)));
                                temp = temp.multiply((choose(26,C)));
                                temp = temp.multiply((choose(26,D)));
                                AWIN = AWIN.add(temp);
                            }
            }

            BigInteger BWIN = BigInteger.ZERO;
            if(H>35) {
                for(int R=18; R<H; R++) {
                    for(int B=18; B<H; B++)
                        if(R+B == H) {
                            BigInteger temp = BigInteger.ONE;
                            temp = temp.multiply((choose(52,R)));
                            temp = temp.multiply((choose(52,B)));
                            BWIN = BWIN.add(temp);
                        }
                }
            }

            BigInteger ABNOWIN = BigInteger.ZERO;
            if(H>35) {
                for(int A=0; A<13; A++) {
                    for(int B=0; B<13; B++)
                        for (int C=0; C<13; C++)
                            for (int D=0; D<13; D++)
                                if(A+B+C+D == H && (A+B < 18 || C+D < 18)) {
                                    BigInteger temp = BigInteger.ONE;
                                    temp = temp.multiply((choose(26,A)));
                                    temp = temp.multiply((choose(26,B)));
                                    temp = temp.multiply((choose(26,C)));
                                    temp = temp.multiply((choose(26,D)));
                                    ABNOWIN = ABNOWIN.add(temp);
                                }
                }
            }

            BigInteger ABWIN = BigInteger.ZERO;
            if(H>35) {
                for(int A=0; A<=26; A++) {
                    for(int B=0; B<=26; B++)
                        for (int C=0; C<=26; C++)
                            for (int D=0; D<=26; D++)
                                if(A+B+C+D == H && A+B >= 18 && C+D >= 18 && (A >= 13 || B >= 13 || C >= 13 || D >= 13)) {
                                    BigInteger temp = BigInteger.ONE;
                                    temp = temp.multiply((choose(26,A)));
                                    temp = temp.multiply((choose(26,B)));
                                    temp = temp.multiply((choose(26,C)));
                                    temp = temp.multiply((choose(26,D)));
                                    ABWIN = ABWIN.add(temp);
                                }
                }
            }

            BigInteger tot = BigInteger.ZERO;
            for(int A=0; A<=26; A++) {
                for(int B=0; B<=26; B++)
                    for (int C=0; C<=26; C++)
                        for (int D=0; D<=26; D++)
                            if(A+B+C+D == H) {
                                BigInteger temp = BigInteger.ONE;
                                temp = temp.multiply((choose(26,A)));
                                temp = temp.multiply((choose(26,B)));
                                temp = temp.multiply((choose(26,C)));
                                temp = temp.multiply((choose(26,D)));
                                tot = tot.add(temp);
                            }
            }

            AWIN = tot.subtract(AWIN);

            System.out.println("    Hand size: " + H);
            System.out.println("    A winning hands:\t" + AWIN.toString());
            System.out.println("    B winning hands:\t" + BWIN.toString());
            System.out.println("    AB both win:\t" + ABWIN.toString());
            System.out.println("    AB do not win:\t" + ABNOWIN.toString());
            System.out.println("    Total hands:\t" + tot.toString());

            BigDecimal topA = new BigDecimal(AWIN);
            BigDecimal topB = new BigDecimal(BWIN);
            BigDecimal topAB = new BigDecimal(ABWIN);
            BigDecimal topNAB = new BigDecimal(ABNOWIN);
            BigDecimal bot = new BigDecimal(tot);
            System.out.println("    Probability A wins: " + topA.divide(bot,8, BigDecimal.ROUND_HALF_UP).toString());
            System.out.println("    Probability B wins: " + topB.divide(bot,8, BigDecimal.ROUND_HALF_UP).toString());
            System.out.println("    Probability both win: " + topAB.divide(bot,8, BigDecimal.ROUND_HALF_UP).toString());
            System.out.println("    Probability neither wins: " + topNAB.divide(bot,8, BigDecimal.ROUND_HALF_UP).toString());
            System.out.println();

        }

    }

    static BigInteger choose(final int N, final int K) {
        BigInteger ret = BigInteger.ONE;
        for (int k = 0; k < K; k++) {
            ret = ret.multiply(BigInteger.valueOf(N-k))
                     .divide(BigInteger.valueOf(k+1));
        }
        return ret;
    }

}
$\endgroup$
  • $\begingroup$ I have a problem with this answer. If you get $12$ of each suit then that would be $24$ of each color ($red$ and black) and B would have won long before that because B only needs $18$ or more of each color to win so $42$ is the max for anyone to win (or tie) so analyzing anything beyond that is not of much value. Even my simulation stopped at $42$ cards for a decision. It never went any higher. Even with 1 billion decisions. $\endgroup$ – David Apr 15 '15 at 22:00
  • 1
    $\begingroup$ Well, sure. Each of these results are independent results. $\endgroup$ – Jonny Apr 15 '15 at 22:06
  • $\begingroup$ Not quite correct. B has an independent chance of winning from 36 to 69 cards. B could have 52 red and 17 black. The next draw is guaranteed black. The problem is that at 42, if B hasn't won, A has (this is a dependent result). I suppose I could add some more information about this interdependence... $\endgroup$ – Jonny Apr 15 '15 at 22:13
  • $\begingroup$ Edited to account for a shared hand. $\endgroup$ – Jonny Apr 15 '15 at 22:37
  • $\begingroup$ A hand of $42$ does not guarantee that A or B will win. They could tie on that card. For example, B has $24$ black cards and $17$ red cards and A needs hearts (a red card). So if hearts comes up on the $42$nd card, they will tie cuz they both need that card to "win". $\endgroup$ – David Apr 16 '15 at 2:07

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.