Tuesday, July 22, 2008

Completely Frivolous Computation

Never satisfied with things until I've totally overdone it, I went back into the BRK Bingo card generation statistics and played around.

Using some basic discrete math, I calculated the odds of randomly generating a valid BRK Bingo card at 0.17%

Unsure of how correct my calculations were, and full of some spare time and CPU cycles, I decided to run a simulation and see how things play out in the "real world".

Wrote a little Java program that would randomly generate boards until it created a valid board, and then report some basic data about the trial.

Then wrapped that whole routine in a loop so it could be repeated many many times.

Bottom line, after running a batch of 10,000,000 simulations the program reported that it nailed a valid board on the first try 16,848 times, or 0.168% of the time.

Pretty damn close to the 0.17% my calculations predicted. The difference is most likely explainable by either too small a sample size of ten million, or the fact that the Java Random Number Generator is not perfect, it is a Pseudo Random Number Generator, and thus can tend to have non-random sequences, although the amount of error is generally accepted as statistically insignificant.

Going one bit further, I wanted to see if I was lucky or unlucky in that it took me about 30 minutes of clicking F9 to generate a solution.

On average, during the 10,000,000 simulation batch, a valid board was generated after 586 trials.

Thinking back to my 30 minutes of clicking, I'll estimate that I spent 2 seconds per click. This is a giagantique estimate, based upon the fact that the 30 minutes had some small interruptions and the fact that I was not spamming the button, but was instead trying to go slow such that I wouldn't fail to recognize a valid board, since my spreadsheet had no "back" button.

30 minutes * 60 seconds / 2 seconds per click = 900 boards.

So I estimate that it took me 900 boards to get a valid one. Somewhat more unlucky than the 586 average that I predicted, but not so far out as to have me worried about getting hit by lightning in the near future. I could to a standard deviation analysis, which will probably show me that 900 is right there in the comfort zone, but I think I'm done. And the 900 is considerably more lucky than the worst-case found during the simulation of 9,364.

That should just about satisfy my curiosity on this topic. Time for that hogie.

Maybe I'll try out a batch of 100,000,000 simulations, which will take roughly 2 days, or maybe even bite the bullet and run a 1,000,000,000 batch over 18 days, just to see if I can keep the process uninterrupted for that long.

In case you're a raw data junkie, here's the output for a variety of sample sizes, adding an order of magnitude each time.


Completed execution of [1] simulations...
Elapsed time (HH:MM:SS.mmm): 00:00:00.20
Minimum Trials until Valid Board : 846
Average Trials until Valid Board : 846
Maximum Trials until Valid Board : 846
Number of times I got it on the first try : 0 (0.000%)
Number of times I got it in less than 100 tries : 0 (0.000%)

Completed execution of [10] simulations...
Elapsed time (HH:MM:SS.mmm): 00:00:00.10
Minimum Trials until Valid Board : 24
Average Trials until Valid Board : 521
Maximum Trials until Valid Board : 1,112
Number of times I got it on the first try : 0 (0.000%)
Number of times I got it in less than 100 tries : 2 (20.000%)

Completed execution of [100] simulations...
Elapsed time (HH:MM:SS.mmm): 00:00:00.110
Minimum Trials until Valid Board : 3
Average Trials until Valid Board : 600
Maximum Trials until Valid Board : 2,382
Number of times I got it on the first try : 0 (0.000%)
Number of times I got it in less than 100 tries : 16 (16.000%)

Completed execution of [1,000] simulations...
Elapsed time (HH:MM:SS.mmm): 00:00:01.222
Minimum Trials until Valid Board : 2
Average Trials until Valid Board : 581
Maximum Trials until Valid Board : 3,690
Number of times I got it on the first try : 0 (0.000%)
Number of times I got it in less than 100 tries : 142 (14.200%)

Completed execution of [10,000] simulations...
Elapsed time (HH:MM:SS.mmm): 00:00:15.422
Minimum Trials until Valid Board : 1
Average Trials until Valid Board : 593
Maximum Trials until Valid Board : 6,530
Number of times I got it on the first try : 26 (0.260%)
Number of times I got it in less than 100 tries : 1,508 (15.080%)

Completed execution of [100,000] simulations...
Elapsed time (HH:MM:SS.mmm): 00:02:26.492
Minimum Trials until Valid Board : 1
Average Trials until Valid Board : 583
Maximum Trials until Valid Board : 6,881
Number of times I got it on the first try : 192 (0.192%)
Number of times I got it in less than 100 tries : 15,566 (15.566%)

Completed execution of [1,000,000] simulations...
Elapsed time (HH:MM:SS.mmm): 00:23:09.501
Minimum Trials until Valid Board : 1
Average Trials until Valid Board : 586
Maximum Trials until Valid Board : 8,573
Number of times I got it on the first try : 1,652 (0.165%)
Number of times I got it in less than 100 tries : 155,395 (15.540%)

Completed execution of [10,000,000] simulations...
Elapsed time (HH:MM:SS.mmm): 03:44:24.375
Minimum Trials until Valid Board : 1
Average Trials until Valid Board : 586
Maximum Trials until Valid Board : 9,364
Number of times I got it on the first try : 16,848 (0.168%)
Number of times I got it in less than 100 tries : 1,554,695 (15.547%)

2 comments:

Loronar said...

Mmm...raw data. If only I were a mathematician. =P

Morance said...

Interesting how the MAXIMUM number of tries needed goes up as you added more simulations to the cycle.