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

Home > Probability
Numbered Cards (Posted on 2007-07-23) Difficulty: 4 of 5
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.)
Solution 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          average
rational          20798/625      20798/3125
decimal           33.2768         6.65536
                  For n = 100
480.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.0000000
total     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.48832
15            5.627016806399999
20            9.932827918860287
25            14.6984426941972
30            19.62109805023992
35            24.59571162835851
40            29.58738972930054
45            34.58466255464537
50            39.58376889424326
55            44.58347605806218
60            49.58338010138258
65            54.58334865828849
70            59.5833383550147
75            64.58333497883788
80            69.58333387253226
85            74.58333351001804
90            79.58333339122939
95            84.58333335230472
100           89.58333333954988
105           94.58333333537036
110           99.58333333400083
115           104.583333333552
120           109.583333333405
125           114.5833333333568
130           119.583333333341
135           124.5833333333359
140           129.5833333333341
145           134.5833333333336
150           139.5833333333334
155           144.5833333333333
160           149.5833333333333
165           154.5833333333333
170           159.5833333333333
175           164.5833333333333
180           169.5833333333333
185           174.5833333333334
190           179.5833333333333
195           184.5833333333333
200           189.5833333333333
205           194.5833333333333
210           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.           contribution
1       1024/3125      1024/3125
2       781/3125       1562/3125
3       114/625        342/625
4       78/625         312/625
5       48/625         48/125
6       24/625         144/625
7       0               0
8       0               0
9       0               0
10      0               0
total   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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information