can this code be improved

[Patricia Shanahan]

I thought that picking 6 random numbers between 1 and 49 a million
times would be a reasonably good estimate of the real world odds. I
guess I was wrong.

Actually, the odds are that if you roll a dice, you will get a 3 or 4
more than any other number so I was trying to sort of simulate that.

There is no one set of "real world" odds.

A single dice roll, a java.util.Random nextInt(), the numbers picked by
a lottery machine, are all approximations to the uniform probability
distribution, in which on each pick every number is exactly equally likely.

In each case, there may be bias due to the specific implementation.

A physical dice may not be perfectly fair, especially if it is at all
worn, or the person throwing it is skilled. As already pointed out,
there are defects in the java.util.Random implementation that may make
it not perfectly fair.

The lottery machine is probably the closest of them all to being exactly
uniform. A state lottery can afford to spend a lot more than the cost of
a dice on buying their machine and testing it for uniformity.

Patricia

 

[Print Guy]

There is no one set of "real world" odds.

A single dice roll, a java.util.Random nextInt(), the numbers picked by
a lottery machine, are all approximations to the uniform probability
distribution, in which on each pick every number is exactly equally likely.

In each case, there may be bias due to the specific implementation.

A physical dice may not be perfectly fair, especially if it is at all
worn, or the person throwing it is skilled. As already pointed out,
there are defects in the java.util.Random implementation that may make
it not perfectly fair.

The lottery machine is probably the closest of them all to being exactly
uniform. A state lottery can afford to spend a lot more than the cost of
a dice on buying their machine and testing it for uniformity.

Patricia

So how do they do it? In the old days, there used to be 49 balls in a
tumbler, one would fall out, then another, then another, then another
until there were six. In fact, I seem to recall seeing on TV some of
the televised American lotteries where the same methods were employed.
If you wanted to simulate that, you would need an array of 49 numbers,
then pick a number at random, drop that number out of the array, shrink
it by one and then pick 1 - 48, then 1-47 etc. I guess the issue here
isn't the way that the picking is simulated, but the way that the
randomness is implemented. Is there any computer language, or program
or whatever that is capable of true random number selection based on
"statistically proven techniques" or is everything we consider to be
random just a close approximation?

 

[Luke Webber]

I thought that picking 6 random numbers between 1 and 49 a million
times would be a reasonably good estimate of the real world odds. I
guess I was wrong.

Actually, the odds are that if you roll a dice, you will get a 3 or 4
more than any other number so I was trying to sort of simulate that.

That doesn't sound right. The statistical bias in dice generally kicks
in when you roll multiple dice. Because there are more ways to make a
seven than, for example, a twelve or a two.

Luke

 

[Patricia Shanahan]

So how do they do it? In the old days, there used to be 49 balls in a
tumbler, one would fall out, then another, then another, then another
until there were six. In fact, I seem to recall seeing on TV some of
the televised American lotteries where the same methods were employed.
If you wanted to simulate that, you would need an array of 49 numbers,
then pick a number at random, drop that number out of the array, shrink
it by one and then pick 1 - 48, then 1-47 etc. I guess the issue here
isn't the way that the picking is simulated, but the way that the
randomness is implemented. Is there any computer language, or program
or whatever that is capable of true random number selection based on
"statistically proven techniques" or is everything we consider to be
random just a close approximation?

The algorithm I suggested, a truncated Fisher-Yates, essentially
simulates the ball dropping process. After N iterations, the first N
elements of the array contain the numbers that have been picked. The
remaining length-N elements contain the numbers that were in the
original array but have not yet been picked, and so can be picked in the
future.

However, its accuracy is dependent on the quality of the underlying
random number generator.

There are several approaches to getting random numbers.

The ball dropping machine, rolling dice, tossed coins, and spinning
roulette wheels all depend on physical processes that are designed so
that very small changes in the initial conditions can make large, hard
to predict, changes in the outcome.

The strongest sources of random numbers are really unpredictable
physical processes. For example, each atom of some isotope has a known
probability of decaying in any given time interval, but we have no way
of predicting which will decay when. The clicks of a Geiger counter are
as close to true randomness as we can get.

