Programming Forums - Problem with random numbers

Programming Forums (http://www.programmingforums.org/forumindex.php)

- C (http://www.programmingforums.org/forum60.html)

- - Problem with random numbers (http://www.programmingforums.org/showthread.php?t=10466)

Problem with random numbers

Me and a friend were in an argument. He said if a coin flipped heads 10 times in a row, it would be more likely to flip tails the next time than heads. I disagreed with him, and decided to write a program to simulate what he was saying to prove to him that it would be approximately 50-50. I wrote the program, and it served its purpose -- it convinced my friend, but afterwards I noticed some anomalies with the results. Here is the code:

#include <stdio.h>

#include <time.h>

#include <stdlib.h>

#include <conio.h>



#define ONES 1

#define ZEROES 0



int main(void)

{

        srand(time(0));

        int ones = 0;

        int zeroes = 0;

        int consecutive_zeroes = 0;

        int consecutive_ones = 0;

        int after_ten_zeroes[2] = {0, 0};

        int after_ten_ones[2] = {0, 0};

        

        for(int i = 0; i<1000000; i++)

        {



                 int temp = rand()%2;

                 if(temp == 1)

                 {

                          if(consecutive_zeroes == 10)

                          {

                                   after_ten_zeroes[ONES]++;

                                   consecutive_zeroes = 0;

                          }

                          else if(consecutive_ones == 10)

                          {

                                   after_ten_ones[ONES]++;

                                   consecutive_ones = 0;

                          }                                                                  

                          ones++;

                          consecutive_zeroes = 0;

                          consecutive_ones++;

                 }         

                 else

                 {

                         if(consecutive_zeroes == 10)

                         {

                                  after_ten_zeroes[ZEROES]++;

                                  consecutive_zeroes = 0;

                         }

                         else if(consecutive_ones == 10)

                         {

                                  after_ten_ones[ZEROES]++;

                                  consecutive_ones = 0;

                         }                                                           

                         zeroes++;

                         consecutive_ones = 0;

                         consecutive_zeroes++;

                 }

        }

        

        printf("After ten consecutive zeroes, there were %d zeroes and %d ones.\n", after_ten_zeroes[ZEROES], after_ten_zeroes[ONES]);

        printf("After ten consecutive ones, there were %d zeroes and %d ones.\n", after_ten_ones[ZEROES], after_ten_ones[ONES]);

        printf("In total there were %d zeroes and %d ones.\n", zeroes, ones);

        getche();

        

        return 0;

}

The results were as follows:

After ten consecutive zeroes, there were 211 zeroes and 203 ones.

After ten consecutive ones, there were 209 zeroes and 213 ones.

In total there were 499882 zeroes and 500118 ones.

All the results were pretty similar. There are a couple of anomalies I see in the results, though. First, I ran the program about ten times and each time there were more zeroes than ones when preceeded by ten successive zeroes, and more ones than zeroes when preceeded by ten succesive ones. Furthermore, in a million runs, I should get somewhere around 976 ([1/{2^10}]*1000000) observations of ten consecutive zeroes and ones, however in all my runs I don't believe I ever got over 850. It is probably a stupid error in my code, but I can't seem to find it. Anyone got any ideas why the results of my program are coming out the way they are? Thanks in advance for your help and time.

Well it's kind of early in the morning, so I can't think straight yet, but what happens when you have 10 consecutive ones? You set consecutive_ones to 0, and then increase consecutive_ones again. Likewise for zeroes. Is that really what you want?

A side note, if you'd try to compile this as C then it would not (at least not C89). You cannot declare an int in a for loop. And you cannot have srand(time(0)); as the first statement, since declarations should go first.

And why do you declare a temp variable when you only use it once to test it? You migth as well do: if(rand()%2 == 1).

I tried this out in VC2003 and got a similar result with the consecutive ones being followed by a one and consecutive zeros being followed by a zero. I think that is just an artifact of the psuedo random nature of rand()

To test this out I downloaded a different random number generator from here and tried it again. This time there was no discernable pattern to the next value after 10 1s or 10 0s

The reason you are not getting the counts you are expecting for the number of runs of 10 is that you reset the counter to 0 when you find a run of 10. In your probability calculation a run of 11 zeros would actually count as 2 runs of 10, but in your program it would only count for 1. You can fix this by setting the counters back to 9 instead of 0 when you have hit a run of 10 (although this does make the code look a bit odd).

>He said if a coin flipped heads 10 times in a row, it would be more likely to flip tails the next time than heads.
Statistically, this is true. Each time you flip the coin you have an equal chance of getting heads or tails. But long spans of either heads or tails is improbable, and the longer the span, the greater the chances of your next flip being different. Flipping two heads would be expected, but ten would be pushing the limits of probability, twenty would be a shocking deviance, and thirty would find you being tested for demonic possession.

>Anyone got any ideas why the results of my program are coming out the way they are?
It's not an accurate test. rand is generally a comparatively poor algorithm, and you're hurting the distribution in the way that you drop the range to 0 and 1. A better way using rand would be:

if ( rand() < RAND_MAX / 2 ) {

  /* Heads */

}

else {

  /* Tails */

}

This maintains the uniform distribution of the entire range that rand expects, but still gives you a yes or no result.

Quote:

Statistically, this is true.

Actually, it isn't. While the probability of flipping 10 heads in a row is low, the probablity of flipping 10 heads and a tail or 10 heads and a head are the same. Usual caveats of independence, no bias, etc.

>Actually, it isn't.

Beat me to it; that's exactly right.

Quote:

Originally Posted by nnxion

That was what I originally thought the problem was as well, however after looking it over many times, I do believe that is what I wanted, as the 11th 0 or 1 should be the beginning of a new sequence.

Quote:

A side note, if you'd try to compile this as C then it would not (at least not C89). You cannot declare an int in a for loop. And you cannot have srand(time(0)); as the first statement, since declarations should go first.

Good points. I get lazy with what the compiler allows me to do. :o It's a bad habit that I need to break.

Quote:

And why do you declare a temp variable when you only use it once to test it? You migth as well do: if(rand()%2 == 1).

Another good point. For some reason, when I started writing my program, I thought I was going to have to perform more tests on it than that. I'm not sure exactly what I was thinking, but that is the reason it is there.

Quote:

It's not an accurate test. rand is generally a comparatively poor algorithm, and you're hurting the distribution in the way that you drop the range to 0 and 1. A better way using rand would be:

<snip>

This maintains the uniform distribution of the entire range that rand expects, but still gives you a yes or no result. Today 05:16 AM

Thanks, I'll try that. Sorry for my ignorance, but I don't understand why exactly modding by 2 hurts the distribution.

Quote:

The reason you are not getting the counts you are expecting for the number of runs of 10 is that you reset the counter to 0 when you find a run of 10. In your probability calculation a run of 11 zeros would actually count as 2 runs of 10, but in your program it would only count for 1. You can fix this by setting the counters back to 9 instead of 0 when you have hit a run of 10 (although this does make the code look a bit odd).

Ahh, thanks. That was drving me insane. I did want it to reset, however I didn't expect that would be one of the consequences.

>Actually, it isn't.
Sure it is...when you misread the question like I did. :rolleyes: :p

LOL, Narue, I promise you that I think twice before contradicting you.

>Narue, I promise you that I think twice before contradicting you.
I'm not *that* scary, am I? ;)