Flipping coin

There is a very very very good possibility that the random number generator is designed to return an even distribution of numbers, completely invalidating your research for any kind of ''Vegas'' schemes.

You must find another way of generating your random numbers. Then do the test.

I had the unfortunate experience of taking a "Random Processes" course this last quarter.

First, Bishop is correct. The standard C rand function has memory. The correlation between all runs is not 0 for all points besides the same run. Therefore, you can use past runs to predict the next run with better accuracy.

As for coin flips, you''ll have to find a coin that has a probability of exactly 0.5. They''re hard to find (one side is usually slightly heavier). And tossing one a million times will take quite a while.

Anecdotally, I''d suggest watching "Rosencrans and Guildenstern are Dead". Not only do you get a bizarrely funny movie with Tim Roth and Gary Oldman, the first 10 minutes are spent flipping a coin and having it come up heads every time.

quote:

---

hey, maybe its just a problem with the random generator, but I dont think so

---

Short answer: it is. Sorry.

Totally off topic, but i love that movie - especially when he tries to demonstrate physics principles

Wyzfen

oh and on topic, doesn't the rand function return values between 0 and RAND_MAX inclusive ? which is an uneven number of possible values, so an even split would favour the upper half.
if you are evenly splitting down the middle, then the shape of the distribution shouldn't be relevant.

but anyway, what i used to do is:
do{ rand_value=rand() }while( rand_value==RAND_MAX);

Edited by - wyzfen on December 20, 2000 10:11:56 PM

Theoretically the split should be 50/50. But that''s based on the law of large numbers. It''s entirely possible that someone could flip a coin for 100 years and not achieve a 50/50 ratio. Or if he did it would change on the next flip.

The Chi-Square goodness-of-fit test was created for cases like this. But I''m not really interested in rehashing my college days. It''s probably on the web somewhere. But my guess is that a 0.2% difference would not qualify as chi-failure.

Interesting theory. So exactly how much does the result of this test make you willing to bet on the outcome the the 1,000,000,001th flip knowing the distribution of the previous 1,000,000,000 flips? And how much more is that than what you would be willing to bet on the first flip? My guess is that it would be 0% more.

hehe, I wasnt looking to make money in Vegas, I was just bored

If you''re really bored, try using chaos theory to predict the stockmarket

---

NPCs will be inherited from the basic Entity class. They will be fully independent, and carry out their own lives oblivious to the world around them ... that is, until you set them on fire ...

The point about a rare 50/50 coin is true. But this guy is using a random number generator so it''s a moot point.

"Consider that you''ve flipped a coin that you believe to be fair 99 times and you''ve gotten heads every single time. Now somebody asks you what you think you''re going to get the next time.
.
.
.
"

Let me iron this out a bit with what I remember from my college days. There are three versions of statistical probability and what you are describing is a mish mash of all of them.

To make it less confusing:

1) a mutually exclusive and collectively exhaustive event (a coin toss for example) has a total probability of 1.0. Since there are only 2 outcomes *theoretically* the chance of a head or tail is 0.5. This is called the Objective or Classical theory of probability.

2) an event that occurs 99 times in 100 observations has a relative frequency of 99%. This is the Relative Frequency concept of probability, and is also considered Objective.

3) if you walked in on the coin-flipper just before he was going to do his 100th flip, you''d know the Objective probability (50%), but you wouldn''t know the Relative Frequency probability. So, you''d probably guess 50% on the next flip. This is called the Subjective concept of probability because you must make a personal judgement call on what data to use in calculating your probability.

Hopefully you can wrap your head around that a bit better.

As long as you are bored why not do a histogram of the lengths of sequences of the same outcome. Basically each time you flip check if it is the same as the last flip. If it is then increment a counter. If it isn''t then increment a counter in an array of counters indexed by the first counter. Just to be on the safe side you should make sure that is a valid array entry. If it isn''t then either keep a seperate count of all sequence greater than the size of the array or add it to the last one. That will give you a better feel for how random, i.e. unpredictable, the results are. As an example if all the sequences are length 1 then it is 100% predictable even if the distribution is 50/50, i.e. the next flip would always be the opposite of the last flip. If it is fairly random then you should only be right 50% of the time by saying it will be the opposite of the last flip so the number of sequences of length one should be half the number of flips. The other half is going to be the same, but the next flip after that is going to be differant 50% of the time. So the sequences of length two should occur one quarter of the time. So the count of sequence of length two should be one half the count of sequences of length one. That pattern should continue.