java.util.Random, and similar software random number generators, are
"pseudo-random". It takes a seed value, and does a repeated computation
on it to get the next seed. Selected bits of the seed are returned as
e.g. nextInt(). The results are designed to LOOK random, but the
complete sequence of results is fixed once the seed has been chosen.

Patricia

 

[Print Guy]

So why are the result of your program so much differnent from the ones
by the responder from gmail.com

Starting:Fri Aug 18 21:07:14 ADT 2006
Rank 1 number is 44
Rank 2 number is 40
Rank 3 number is 48
Rank 4 number is 43
Rank 5 number is 47
Rank 6 number is 45
Ending:Fri Aug 18 21:07:28 ADT 2006


vs

[27, 28, 3, 19, 45, 15]

My (your) numbers were all in the 40's where the other ones were more
scattered.

 

[Print Guy]

That doesn't sound right. The statistical bias in dice generally kicks
in when you roll multiple dice. Because there are more ways to make a
seven than, for example, a twelve or a two.

Luke

Agreed but if you roll one dice say 10 or 20 times, you are more apt to
get a 3 or 4 than any other number... let me see if I can find a link
to verify this...

And of course I can't find it... I'll search some more tomorrow.... I
like the way this thread turned out.... I got lots of good ideas and
now it's time to continue reading.... I wonder if Ruby can do this kind
of stuff ;-) (**ducks***)

 

[Print Guy]

Apparently 4 is the best number of of 6

http://en.wikibooks.org/wiki/Image:Histogramofdice.png

 

[Patricia Shanahan]

Apparently 4 is the best number of of 6

http://en.wikibooks.org/wiki/Image:Histogramofdice.png

You are taking a single image badly out of context. See
http://en.wikibooks.org/wiki/Statistics:Displaying_Data/Histograms.
It is an example of a hypothetical set of dice rolls, for part of a
statistics course. As the page says "This could be the result of chance,
or it could represent an actual anomaly in the data and it is something
to take note of keep in mind.".

If I had been the person constructing the page, I would have used a
biased "dice" to ensure an interesting histogram.

Patricia

 

[Patricia Shanahan]

Agreed but if you roll one dice say 10 or 20 times, you are more apt to
get a 3 or 4 than any other number... let me see if I can find a link
to verify this...

That may be a property of dice from some manufacturer, though they would
probably not stay in business long if people found out. However, I think
you may be confusing the single roll situation with the effect of adding
the results of a lot of rolls.

For example, if you roll two fair dice, there is only one combination,
a=6, b=6, that gives a 12. On the other hand, there are 6 ways of
getting a total of 7.

According to http://en.wikipedia.org/wiki/Loaded_dice, "There is some
controversy over whether manufacturing processes create genuinely "fair"
dice (dice that roll with even distributions over their number span).
Casino dice are legally required to be fair; those used by all others
hold no such requirement." Note that if dice were consistently and
measurably biased towards 4 there would be no controversy - it would be
easy to prove. For there to be a controversy, any bias must be tiny.

Also, http://en.wikipedia.org/wiki/Craps discusses craps strategy solely
in terms of the odds that would apply if the dice are fair. That
suggests that there is no common bias.

Patricia

 

[Patricia Shanahan]

So why are the result of your program so much differnent from the ones
by the responder from gmail.com

Starting:Fri Aug 18 21:07:14 ADT 2006
Rank 1 number is 44
Rank 2 number is 40
Rank 3 number is 48
Rank 4 number is 43
Rank 5 number is 47
Rank 6 number is 45
Ending:Fri Aug 18 21:07:28 ADT 2006


vs

[27, 28, 3, 19, 45, 15]

My (your) numbers were all in the 40's where the other ones were more
scattered.

Your method for finding the six most frequent numbers does not make
sense to me. Could you explain how it is supposed to work? Specifically,
why do you assign 0 to BigList[y] where you do? And why the three loops?


// now find the top six and create a new array called topSix
int[] topSix = new int[6];
for (int count = 0; count <= topSix.length - 1; count++) {
int lIndex = 0;
int largest = BigList[0];
// compare each element of BigList with each "other"
// element
// of BigList (I created this algorithm on my own, or maybe
// I
// rememered
// it from somewhere.
for (int x = 0; x <= BigList.length - 1; x++) {
for (int y = x + 1; y <= BigList.length - 2; y++)
if (BigList[y] > largest) {
largest = BigList[y];
BigList[y] = 0;
lIndex = y;
topSix[count] = lIndex;
}

}
}

