You have a standard pack of 52 playing cards. You then shuffle them and begin to draw out cards until you have three of a kind. What is the most likely number of cards drawn when this happens?

You then shuffle another pack of 52 playing cards into the pile. What happens to the expected number of cards now? (i.e. does it double / halve / stay the same?)

At any given number, n, of cards having been drawn, the situation that the first triplet has been completed just at that step entails that, among the first n-1 cards drawn, there were exactly 2 of that denomination. Of the remaining 12 denominations there could have been zero through [(n-3)/2] pairs, where the square brackets indicate the floor function (greatest integer not exceeding the contents). Call the number of pairs p (excluding the previous pair of the denomination whose triplet was just completed).

The number of singlets (one of a kind) drawn then must be n-3-2p. The total of pairs and singlets must be less than or equal to 12, so don't count terms which use larger values for these.

There are 13 choices for which of the denominations is represented by the newly formed triplet. But there are also 4 possible choices of which card is the triplet completion card, and C(3,2) ways of choosing the first 2 of the triplet.

For each of these, there are C(12,p) ways of choosing which denominations are present in pairs, and, since each pair can be any of C(4,2)=6 choices from the original deck, the C(12,p) is to be multiplied by 6^p.

For each of the choices so far, the s singlets can be each of the 4 from the original deck, so we multiply the product so far by 4^s. And there are C(12-p,s) of them, that factors in also.

The total of the [(n-3)/2] terms thus calculated must then be divided by the total combinations of 52 cards taken n at a time.

For two decks the 52 becomes 104. Also, in the above, there are 8 ways of choosing the triplet-completion card for a given denomination and C(7,2) ways of choosing the first 2 of the triplet, and C(4,2)=6 becomes C(8,2)=28, SO that 6^p becomes 28^p.

A program that calculates the above is:
DECLARE FUNCTION combi# (x#, y#)
DECLARE FUNCTION lxf# (x#)
DEFDBL A-Z
DIM SHARED twopi
DIM cum(28)
twopi = ATN(1) * 8
decks = 1
pairBase = combi(4 * decks, 2)
totCards = 52 * decks
PRINT
FOR n = 3 TO 28
 tot = 0
 FOR p = 0 TO INT((n - 3) / 2)
  s = n - 3 - 2 * p
  IF p + s <= 12 AND s >= 0 THEN
    term = 13 * 4 * decks * combi(4 * decks - 1, 2) * combi(12, p) * pairBase ^ p * (4 * decks) ^ s * combi(12 - p, s)
    tot = tot + term
  END IF
 NEXT
 tot = tot / (combi(totCards - 1, n - 1) * totCards)
 cumTot = cumTot + tot
 cum(n) = cumTot
 PRINT USING "## ####### #.####### #.#######"; n; tot * 1000000; tot; cumTot
NEXT

tot = 0
FOR i = 1 TO 27
 IF cum(i) > .5 AND med = 0 THEN
   med = i - 1 + (.5 - cum(i - 1)) / (cum(i) - cum(i - 1))
   PRINT "Median is"; med
 END IF
 tot = tot + i * (cum(i) - cum(i - 1))
NEXT
PRINT "Mean is"; tot

 FUNCTION combi (x, y)
  lg = lxf(x) - lxf(y) - lxf(x - y)
  combi = INT(EXP(lg) + .5)
 END FUNCTION

FUNCTION lxf (x)
  IF x < 171 THEN
    fact = 1
    IF x > 1 THEN
      FOR i = 2 TO x
       fact = fact * i
      NEXT
    END IF
    lo = LOG(fact)
  ELSE
    lo = LOG(x) * (x + .5)
    lo = lo + (-x + 1 / (12 * x) - 1 / (360 * x * x * x) + 1 / (1260 * x * x * x * x * x))
    lo = lo + LOG(twopi) / 2
  END IF
  lxf = lo
END FUNCTION

It produces

 3    2353 0.0023529 0.0023529


 4    6915 0.0069148 0.0092677


 5   13541 0.0135414 0.0228091


 6   22028 0.0220275 0.0448367


 7   32059 0.0320592 0.0768958


 8   43179 0.0431794 0.1200752


 9   54772 0.0547716 0.1748468


10   66065 0.0660651 0.2409119


11   76172 0.0761724 0.3170843


12   84160 0.0841603 0.4012447


13   89155 0.0891549 0.4903995


14   90472 0.0904717 0.5808713


15   87752 0.0877525 0.6686237


16   81077 0.0810771 0.7497008


17   71020 0.0710195 0.8207203


18   58613 0.0586129 0.8793333


19   45210 0.0452103 0.9245436


20   32252 0.0322518 0.9567953


21   20987 0.0209866 0.9777819


22   12227 0.0122267 0.9900086


23    6213 0.0062133 0.9962220


24    2650 0.0026498 0.9988717


25     891 0.0008912 0.9997630


26     211 0.0002107 0.9999737


27      26 0.0000263 1.0000000


28       0 0.0000000 1.0000000


Median is 13.10611589574091


Mean is 13.55606605519886

-------
Where the second column shows the probability of that run length multiplied by 1,000,000 to facilitate comparison to the previous simulation results; the third column shows the probability as calculated; the fourth shows the cumulative probability, which does reach 1 at the number of draws equal to 27.

If the decks variable is changed to 2 and the program run, it produces:

 3    3998 0.0039977 0.0039977


 4   11399 0.0113994 0.0153971


 5   21659 0.0216589 0.0370561


 6   34114 0.0341138 0.0711699


 7   47909 0.0479086 0.1190785


 8   61979 0.0619789 0.1810574


 9   75096 0.0750961 0.2561534


10   85972 0.0859715 0.3421249


11   93411 0.0934109 0.4355359


12   96498 0.0964977 0.5320336


13   94770 0.0947703 0.6268038


14   88347 0.0883470 0.7151509


15   77958 0.0779581 0.7931090


16   64854 0.0648540 0.8579630


17   50596 0.0505958 0.9085587


18   36765 0.0367655 0.9453242


19   24670 0.0246696 0.9699939


20   15118 0.0151177 0.9851115


21    8340 0.0083402 0.9934517


22    4064 0.0040637 0.9975154


23    1703 0.0017029 0.9992182


24     590 0.0005902 0.9998085


25     159 0.0001590 0.9999675


26      30 0.0000297 0.9999971


27       3 0.0000029 1.0000000


28       0 0.0000000 1.0000000


Median is 11.66803791319374


Mean is 12.21442208680124

--------
These numbers, including the medians and the means, compare well with the simulation results.

Posted by Charlie on 2003-11-21 15:58:44