Notch ( the creator of Minecraft ) posted an interesting lottery problem.
Lottery Question
Lottery Answer
I quickly wrote this java to help people understand the results.
package com.jsa;
import java.util.Iterator;
import java.util.Random;
import java.util.Vector;
public class test {
final static int LOTTOSIZE = 1000000;
final static int WINSTOP = 3;
public static void main( String args[] ){
Vector<Vector> wins = new Vector<Vector<Integer>>(WINSTOP);
Vector<Integer> oneWin = new Vector<Integer>(LOTTOSIZE);
wins.add(oneWin);
Random random = new Random( System.currentTimeMillis());
boolean foundXWins = false;
int draws = 0;
while ( ! foundXWins ){
Integer winner = random.nextInt(LOTTOSIZE);
draws++;
boolean notFound = true;
for (Iterator iterator = wins.iterator(); iterator.hasNext() && notFound ;) {
Vector<Integer> vector = (Vector<Integer>) iterator.next();
if ( vector.contains(winner) ){
notFound = false;
vector.remove(winner);
if ( iterator.hasNext() ){
vector = (Vector<Integer>) iterator.next();
} else {
vector = new Vector<Integer>(LOTTOSIZE);
wins.add(vector);
System.out.println( "Someone has just won " + wins.size() + " times, after only " + draws +" draws. " );
}
vector.add(winner);
}
}
if ( notFound ){
oneWin.add(winner);
}
if ( wins.size() == WINSTOP ){
foundXWins = true;
int nonWinners = LOTTOSIZE;
for (int i = 0; i &tl; wins.size() ; i++ ){
nonWinners -= wins.get(i).size();
}
System.out.println( "Win Limit Reached: " + wins.size() + " wins.");
System.out.println( "There are " + nonWinners + " who have not yet won once." );
}
if( draws %10000 == 0 || foundXWins ){
StringBuilder sb = new StringBuilder();
sb.append( draws );
sb.append( "," );
for (int i = 0; i &tl; wins.size() ; i++ ){
sb.append( wins.get(i).size() );
sb.append( "," );
}
System.out.println( sb );
}
}
}
}
Output was:
Someone has just won 2 times, after only 177 draws.
10000,9902,49,
Someone has just won 3 times, after only 18936 draws.
Win Limit Reached: 3 wins.
There are 981230 who have not yet won once.
18936,18605,164,1,
So in this instance it only took 18,936 draws before one of the lottery members won 3 times, and the vast majority of lottery players 981,230 had not won at all!
After running the program several times it seems like a 3 time winner will show up somewhere between 10,000 and 25,000 draws. This is quite a small number compared to the 1 mil players, Showing that It is much more likely that somebody else will win 3 times before you win once.