I would have done something like the following, except I've kept your
variable names to make the relationships clearer:

***** Warning! Warning! untested code ahead! ******

int[] topSix = new int[6];
for(int count = 0; count < topSix.length; count++){
int lIndex = 0;
int largest = BigList[0];
for( int x = 1; x < BigList.length; x++){
if(BigList[x] > largest){
largest = BigList[x];
lIndex = x;
}
}
topSix[count] = lIndex;
BigList[lIndex] = 0;
}

only zeroing out a BigList element when I definitely commit to its index
being in the topSix.

 

[David Segall]

Actually, the odds are that if you roll a dice, you will get a 3 or 4
more than any other number

Not true. The chances of rolling any number are exactly one in six if
the dice has been perfectly made. It is true that for real physical
devices there will be a bias but it is unlikely that will be apparent
over the statistics available from Lotto draws. It is obviously
impossible for you to simulate that bias with any computer program.

[OT] 1 http://www.random.org/ offers a source of "true" random numbers
based on the noise you hear when your radio is not tuned to a station.

[OT] 2 A friend spent a week observing a roulette wheel in a casino
and decided he had located a bias. As soon as he started betting the
staff picked up the wheel he was at and dropped in a different one.

 

[Daniel Dyer]

So how do they do it? In the old days, there used to be 49 balls in a
tumbler, one would fall out, then another, then another, then another
until there were six. In fact, I seem to recall seeing on TV some of
the televised American lotteries where the same methods were employed.
If you wanted to simulate that, you would need an array of 49 numbers,
then pick a number at random, drop that number out of the array, shrink
it by one and then pick 1 - 48, then 1-47 etc. I guess the issue here
isn't the way that the picking is simulated, but the way that the
randomness is implemented. Is there any computer language, or program
or whatever that is capable of true random number selection based on
"statistically proven techniques" or is everything we consider to be
random just a close approximation?

I think you're right, the more important issue is the source of the
randomness. That's not to say that the question which you posed was not
an interesting programming problem. I think that Patricia's solution is
particularly elegant (once I switched on my brain and understood why she
was doing it that way).

