A Lotto bet is picking 6 numbers out of 49 -- if you pick the correct combination, you get the jackpot!
If N persons play, there will be many repeats, since it's highly probable that some combinations will be chosen by two persons or more. (This is known as the "birthday paradox".)
What's the expected number of DIFFERENT combinations that will be chosen, if N persons play? (Assume these persons pick their combinations totally randomly.)
There are C(49,6) = 13,983,816 different combinations that can be chosen. So the problem, basically, is After choosing N numbers at random between 1 and 13,983,816, how many different numbers will have been chosen.
In principle, this is no different from a case in which the numbers chosen are, say, from 1 to 10. The combinatorial analysis is complicated, but a simulation for the case of random numbers chosen from 10 follows. It represents over 40,000 trials, in which, at each number, n, of choices thus far, the number of different numbers chosen was recorded, up to n=100 (so there were over 4 million number choices made altogether).
What the table shows are 40,572 trials, and a table of, for each number, n, of tosses thus far, the average number of different numbers chosen out of 10 that far, which should approximate the expected value:
40572
1 1.00000 26 9.34827 51 9.95554 76 9.99709
2 1.89774 27 9.41433 52 9.95997 77 9.99724
3 2.70886 28 9.47466 53 9.96443 78 9.99756
4 3.43841 29 9.52901 54 9.96838 79 9.99783
5 4.09842 30 9.57646 55 9.97153 80 9.99823
6 4.68668 31 9.61932 56 9.97434 81 9.99840
7 5.22008 32 9.65792 57 9.97673 82 9.99860
8 5.69834 33 9.69260 58 9.97878 83 9.99862
9 6.13179 34 9.72286 59 9.98087 84 9.99867
10 6.52065 35 9.74990 60 9.98294 85 9.99887
11 6.86782 36 9.77640 61 9.98489 86 9.99892
12 7.17943 37 9.79915 62 9.98644 87 9.99911
13 7.46323 38 9.81926 63 9.98792 88 9.99921
14 7.71355 39 9.83718 64 9.98913 89 9.99931
15 7.93717 40 9.85399 65 9.99036 90 9.99936
16 8.14229 41 9.86934 66 9.99123 91 9.99946
17 8.32589 42 9.88297 67 9.99219 92 9.99953
18 8.49224 43 9.89572 68 9.99290 93 9.99953
19 8.64567 44 9.90577 69 9.99352 94 9.99958
20 8.77960 45 9.91553 70 9.99423 95 9.99965
21 8.89855 46 9.92418 71 9.99475 96 9.99965
22 9.01015 47 9.93202 72 9.99561 97 9.99968
23 9.11005 48 9.93937 73 9.99586 98 9.99970
24 9.19955 49 9.94545 74 9.99623 99 9.99970
25 9.27852 50 9.95090 75 9.99680 100 9.99970
Thus for example, in the 40,572 trials, after 20 choices had been made in each, the average number of different numbers chosen out of ten, was 8.77960. The purpose of the above exercise is to compare any proposed analytic solution, in a symple case of numbers from 1 to 10, to simulation results. Then the analysis can be expanded to the case of numbers from 1 to 13,983,816.
The program used was
DEFDBL A-Z
c = 10
DIM numComp(100)
getSomeMore:
DO
REDIM had(c)
diffVals = 0
FOR players = 1 TO 100
r = INT(RND(1) * c) + 1
IF had(r) = 0 THEN
diffVals = diffVals + 1
had(r) = 1
END IF
numComp(players) = numComp(players) + diffVals
NEXT players
tr = tr + 1
PRINT tr
FOR i = 1 TO 100
PRINT USING "###.###"; numComp(i) / tr;
NEXT i
PRINT
LOOP UNTIL INKEY$ = CHR$(27)
CLS : PRINT tr
FOR i = 1 TO 100
LOCATE (i - 1) MOD 25 + 2, ((i - 1) 25) * 19 + 1
PRINT USING "### ###.#####"; i; numComp(i) / tr;
NEXT i
DO
LOOP UNTIL INKEY$ > ""
GOTO getSomeMore
Edited on January 14, 2005, 7:07 pm
|
|
Posted by Charlie
on 2005-01-14 19:00:49 |
thoughts
