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.)
re: my solution | Comment 6 of 13 |
(In reply to my solution by Ady TZIDON)

If p=(s-1)*(s-2)*(s-3)*...(s-k )...*(s-N+1)/(S^(N-1)) and the expected number of different combinations is N*p, then, when N=s, p=(s-1)!/(s^(s-1)) and the expected number of different combinations would be (s-1)!/(s^(s-2)).

In the simple case that I gave originally, for s=10, that would be 9!/(10^8) = 0.0036288. Clearly that expected value is larger.

In the case of s=C(49,6)=13,983,816, (s-1)! is 5.09456697 x 10^93,850,017, which is much less than 13,983,816^13,983,814, so the expected number of different values would be only an infinitesimal fraction.

Here's an evaluation of your formula for various N, showing N, p and N*p:

 2000    0.8667906644994577999   1733.5813289989155999357
 3000    0.7249038095932000619   2174.7114287796001859441
 4000    0.5643947166555643515   2257.5788666222574062672
 5000    0.4090907651277387745   2045.4538256386938725305
 6000    0.2760503920116564839   1656.302352069938903711
 7000    0.1734150535030699466   1213.9053745214896268831
 8000    0.1014174603352282436   811.3396826818259494062
 9000    0.0552158744998651441   496.9428704987862977751
 10000   0.0279858332744194512   279.858332744194512995
 11000   0.0132048468890099776   145.2533157791097544468
 12000   0.0058002553429323945   69.603064115188734498
 13000   0.0023717955320933506   30.8333419172135586344
 14000   0.0009028623571569044   12.6400730001966617394
 15000   0.0003199468119638217   4.7992021794573269536
 16000   0.0001055464773157981   1.688743637052770273
 17000   0.0000324128476834766   0.5510184106191037302
 18000   0.0000092660768321063   0.1667893829779141167
 19000   0.0000024659123875676   0.0468523353637848158
 20000   0.0000006108860356235   0.0122177207124703028
 21000   0.0000001408774025805   0.0029584254541911454
 22000   0.0000000302425793817   0.0006653367463985149

Notice how it goes down after a while.

The program uses logarithms to avoid overflow:

    5   S=combi(49,6)
   10   for N=2000 to 22000 step 1000
   20     LNum=0
   30     for I=S-N+1 to S-1
   40       LNum=LNum+log(I)
   50     next
   55     Lp=LNum-(N-1)*log(S):P=exp(Lp):E=N*P
   60     print N,P,E
   70   next

The results of my formula (after the typo was corrected) are:

2000    1999.8570558440459625842
3000    2999.6783296844847674345
4000    3999.4281076214049976602
5000    4999.1063947673916414075
6000    5998.7131962340449614474
7000    6998.2485171335580267427
8000    7997.7123625785567609058
9000    8997.1047376785105082852
10000   9996.4256475453432250585
11000   10995.6750972870725626615
12000   11994.8530920177215569979
13000   12993.9596368426030864938
14000   13992.9947368750768808918
15000   14991.9583972229180110886
16000   15990.8506229925446130908
17000   16989.6714192930303217428
18000   17988.4207912338353846232
19000   18987.0987439216326473044
20000   19985.705282462452874995
21000   20984.2404119610722366784
22000   21982.7041375289795596902

which seems reasonable.

That segment of the program is:

  100   for N=2000 to 22000 step 1000
  110    print N,S*(1-((S-1)/S)^N)
  120   next


  Posted by Charlie on 2005-01-15 15:45:14
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