This article
(http://www.cigital.com/papers/download/developer_gambling.pdf) is an
interesting story of how flaws in random number generation and shuffling
algorithms allowed the authors to exploit an online poker site.

I'm not sure what you mean by "statistically proven techniques" for
generating random numbers. There are however several tests that can be
applied to a sequence of numbers in order to obtain a measure of "how
random" the sequence is (or more correctly, a measure of how confident we
should be that the sequence is truly random, since the statistics don't
actually *prove* anything about the sequence). The most well-known of
these tests is the Diehard suite (http://stat.fsu.edu/pub/diehard/).
java.util.Random performs poorly on the Diehard suite, whereas
java.security.SecureRandom performs well. I would imagine that the
revelant gaming authorities have tested the performace of the lottery
machines, using Diehard or similar, before awarding a licence in order to
satisfy themselves that the outcomes are sufficiently random.

People who are seriously interested in good quality, unpredictable random
numbers (i.e. cryptographers and online gaming operators) will typically
use hardware devices that extract entropy from physical processes such as
radioactive decay or electronic noise. The random bits from these devices
(which are invariably slow) are often used as a seed for a PRNG with known
statistical properties rather than relied upon in their own right.

A cheaper variation on this theme is to rely on sources of randomness that
are already present in the computer hardware. The Solaris kernel, for
example, extracts entropy from I/O timings in order to provide random
numbers via /dev/random.

Are you interested in lotteries just as a programming exercise or are you
seriously hoping to find a way to beat the system?

If you are interested in this kind of thing, maybe you should consider
other types of gambling (i.e. roulette, blackjack, poker). For a start,
the expected return on the lottery is abysmal (only about 50% of the money
staked goes into the prize pool). So you have to have a huge edge in
order to overcome the inherent disadvantage of playing the game in the
first place. Blackjack on the other hand has an expected return of
somewhere in the region of 99.4% (depending on the exact rules in use).
In other words, if you play optimally (and it's not difficult to learn to
do so), on average you will only lose 3 cents for every $5 you stake.
This is still a losing proposition in the long-run, but you'd only need to
find a slight edge to turn it around. Traditionally professional gamblers
found this edge by card-counting, but the casinos have since introduced
measures to prevent this such as using more decks and a continous
shuffling machine.

The book "Fortune's Formula", by William Poundstone, is a good read.
Among other things, it discusses money-making systems that have been used
for Roulette, Blackjack and the stock market and looks at the ideas behind
them, dating back to Shannon's work on information theory in the 1940s.

Dan.

 

[Daniel Dyer]

So why are the result of your program so much differnent from the ones
by the responder from gmail.com

Starting:Fri Aug 18 21:07:14 ADT 2006
Rank 1 number is 44
Rank 2 number is 40
Rank 3 number is 48
Rank 4 number is 43
Rank 5 number is 47
Rank 6 number is 45
Ending:Fri Aug 18 21:07:28 ADT 2006


vs

[27, 28, 3, 19, 45, 15]

My (your) numbers were all in the 40's where the other ones were more
scattered.

While the first output does look suspicious, it could just be a freak
occurrence. Have you only run it once or does it favour high numbers over
repeated runs?

This may not be the cause of the anomaly, but both programs make the
mistake of creating a new Random object for each random number generated.
You should only ever use one Random instance and instead make multiple
calls to it. Not only is it more efficient this way, it will avoid
potential problems with the seeds of the instances being the same or very
similar when they are used to generate only one number before being
discarded.

Dan.

 

[Print Guy]

So why are the result of your program so much differnent from the ones
by the responder from gmail.com

Starting:Fri Aug 18 21:07:14 ADT 2006
Rank 1 number is 44
Rank 2 number is 40
Rank 3 number is 48
Rank 4 number is 43
Rank 5 number is 47
Rank 6 number is 45
Ending:Fri Aug 18 21:07:28 ADT 2006


vs

[27, 28, 3, 19, 45, 15]

My (your) numbers were all in the 40's where the other ones were more
scattered.

Your method for finding the six most frequent numbers does not make
sense to me. Could you explain how it is supposed to work? Specifically,
why do you assign 0 to BigList[y] where you do? And why the three loops?


// now find the top six and create a new array called topSix
int[] topSix = new int[6];
for (int count = 0; count <= topSix.length - 1; count++) {
int lIndex = 0;
int largest = BigList[0];
// compare each element of BigList with each "other"
// element
// of BigList (I created this algorithm on my own, or maybe
// I
// rememered
// it from somewhere.
for (int x = 0; x <= BigList.length - 1; x++) {
for (int y = x + 1; y <= BigList.length - 2; y++)
if (BigList[y] > largest) {
largest = BigList[y];
BigList[y] = 0;
lIndex = y;
topSix[count] = lIndex;
}

}
}

I would have done something like the following, except I've kept your
variable names to make the relationships clearer:

***** Warning! Warning! untested code ahead! ******

int[] topSix = new int[6];
for(int count = 0; count < topSix.length; count++){
int lIndex = 0;
int largest = BigList[0];
for( int x = 1; x < BigList.length; x++){
if(BigList[x] > largest){
largest = BigList[x];
lIndex = x;
}
}
topSix[count] = lIndex;
BigList[lIndex] = 0;
}

only zeroing out a BigList element when I definitely commit to its index
being in the topSix.

Well if each element of "BigList" contains the number of times it was
picked when I did 6 selections, 1 million times then
a) I need the top six (outer most loop)
b) I need to compare each number (inner loop number 1)
c) with each other number (inner loop number 2)

Seems to me that topSix should now contain the top six picks but I
could be wrong..

 

[Print Guy]

Actually, the odds are that if you roll a dice, you will get a 3 or 4
more than any other number

Not true. The chances of rolling any number are exactly one in six if
the dice has been perfectly made. It is true that for real physical
devices there will be a bias but it is unlikely that will be apparent
over the statistics available from Lotto draws. It is obviously
impossible for you to simulate that bias with any computer program.

[OT] 1 http://www.random.org/ offers a source of "true" random numbers
based on the noise you hear when your radio is not tuned to a station.

