3
$\begingroup$

Suppose we have a standard well shuffled $52$ card deck and deal cards from it without replacement (for each hand). Which is likely to happen first on average, we deal out an entire suit (all $13$ cards of any one suit) or get $3$ quads?

None of the cards have to be in any special order, just that they show up. For example, the quads could show up with other "irrelevant" cards in between.

Note that both of these are stopping conditions for a trial, whether you first get the full suit or the triple quads.

Also note that each case could be poised, waiting for $1$ card to "win" but a single card drawn could satisfy both conditions simultaneously and thus will be considered a tie or no decision and we would then reshuffle and retry a new hand. For example, if you needed the K of hearts to complete all $13$ hearts but you also have seen $5,5,5,5,3,3,3,3,K,K,K$ so far with no other quads seen yet that hand. The K of hearts would satisfy both conditions simultaneously and thus create a "tie" (no decision) situation, prompting a reshuffle and retrial.

$\endgroup$
  • $\begingroup$ What is a "quad"? $\endgroup$ – K. Jiang Apr 11 '16 at 3:48
  • $\begingroup$ I gave examples. A quad in this context is $4$ cards all of the same rank such as K,K,K,K. There are $13$ different ranks in a standard $52$ card deck. $\endgroup$ – David Apr 11 '16 at 4:00
2
$\begingroup$

As I said in my other answer, it is feasible to explicitly calculate all the probabilities. We generate all the distributions of cards into ranks, ${13+4\choose4}=2380$ except the distributions that lack $3$ cards of any rank, ${13+3\choose3}=560$. Then for each distribution we can compute the probability of having that distribution given a hand of that many cards, $$P_{dist}=\frac{\frac{13!}{n_0!n_1!n_2!n_3!n_4!}{4\choose0}^{n_0}{4\choose1}^{n_1}{4\choose2}^{n_2}{4\choose3}^{n_3}{4\choose4}^{n_4}}{{52\choose0\cdot n_0+1\cdot n_1+2\cdot n_2+3\cdot n_3+4\cdot n_4}}$$ Where $n_i$ is the number of ranks that have $i$ cards in the distribution. Then we multiply that by the probability of ending a game requiring $n_4+1$ quads on the next card, $$P_{over}=\frac{n_3}{52-(0\cdot n_0+1\cdot n_1+2\cdot n_2+3\cdot n_3+4\cdot n_4)}$$ Now we have to find the probabilities of winning on that next card, drawing, or already having lost. $$\begin{align}P_{win}&=P(0)\\ P_{tie}&=\frac14P(1)\\ P_{lose}&=\frac34P(1)+P(2)+P(3)+P(4)\end{align}$$ Where $P(i)$ is the probability of having completed $i$ suits after the next card has been drawn. Then by inclusion-exclusion, we can find that $$\begin{align}P(0)&=1-4P(\spadesuit)+6P(\heartsuit\spadesuit)-4P(\diamondsuit\heartsuit\spadesuit)+P(\clubsuit\diamondsuit\heartsuit\spadesuit)\\ P(1)&=4P(\spadesuit)-12P(\heartsuit\spadesuit)+12P(\diamondsuit\heartsuit\spadesuit)-4P(\clubsuit\diamondsuit\heartsuit\spadesuit)\\ P(2)&=6P(\heartsuit\spadesuit)-12P(\diamondsuit\heartsuit\spadesuit)+6P(\clubsuit\diamondsuit\heartsuit\spadesuit)\\ P(3)&=4P(\diamondsuit\heartsuit\spadesuit)-4P(\clubsuit\diamondsuit\heartsuit\spadesuit)\\ P(4)&=P(\clubsuit\diamondsuit\heartsuit\spadesuit)\end{align}$$ Where, for example $P(\heartsuit\spadesuit)=P_2$ is the probability of having completed both the hearts and spades suits by the time the next card is drawn. Having picked $K$ specific suits, the probability of all of those suits being present in a rank where $N$ cards has been drawn is $$P_{NK}=\frac{{4-K\choose N-K}}{{4\choose N}}$$ Where ${N\choose k}=0$ if $k<0$. So the probability of success over all ranks is $$P_K=P_{0K}^{n_0}P_{1K}^{n_1}P_{2K}^{n_2}P_{3K}^{n_3-1}P_{4K}^{n_4+1}$$ Where conventionally $0^0=1$. Putting all that stuff together we can write a program (not posted) to calculate the probabilities of winning, losing, or drawing for games requiring all numbers of quads to win.

$$\begin{array}{r|rrr} \text{Quads}&\text{Win}&\text{Lose}&\text{Tie}\\ \hline 1&0.998563&0.001078&0.000359\\ 2&0.992344&0.005746&0.001910\\ 3&0.975825&0.018161&0.006013\\ 4&0.941256&0.044220&0.014525\\ 5&0.879013&0.091425&0.029562\\ 6&0.778897&0.168285&0.052818\\ 7&0.633332&0.282725&0.083944\\ 8&0.444088&0.438620&0.117292\\ 9&0.234020&0.629219&0.136761\\ 10&0.060783&0.826763&0.112455\\ 11&0.004689&0.972954&0.022357\\ 12&0.000048&0.999376&0.000576\\ 13&0.000000&1.000000&0.000000\\ \end{array}$$

$\endgroup$
4
$\begingroup$

While I can't tell you the exact likelihood of either option coming first, I can prove that getting three quads first is far more likely.

Consider that after 42 cards, you are guaranteed to have at least three quads since there are only 10 cards remaining. After 42 cards, the likelihood of having a full suit would be the likelihood that the remaining 10 cards contain 3 suits or fewer. This probability is $${4*{39 \choose 10}-6*{26 \choose 10}+{13 \choose 10}\over {52 \choose 10}}=.1587 $$

