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

Home > Probability
Playing Lotto (Posted on 2005-01-14) Difficulty: 4 of 5
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.)

See The Solution Submitted by Federico Kereki    
Rating: 3.7500 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts thoughts | Comment 1 of 13

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

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 (6)
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