[OT] 2 A friend spent a week observing a roulette wheel in a casino
and decided he had located a bias. As soon as he started betting the
staff picked up the wheel he was at and dropped in a different one.

Yes, the odds are 1 in 6 if you roll a dice once. But what if you roll
a 6 sided dice 5000000 times? I still think that 4 or 5 will occur
more times... I don't have time to roll a dice that many times, but it
makes sense that it should apply no matter how many times you roll the
die as long as it is a large number of times.

 

[Daniel Dyer]

Yes, the odds are 1 in 6 if you roll a dice once. But what if you roll
a 6 sided dice 5000000 times? I still think that 4 or 5 will occur
more times... I don't have time to roll a dice that many times, but it
makes sense that it should apply no matter how many times you roll the
die as long as it is a large number of times.

If the odds are 1 in 6 for the first roll, wouldn't they be 1 in 6 for the
second roll too? And for the third roll, and so on.

Why do you think 4 and 5 are more likely?

Perhaps you are confusing a uniform distribution with a normal
distribution (a.k.a "bell curve")?

Dan.

 

[Patricia Shanahan]

So why are the result of your program so much differnent from the ones
by the responder from gmail.com

Starting:Fri Aug 18 21:07:14 ADT 2006
Rank 1 number is 44
Rank 2 number is 40
Rank 3 number is 48
Rank 4 number is 43
Rank 5 number is 47
Rank 6 number is 45
Ending:Fri Aug 18 21:07:28 ADT 2006


vs

[27, 28, 3, 19, 45, 15]

My (your) numbers were all in the 40's where the other ones were more
scattered.

Your method for finding the six most frequent numbers does not make
sense to me. Could you explain how it is supposed to work? Specifically,
why do you assign 0 to BigList[y] where you do? And why the three loops?


// now find the top six and create a new array called topSix
int[] topSix = new int[6];
for (int count = 0; count <= topSix.length - 1; count++) {
int lIndex = 0;
int largest = BigList[0];
// compare each element of BigList with each "other"
// element
// of BigList (I created this algorithm on my own, or maybe
// I
// rememered
// it from somewhere.
for (int x = 0; x <= BigList.length - 1; x++) {
for (int y = x + 1; y <= BigList.length - 2; y++)
if (BigList[y] > largest) {
largest = BigList[y];
BigList[y] = 0;
lIndex = y;
topSix[count] = lIndex;
}

}
}

I would have done something like the following, except I've kept your
variable names to make the relationships clearer:

***** Warning! Warning! untested code ahead! ******

int[] topSix = new int[6];
for(int count = 0; count < topSix.length; count++){
int lIndex = 0;
int largest = BigList[0];
for( int x = 1; x < BigList.length; x++){
if(BigList[x] > largest){
largest = BigList[x];
lIndex = x;
}
}
topSix[count] = lIndex;
BigList[lIndex] = 0;
}

only zeroing out a BigList element when I definitely commit to its index
being in the topSix.

Well if each element of "BigList" contains the number of times it was
picked when I did 6 selections, 1 million times then
a) I need the top six (outer most loop)
b) I need to compare each number (inner loop number 1)
c) with each other number (inner loop number 2)

Nope, you only need to compare each number to the best so far.

And you have not said why you zero out a value before you have committed
to putting its index in topSix.

Seems to me that topSix should now contain the top six picks but I
could be wrong..

Try separating it out into a method, and taking it for a test drive with
known data.

Patricia

 

[Patricia Shanahan]

Actually, the odds are that if you roll a dice, you will get a 3 or 4
more than any other number

Not true. The chances of rolling any number are exactly one in six if
the dice has been perfectly made. It is true that for real physical
devices there will be a bias but it is unlikely that will be apparent
over the statistics available from Lotto draws. It is obviously
impossible for you to simulate that bias with any computer program.

[OT] 1 http://www.random.org/ offers a source of "true" random numbers
based on the noise you hear when your radio is not tuned to a station.

[OT] 2 A friend spent a week observing a roulette wheel in a casino
and decided he had located a bias. As soon as he started betting the
staff picked up the wheel he was at and dropped in a different one.

Yes, the odds are 1 in 6 if you roll a dice once. But what if you roll
a 6 sided dice 5000000 times? I still think that 4 or 5 will occur
more times... I don't have time to roll a dice that many times, but it
makes sense that it should apply no matter how many times you roll the
die as long as it is a large number of times.