Tis the nature of random that even with a purely random outcome, if such a thing existed, that it won''t always be true, just likely to be true, i.e. it is highly unlikely that 100 flips in a row will come out the same, but 1/2^100th of the time it will on average and that could be the first 100 flips. It might not happen at all within 2^100 flips or might happen many times. You are not dealing with a truely random outcome though and there could be errors in the implementation of the generator you are using. So if you see a repeatable skewing of the distribution of the sequence lengths it doesn''t say anything about random events in general. Generally you test a generator to see if it produces results reasonably similar to what would be expected from a truely random outcome rather than using a generator to prove what should happen with a truely random outcome.

The test you ran wouldn''t give you much confidence in the generator. Just as an example if the flips formed a pattern of 23 heads followed 23 tails then in a million flips heads comes up roughly 50% of the time. It won''t be exact because 46 doesn''t go evenly into 1,000,000 so it would depend on where within the 46 you started. I believe your prediction would come out pretty close to 50% as well. What you predicted would be highly skewed depending upon whether you started with the first heads or last out of the 23 consecutive ones, but whether your prediction is right or wrong shouldn''t be since predicting tails all the time is right roughly 50% of the time. Now to your player 23 heads followed by 23 tails repeating into eternity is going to seem anything but random. Humans are very good at recognizing patterns. They are also impatient. They are not going to wait until they have seen a million outcomes to decide if it is really random or if there is a pattern. So using 10,000 differant seeds to test 100 flips would be better than testing a million flips. You can''t use the random generator to generate the seeds though. If you generated the seeds first the test would degenerate into generating 10,100 random numbers and testing 0..99,1..100,2..101, ect. If you generated a new seed after each test it would be the same as just calling rand. Instead you have to just increment it such as starting with the current time and adding the seconds in a year divided by 10,000.

"Generally you test a generator to see if it produces results reasonably similar to what would be expected from a truely random outcome rather than using a generator to prove what should happen with a truely random outcome."

As I said in a previous post, this is what the Chi-square goodness-of-fit test does.

chi^2=sigma(observed frequency-expected frequency)^2/expected frequency.

Perhaps I don''t understand chi square, but I don''t see how it would be a useful test. It is useful for things like determining if there is a statistically significant variance in something like sales by category by region, but I don''t see how it applies here. What would your rows and columns be? The count by outcome by outcome? Wouldn''t all the counts have to fall on the diagonal?

Why is variance testing limited to sales?

Chi-squares is used in any scenario to determine how well an observed data set fits an expected set. That can be anything... from sales, to slot machines, to a loaded set of dice. Or even a random number generator that flips "heads" too much

Kick me in the forehead if im off base here, but wouldn''t the very act of flipping the coin cause the weights to shift slightly to favor one side or another?

Granted, they would be close, but that tiny amount could make a difference on say 1,000,000+ flips.

The point wasn''t that it is only applicable to sales, but rather only to data of two dimensions. I don''t see a valid way to get a second dimension from this data. If you were comparing two generators you could use it. Which generator would provide a valid second dimension. You could then say whether there is a statistically significant variance between the frequency of heads and tales between the two generators. You could also test whether two means of deciding if the result was heads or tales from the generated number vary significantly such as (rand()*2)/MAX_RAND and rand()%2. There are altenatives to what I suggested, but I don''t see how Chi Square is one of them. Perhaps if you could explain how you would get a second dimension instead of just repeating to use Chi Square I might better understand.

ok, major bump from me. Just curious how did they come up w/ the name Chi-Square for this particular test? Did some oriential person named Chi first propose such a test or something?

---

--{You fight like a dairy farmer!}

Chi refers to the greek letter used when writing the function. It sort of looks like a X with flair.

Mathworld is your friend.

WEll, if you re-seeded the random number generator with say clock()/day or clock/month clock/year in the loop, then youd be getting more random results correct?

-Dan

Yes I realize im a n00b...

The time might not change between each loop though because the loop is probably really fast. So you risk that chance.

I wonder what would happen if you reseeded it to a random number based off of the current seed though.

Can''t you use www.random.org as your source of really true random numbers?

Use this form to get a file of raw random bytes, and use that as your source of random numbers.

Do it a couple of times, and I''m sure that the output will make a lot more sense than the original.

If no one is willing do to this, I might just as well do it myself.

---
shurcooL`