Software Programming

Kunuk Nykjaer

Lotto probability Monte Carlo method with Java

leave a comment »


Monte Carlo is a method of approximating the probability value by trying a lot of times. You can read more about Monte Carlo at wiki here link.

The program example is:
Simple Lotto simulation with n possible numbers and m winner numbers where you have to pick m numbers.
The data structure strategy is to use primitive type int and arrays for reducing memory usage. This may not have the fastest running time, but the memory usage is kept as small as possible for large calculation samples.

This example pick a random winning numbers (ordering not important). Then it tries to select a lot of random coupons and compare the probability of how many correct numbers you select from your winning numbers.

Lotto.java

import java.text.*;
import java.util.*;


/**
 * 
 * @author Kunuk Nykjaer
 * Lotto simulation Monte Carlo
 * Simple lotto with possible range of n numbers and m range of winner numbers 
 *
 */
public class Lotto {

	private final NumberFormat nf = new DecimalFormat("#.#####");
	
	
	public static void main(String[] args) {
		long begin = System.currentTimeMillis();
		
		int coupons = 5000000;
		int numberRange = 36; // 1..numberRange
		int pickNumbers = 6;
		new Lotto().playLotto(coupons, numberRange, pickNumbers);
	
		long end = System.currentTimeMillis();
		System.out.println("Time: " + (end - begin) / 1000.0 + " sec.");
	}
	
	
	/**
	 * 
	 * Lotto simulation (combination of numbers not same) Check to see how often I win
	 * Pick random winner numbers, play with n coupons and use random numbers for each coupon
	 * First index is the winner numbers
	 */
	private int[][] getResult(int numbersOfCoupons, int numbersRange, int numbersOfuse) {
		Random rand = new Random();
		int[][] lottos = new int[numbersOfCoupons+1][numbersOfuse];

		// O(numbersOfCoupons * k)
		for (int coupon = 0; coupon < numbersOfCoupons+1; coupon++) {
			int size = numbersRange;
			int[] possibleNumbers = new int[size];
			int[] lottoNumbers = new int[numbersOfuse];

			// O(numbersRange * k)
			// store possible numbers for random selection
			for (int i = 0; i < possibleNumbers.length; i++)
				possibleNumbers[i] = i + 1;

			// O(numbersOfuse * k)
			// pick random numbersOfuse numbers not same
			for (int i = 0; i < lottoNumbers.length; i++) {
				int last = size - 1;
				int next = rand.nextInt(size);
				int temp = possibleNumbers[last];
				int value = possibleNumbers[next];
				possibleNumbers[next] = temp;
				lottoNumbers[i] = value;
				size--;
			}
			lottos[coupon] = lottoNumbers;
		}
		return lottos;
	}
	
	
	
	/**
	*  	buy n coupons with random numbers
	*	lotto is possible numbers 1..n
	*	I pick x random numbers where there are x winner numbers 	
	*/	
	public void playLotto(int coupons, int n, int pickSize)
	{						
		HashSet<Integer> winnerNumbersLookup = new HashSet<Integer>();
				
		int[][] lotto = getResult(coupons, n, pickSize);
		int[] winnerNumbers = lotto[0];
		for (int i = 0; i < winnerNumbers.length; i++) {
			winnerNumbersLookup.add( winnerNumbers[i] );
		}
			
		int[] countCorrect = new int[pickSize+1];
		
		for (int i = 1; i < lotto.length; i++) {
			int numbersCorrect = 0;
			int[] coupon = lotto[i];
			for (int j = 0; j < coupon.length; j++) {
				int number = coupon[j];
				if(  winnerNumbersLookup.contains(number))
					numbersCorrect++;
			}
			countCorrect[numbersCorrect]++;			
		}
		
		// Print result
		System.out.print("Winner numbers are: ");
		Arrays.sort(winnerNumbers);
		for (int i = 0; i < winnerNumbers.length; i++) {
			System.out.print(winnerNumbers[i]+ " ");
		}
		System.out.println("\nNumber range is 1.."+n);
		System.out.println("PickSize is "+pickSize);
		System.out.println("Correct hit count with coupons "+coupons);
		for (int i = 0; i < countCorrect.length; i++) {
			System.out.println(i+" hit: " +countCorrect[i] + " ~ "+nf.format(100*(countCorrect[i]/(double)coupons))+  "%");
		}							
	}
}

Result:
Winner numbers are: 2 7 11 12 14 33
Number range is 1..36
PickSize is 6
Correct hit count with coupons 5000000
0 hit: 1522834 ~ 30,45668%
1 hit: 2195431 ~ 43,90862%
2 hit: 1056309 ~ 21,12618%
3 hit: 208328 ~ 4,16656%
4 hit: 16653 ~ 0,33306%
5 hit: 441 ~ 0,00882%
6 hit: 4 ~ 0,00008%
Time: 21.63 sec.

The result of the Monte Carlo method (experience based) can be compared with the Math using hyper-geometric distribution (theory based).
I made a probability tool in Javascript a long time ago which can calculate hyper-geometric distribution. By comparing the probability values it show the values are more or less equal.

Heres for 0 hit link for mathematical calculating 0 hit
The value is 0.3048451785406245 which is pretty close to the Monte Carlo method.

Advertisements

Written by kunuk Nykjaer

October 2, 2010 at 10:49 am

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: