All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Numbered Cards (Posted on 2007-07-23)
Consider a deck of 10 cards numbered in order from 1 to 10. Pick up the first five cards (1 to 5). Randomly discard one and take the 6. Randomly discard one again and take the 7. Continue until the 10 has just been taken.

a) What is the expected average of the five cards in the final hand?
b) What is the expected value of the smallest card in the final hand?

Recompute parts a) and b) where you still hold 5 cards, but go all the way through a 100 card deck.

 See The Solution Submitted by Jer Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer-assisted solution | Comment 4 of 13 |

Part a:

The probability that any given card will be one of the five represented in the final deck is (4/5)^x where x is the number of times that card is to be subject to the random discard procedure.  For the first five cards, x = n - 5 where n is the total number of cards. For the remaining cards, x = n - i where i is the number of the card in question.  The following UBASIC program multiplies each such probability by the value of each card (the first five cards total 15, and that's multiplied by the probability of any given one of the first five cards).

`    5   point 5   10   for N=10 to 100 step 90   20     T=(4//5)^(N-5)*15   30     for I=6 to N   40       T=T+I*(4//5)^(N-I)   50     next   60     print T,T//5   61     print T/1,T/5   70   next`

The result, showing the total of the cards and the average card (by dividing by 5) is:

`                  For n = 10:                  total          averagerational          20798/625      20798/3125decimal           33.2768         6.65536`
`                  For n = 100480.000000006216540455122332    96.000000001243308091024466`

(The rational numbers for n=100 come out rather long).

For other values of n, we get:

`  n       total                              average 10      33.2768                         6.65536 20      80.35184372088832               16.070368744177664 30      130.037778931862957161709567    26.007555786372591432341913 40      180.004056481920730334084788    36.000811296384146066816957 50      230.000435561429658801233232    46.000087112285931760246645 60      280.000046768052394588893381    56.000009353610478917778676 70      330.00000502168138830934461     66.000001004336277661868921 80      380.000000539198933343012795    76.000000107839786668602558 90      430.000000057896044618658097    86.000000011579208923731619 100     480.000000006216540455122332    96.000000001243308091024466 110     530.000000000667495948725283    106.000000000133499189745056 120     580.000000000071671831749689    116.000000000014334366349937 130     630.000000000007695704335232    126.000000000001539140867046 140     680.000000000000826319960987    136.000000000000165263992197 150     730.000000000000088725430211    146.000000000000017745086041 160     780.000000000000009526820527    156.000000000000001905364104 170     830.000000000000001022934564    166.000000000000000204586912 180     880.000000000000000109836762    176.000000000000000021967351 190     930.000000000000000011793631    186.000000000000000002358726 200     980.000000000000000001266331    196.000000000000000000253266 The average apparently approaches n-4.`

Part b:

The probability that any given card will wind up as the lowest card is equal to the probability that that card will survive until the end (as in part 1) multiplied by the probability that, given that that card will survive, the other four cards held at that time, all being lower, will eventually all be eliminated.  As before, the respective probability is multiplied by the card's value for adding into the ultimate expected value.

The tricky part is calculating the probability the the four other cards already in hand when the card in question is drawn will all be discarded eventually. The general situation is that there are four such other cards, but in the case of the first five cards, only i-1 of them is actually lower than card i.

To take the most common, general, case first, there are 4 cards that must be gotten rid of and 1 card kept.  As before, the probability that the one card will be kept is (4/5)^(n-i). Calculating the probability that one card or group of cards will be kept is easy: given that a specific different one is going to be kept (it's a conditional probability) there are 4-j choices at each randomization, where j is the number of additional cards to protect, out of the 4 non-guaranteed-protected cards, that will be "safe" for those cards, versus j that will be one of the additional cards to protect.

But getting back to our problem: We don't want to protect those cards but get rid of them.  Here we must use the process of inclusion/exclusion. In the case of 4 cards to be gotten rid of, the probability that all 4 will be removed eventually is the sum of the probabilities that each one will be removed, minus the sum of the probabilities that each possible pair of them will have at least one member of the pair removed, plus the sum of the probabilities that each possible triplet will have at least one member removed, minus the probability that at least one of the 4 will be removed.

That calculation is simplified by the fact that each of the four individual cards has the same probability of ultimately being removed. The six pairs also have equal probability for the lack of total safety of their members, as do the four triplets.  Of course the group of four is just one group of four.

As mentioned, the probability of all of any one of these groups surviving is ((4-j)/4)^x, where x is the number of randomized tosses to which they are subject. The probability of some loss, of at least one card from such a group is therefore 1 - ((4-j)/4)^x.

For the first five (actually first four, as the fifth fits the above any way), the number in their  initial group that are lower in value is i-1. So the inclusion/exclusion process uses a lower order set of binomial coefficients

For card 1 there are no cards to get rid of, so that isn't a factor there. For card 2, there is just one card to get rid of, so the complement of its survival probability is its elimination probability. For card 3 there are 2 cards to get rid of, so twice the elimination probability of one of them is used and one times the probability of either one being eliminated is subtracted.  For card 4, there are 3 cards below that in value that must be eliminated, so from three times the individual probability of elimination, is subtracted three times the probability of any of the three pairs being subject to at least partial loss, and added is the probability that at least one of the three will be lost.  In the case of card 5, there are four below it, and the math is as described, using the binomial coefficients 4, -6, 4, -1 for singles, pairs, triplets, and the overall four, probabilities of losing at least one member from such a group.

The program to do this is:

DECLARE FUNCTION pr# (x#)
DECLARE FUNCTION pAnyOfG# (howMany#, tries#, numBelow#)
DECLARE FUNCTION pAllOfG# (tries#, numBelow#)
DEFDBL A-Z
DIM SHARED n

n = 10
tries = n - 5

CLS
FOR i = 1 TO n
PRINT USING "### #.####### ###.#######"; i; pr(i); i * pr(i)
t = t + pr(i)
tt = tt + i * pr(i)
NEXT
PRINT t, tt

FUNCTION pAllOfG (tries, numBelow)
SELECT CASE numBelow
CASE 1
t = pAnyOfG(1, tries, numBelow)
CASE 2
t = 2 * pAnyOfG(1, tries, numBelow) - pAnyOfG(2, tries, numBelow)
CASE 3
t = 3 * pAnyOfG(1, tries, numBelow) - 3 * pAnyOfG(2, tries, numBelow) + pAnyOfG(3, tries, numBelow)
CASE 4
t = 4 * pAnyOfG(1, tries, numBelow) - 6 * pAnyOfG(2, tries, numBelow) + 4 * pAnyOfG(3, tries, numBelow) - pAnyOfG(4, tries, numBelow)
END SELECT
pAllOfG = t
END FUNCTION

FUNCTION pAnyOfG (howMany, tries, numBelow)
p = 1 - ((4 - howMany) / 4) ^ tries
pAnyOfG = p
END FUNCTION

FUNCTION pr (x)
IF x < 6 THEN
IF x = 1 THEN
p = (4 / 5) ^ (n - 5)
ELSE
p = (4 / 5) ^ (n - 5) * pAllOfG(n - 5, x - 1)
END IF
ELSE
p = (4 / 5) ^ (n - x) * pAllOfG(n - x, 4)
END IF
pr = p
END FUNCTION

For n=10 this results in

`card  prob.      contribution to expected value   1 0.3276800   0.3276800   2 0.2499200   0.4998400   3 0.1824000   0.5472000   4 0.1248000   0.4992000   5 0.0768000   0.3840000   6 0.0384000   0.2304000   7 0.0000000   0.0000000   8 0.0000000   0.0000000   9 0.0000000   0.0000000  10 0.0000000   0.0000000total     1      2.48832`

So in the 10-card case, the 1 card is almost 1/3 probable of being the lowest card remaining, with decreasing probabilities from then on.  The expected value of the lowest card is 2.48832.

For 100 cards, the same chart is:

`   1 0.0000000   0.0000000   2 0.0000000   0.0000000   3 0.0000000   0.0000000   4 0.0000000   0.0000000   5 0.0000000   0.0000000   6 0.0000000   0.0000000   7 0.0000000   0.0000000   8 0.0000000   0.0000000   9 0.0000000   0.0000000  10 0.0000000   0.0000000  11 0.0000000   0.0000000  12 0.0000000   0.0000000  13 0.0000000   0.0000000  14 0.0000000   0.0000001  15 0.0000000   0.0000001  16 0.0000000   0.0000001  17 0.0000000   0.0000002  18 0.0000000   0.0000002  19 0.0000000   0.0000003  20 0.0000000   0.0000004  21 0.0000000   0.0000005  22 0.0000000   0.0000006  23 0.0000000   0.0000008  24 0.0000000   0.0000010  25 0.0000001   0.0000013  26 0.0000001   0.0000018  27 0.0000001   0.0000023  28 0.0000001   0.0000029  29 0.0000001   0.0000038  30 0.0000002   0.0000049  31 0.0000002   0.0000064  32 0.0000003   0.0000082  33 0.0000003   0.0000106  34 0.0000004   0.0000137  35 0.0000005   0.0000176  36 0.0000006   0.0000226  37 0.0000008   0.0000290  38 0.0000010   0.0000373  39 0.0000012   0.0000478  40 0.0000015   0.0000613  41 0.0000019   0.0000785  42 0.0000024   0.0001006  43 0.0000030   0.0001287  44 0.0000037   0.0001646  45 0.0000047   0.0002105  46 0.0000058   0.0002689  47 0.0000073   0.0003435  48 0.0000091   0.0004384  49 0.0000114   0.0005595  50 0.0000143   0.0007136  51 0.0000178   0.0009099  52 0.0000223   0.0011596  53 0.0000279   0.0014774  54 0.0000348   0.0018816  55 0.0000436   0.0023956  56 0.0000544   0.0030489  57 0.0000681   0.0038792  58 0.0000851   0.0049340  59 0.0001063   0.0062738  60 0.0001329   0.0079750  61 0.0001661   0.0101348  62 0.0002077   0.0128760  63 0.0002596   0.0163542  64 0.0003245   0.0207665  65 0.0004056   0.0263627  66 0.0005069   0.0334584  67 0.0006336   0.0424535  68 0.0007920   0.0538535  69 0.0009898   0.0682977  70 0.0012371   0.0865939  71 0.0015460   0.1097625  72 0.0019318   0.1390914  73 0.0024138   0.1762043  74 0.0030155   0.2231464  75 0.0037665   0.2824891  76 0.0047034   0.3574595  77 0.0058714   0.4520957  78 0.0073261   0.5714326  79 0.0091357   0.7217164  80 0.0113830   0.9106428  81 0.0141679   1.1476031  82 0.0176086   1.4439028  83 0.0218420   1.8128829  84 0.0270216   2.2698170  85 0.0333101   2.8313563  86 0.0408620   3.5141323  87 0.0497916   4.3318662  88 0.0601130   5.2899435  89 0.0716390   6.3758746  90 0.0838164   7.5434803  91 0.0954778   8.6884762  92 0.1045094   9.6148685  93 0.1075200   9.9993600  94 0.0998400   9.3849600  95 0.0768000   7.2960000  96 0.0384000   3.6864000  97 0.0000000   0.0000000  98 0.0000000   0.0000000  99 0.0000000   0.0000000 100 0.0000000   0.0000000 .9999999999999999                 89.58333333954988`

So the expected value of the lowest card is about 89.58333.

The expected values for other numbers of cards is as follows:

`10            2.4883215            5.62701680639999920            9.93282791886028725            14.698442694197230            19.6210980502399235            24.5957116283585140            29.5873897293005445            34.5846625546453750            39.5837688942432655            44.5834760580621860            49.5833801013825865            54.5833486582884970            59.583338355014775            64.5833349788378880            69.5833338725322685            74.5833335100180490            79.5833333912293995            84.58333335230472100           89.58333333954988105           94.58333333537036110           99.58333333400083115           104.583333333552120           109.583333333405125           114.5833333333568130           119.583333333341135           124.5833333333359140           129.5833333333341145           134.5833333333336150           139.5833333333334155           144.5833333333333160           149.5833333333333165           154.5833333333333170           159.5833333333333175           164.5833333333333180           169.5833333333333185           174.5833333333334190           179.5833333333333195           184.5833333333333200           189.5833333333333205           194.5833333333333210           199.5833333333333`

so it looks as if this approaches n - 10.4166666..., or n - 125/12.

To get rational numbers, we use UBASIC, such as this for n=10:

000100   point 6
000600
000700   n = 10
000800   tries = n - 5
000900
001000   CLS
001100   FOR i = 1 TO n
001200     PRINT  i,
001201     print  fnpr(i),
001202     print  i * fnpr(i)
001300     t = t + fnpr(i)
001400     tt = tt + i * fnpr(i)
001500   NEXT
001600   PRINT t, tt
001610   ttWhole=int(tt):ttFrac=tt-ttWhole
001620   print:print ttWhole;"+";ttFrac
001699   end
001700
001800   fnpAllOfG (tries, numBelow)
001801     local t
001900    if numBelow = 1 then
002100      :t = fnpAnyOfG(1, tries, numBelow)
002200    if numBelow = 2 then
002300      :t = 2 * fnpAnyOfG(1, tries, numBelow) - fnpAnyOfG(2, tries, numBelow)
002400    if numBelow = 3 then
002500      :t = 3 * fnpAnyOfG(1, tries, numBelow) - 3 * fnpAnyOfG(2, tries, numBelow) + fnpAnyOfG(3, tries, numBelow)
002600    if numBelow = 4 then
002700      :t = 4 * fnpAnyOfG(1, tries, numBelow) - 6 * fnpAnyOfG(2, tries, numBelow) + 4 * fnpAnyOfG(3, tries, numBelow) - fnpAnyOfG(4, tries, numBelow)
002900    pAllOfG = t
003000   return(pAllOfG)
003100
003200   fnpAnyOfG (howMany, tries, numBelow)
003201     local p
003300    p = 1 - ((4 - howMany) // 4) ^ tries
003400    pAnyOfG = p
003500   return(pAnyOfG)
003600
003700   fnpr (x)
003701     local p,pr
003800    IF x < 6 THEN
003900     :IF x = 1 THEN
004000       :p = (4 // 5) ^ (n - 5)
004100      :ELSE
004200       :p = (4 // 5) ^ (n - 5) * fnpAllOfG(n - 5, x - 1)
004300      :END IF
004400    :ELSE
004500       :p = (4 // 5) ^ (n - x) * fnpAllOfG(n - x, 4)
004600    :END IF
004700    pr = p
004800   return(pr)
004900

which gives:

`n       prob.           contribution1       1024/3125      1024/31252       781/3125       1562/31253       114/625        342/6254       78/625         312/6255       48/625         48/1256       24/625         144/6257       0               08       0               09       0               010      0               0total   1               7776/3125`

so the expected value of the lowest card is
2 + 1526/3125.  (I've replaced the double slashes that UBASIC uses with single slashes here.)

For 100 cards, the exact rational expected value is

89 + 1472540372105309708557990755715447949544383473283720944341076550891 / 2524354896707237777317531408904915934954260592348873615264892578125

 Posted by Charlie on 2007-07-23 23:46:20

 Search: Search body:
Forums (0)