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 |
computer-assisted solution