What is your definition of "odds"?

It seems clear that you are not following the frequency interpretation
of probability because in that approach the probability of a four on a
single rolls is defined to be the limit, as N tends to infinity, of the
proportion of fours in N rolls.

You seem to have different opinions about the proportion of fours in a
large number of rolls and the probability of a four on a single roll?

Patricia

 

[Patricia Shanahan]

....

Seems to me that topSix should now contain the top six picks but I
could be wrong..

I'm afraid you are wrong, and the apparent over-selection of the high
numbers is due to bugs in your top six selection.

I've written a simple test program comparing the two methods. Take a
look at it, and take it for a test drive:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class TopSixTest {

public static void main(String[] args) {
int[] data = new int[49];
// Fixed seed for reproducibility
Random rand = new Random(5);

for (int i = 0; i < data.length; i++) {
data = 5;
}
System.out.println("data==5");
test(data);

for (int i = 0; i < data.length; i++) {
data = i + 1;
}
System.out.println("data==i+1");
test(data);

for (int i = 0; i < data.length; i++) {
data = 100 - i;
}
System.out.println("data=100-i");
test(data);

testRandomData(rand);
testRandomData(rand);
testRandomData(rand);
}

/**
* Test random permutation of numbers from 1000 through 1048
*
* @param rand
*/
private static void testRandomData(Random rand) {
int[] data = new int[49];
List<Integer> dataList = new ArrayList<Integer>();
for (int i = 0; i < data.length; i++) {
dataList.add(new Integer(1000 + i));
}
Collections.shuffle(dataList, rand);
for (int i = 0; i < data.length; i++) {
data = dataList.get(i).intValue();
}
System.out
.println("Random permutation of 1000 through 1048");
test(data);
System.out.println("Actual positions of largest 6 elements");
for (int i = 1048; i > 1042; i--) {
System.out.printf("%d %d", i, dataList
.indexOf(new Integer(i)));
System.out.println();
}
}

/**
* Print the results of both methods on the input data
*
* @param data
* "BigList" data, a 49 element frequency array.
*/
private static void test(int[] data) {
int[] printsTop = printsVersion(data.clone());
int[] patsTop = patsVersion(data.clone());
for (int i = 0; i < 6; i++) {
System.out.printf("%d Print's %d Pats's %d", i,
printsTop, patsTop);
System.out.println();
}
}

private static int[] printsVersion(int[] BigList) {
int[] topSix = new int[6];
for (int count = 0; count <= topSix.length - 1; count++) {
int lIndex = 0;
int largest = BigList[0];
for (int x = 0; x <= BigList.length - 1; x++) {
for (int y = x + 1; y <= BigList.length - 2; y++)
if (BigList[y] > largest) {
largest = BigList[y];
BigList[y] = 0;
lIndex = y;
topSix[count] = lIndex;
}

}
}
return topSix;
}

private static int[] patsVersion(int[] BigList) {
int[] topSix = new int[6];
for (int count = 0; count < topSix.length; count++) {
int lIndex = 0;
int largest = BigList[0];
for (int x = 1; x < BigList.length; x++) {
if (BigList[x] > largest) {
largest = BigList[x];
lIndex = x;
}
}
topSix[count] = lIndex;
BigList[lIndex] = 0;
}
return topSix;
}

}

 

[Patricia Shanahan]

...

Seems to me that topSix should now contain the top six picks but I
could be wrong..

I'm afraid you are wrong, and the apparent over-selection of the high
numbers is due to bugs in your top six selection.

I've written a simple test program comparing the two methods. Take a
look at it, and take it for a test drive: ....
private static int[] patsVersion(int[] BigList) {
int[] topSix = new int[6];
for (int count = 0; count < topSix.length; count++) {
int lIndex = 0;
int largest = BigList[0];
for (int x = 1; x < BigList.length; x++) {
if (BigList[x] > largest) {
largest = BigList[x];
lIndex = x;
}
}
topSix[count] = lIndex;
BigList[lIndex] = 0;

This line should be:

BigList[lIndex] = -1;

Zero is a possible count of the number of instances of a result. -1 is not.