This means that at a point when you are certain you have three quads, there is still a more than 84% chance that you do not have a full suit. Hence, the three quads are more likely to come first.

$\endgroup$
  • $\begingroup$ Can anyone run a Monte Carlo simulation to help confirm this? I'd be interested to know things like the percentages of each, % of ties, average number of cards for a winner.... $\endgroup$ – David Apr 11 '16 at 14:28
  • $\begingroup$ @David Thanks for the suggested edit. I changed it to 84%. $\endgroup$ – browngreen Apr 11 '16 at 15:45
  • $\begingroup$ @Browngren, can you redo your calculation to see what happens when checking for $8$ quads instead of only $3$? According to the simulation by user5713492, those outcomes (one full suit vs. $8$ quads) are almost "even steven" (equiprobable). Thanks. $\endgroup$ – David Apr 12 '16 at 4:12
  • $\begingroup$ You are guaranteed at least 8 quads after 47 cards. At that point, the likelihood of having a full suit is $${4*{39 \choose 5}-6*{26 \choose 5}+{13 \choose 5}\over {52 \choose 5}}=.7348$$ Based on this alone, we see that the probability of 8 quads coming first is at least .2652, but you couldn't conclude which is more likely to come first. $\endgroup$ – browngreen Apr 12 '16 at 16:00
1
$\begingroup$

I tried a simulation. Ran a total of $1.0\times10^{10}$ times. Program was:

program shuffle
   use ISO_FORTRAN_ENV
   implicit none
   integer(INT64) deck(52)
   integer i, j
! DATA STRUCTURE:
! The deal has 4 4-bit counters for suits and 13 2-bit counters
! for ranks. Like this:
! xxxx0SSSS0HHHH0DDDD0CCCC0AA0KK0QQ0JJ0TT099088077066055044033022
! Each card has a bit set for its suit and for its rank.
! When added to the deal it updates the appropriate suit and rank
! counters. When a counter overflows, we know that all 4 of a
! rank or all 13 of a suit have been dealt (the suit counters
! were initialized to 3 so that 13 more overflowed them.)
   integer(INT64), parameter :: initial(52) = &
      [((ior(ishft(1_INT64,3*j),ishft(1_INT64,39+5*i)),j=0,12),i=0,3)]
   integer(INT64), parameter :: suits = &
      iany([(ishft(1_INT64,43+5*i),i=0,3)])
   integer(INT64), parameter :: ranks = &
      iany([(ishft(1_INT64,2+3*j),j=0,12)])
   integer(INT64), parameter :: first = &
      iany([(ishft(3_INT64,39+5*i),i=0,3)])
   integer(INT64) Nsim, k, deal
   integer(INT64) :: win = 0, tie = 0, lose = 0
   real harvest(51)
   integer quads
   logical won, lost

   Nsim = 1000000000
   call random_seed()
   do k = 1, Nsim
      deck = initial
      deal = first
      call random_number(harvest)
      do i = 1, 51
         j = harvest(i)*(53-i)
         if(j /= 0) deck([i,j+i]) = deck([j+i,i])
      end do
      do i = 1, 52
         deal = deal+deck(i)
         won = popcnt(iand(deal,ranks)) >= 3
         lost = iand(deal,suits) /= 0
         if(won .OR. lost) exit
      end do
      if(won) then
         if(lost) then
            tie = tie+1
         else
            win = win+1
         end if
      else
         lose = lose+1
      end if
   end do
   write(*,'(a,i12,1x,f12.8)') ' win = ', win, win*1.0d2/Nsim
   write(*,'(a,i12,1x,f12.8)') 'lose = ', lose, lose*1.0d2/Nsim
   write(*,'(a,i12,1x,f12.8)') ' tie = ', tie, tie*1.0d2/Nsim
end program shuffle

Results were as follows: $$\begin{array}{rrr} \text{win} & 9758240072 & 97.5824\% \\ \text{lose} & 181632175 & 1.8163\% \\ \text{tie} & 60127753 & 0.6013\% \end{array}$$ So it can be seen that a loss (all of a suit before 4 quads) was rare, and ties even less frequent.

$\endgroup$
  • $\begingroup$ Just curious. How many quads are needed to make it "neck and neck" with filling a full suit? 6? 7?...? Can you mod your program to check when the percentages approach 50% each please? $\endgroup$ – David Apr 12 '16 at 2:19
  • 1
    $\begingroup$ When I cranked it up to 8 quads, it was 44.39% win, 43.87% lose, 11.74% tie. $\endgroup$ – user5713492 Apr 12 '16 at 2:51
  • $\begingroup$ Wow that tie seems very high maybe someone else should also do a Monte Carlo simulation to check. How can it be that just as you get the $8$th quad you are also finishing the first complete suit on that same exact card about $1$ out of $9$ trials? What is the average number of cards of the win, loss, and tie "buckets"? $8$ quads is at least $32$ cards and likely more. $\endgroup$ – David Apr 12 '16 at 3:52
  • $\begingroup$ If you think about it, the 8th quad is very likely to come in the 45th-47th card range, which is also a very reasonable range to complete the first full suit. $\endgroup$ – browngreen Apr 12 '16 at 8:06
  • 1
    $\begingroup$ Another $6.0\times10^9$ simulations, tracking mean game length: $$\begin{array}{rr}\text{Quads}&\text{Length}\\3&35.11\\4&37.96\\5&40.19\\6&41.96\\7&43.33\\8&44.33\end{array}$$ Come to think of it, it may be feasible to calculate exact probabilities -- in terms of distributions there aren't really that many possibilities. $\endgroup$ – user5713492 Apr 12 '16 at 17:18

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.