Programming Forums > Application Development > C

Mjordan2nd · Jun 20th, 2006, 9:21 PM

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:

(Toggle Plain Text)

#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:

(Toggle Plain Text)

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.

nnxion · Jun 21st, 2006, 4:40 AM

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).

The Dark · Jun 21st, 2006, 5:16 AM

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).

Narue · Jun 21st, 2006, 8:16 AM

>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:

(Toggle Plain Text)

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.

DaWei · Jun 21st, 2006, 8:31 AM

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.

bivhitscar · Jun 21st, 2006, 8:52 AM

>Actually, it isn't.

Beat me to it; that's exactly right.

Mjordan2nd · Jun 21st, 2006, 8:55 AM

Quote:

Originally Posted by nnxion

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?

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.

Narue · Jun 21st, 2006, 1:41 PM

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

:p

DaWei · Jun 21st, 2006, 2:42 PM

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

Narue · Jun 21st, 2006, 4:15 PM

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

Jun 20th, 2006, 9:21 PM	#1
Mjordan2nd The Supreme Ruler Join Date: May 2004 Location: Houston Posts: 1,476 Rep Power: 6	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: (Toggle Plain Text) #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; } #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: (Toggle Plain Text) 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. 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. __________________ "Every gun that is made, every warship launched, every rocket signifies, in the final sense, a theft from those who hunger and are not fed, from those who are cold and are not clothed. The world in arms is not spending money alone. It is spending the sweat of its laborers, the genius of its scientists, the hopes of its children." - Dwight D. Eisenhower

Jun 21st, 2006, 4:40 AM	#2
nnxion Programming Guru Join Date: Jun 2005 Location: elemental plane Posts: 1,429 Rep Power: 5	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). __________________ "Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for." -- Socrates

Jun 21st, 2006, 8:16 AM	#4
Narue Professional Programmer Join Date: Sep 2005 Posts: 419 Rep Power: 4	>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: (Toggle Plain Text) if ( rand() < RAND_MAX / 2 ) { /* Heads / } else { / Tails / } 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. __________________ Even if the voices aren't real, they have some pretty good ideas.

Jun 21st, 2006, 8:52 AM	#6
bivhitscar Hobbyist Programmer Join Date: Oct 2005 Location: Melbourne, Australia Posts: 126 Rep Power: 3	>Actually, it isn't. Beat me to it; that's exactly right. __________________ it's ironic considerate rarity patron of love higher knowledge engulfs me...

Jun 21st, 2006, 1:41 PM	#8
Narue Professional Programmer Join Date: Sep 2005 Posts: 419 Rep Power: 4	>Actually, it isn't. Sure it is...when you misread the question like I did. :p __________________ Even if the voices aren't real, they have some pretty good ideas.

Jun 21st, 2006, 5:16 AM	#3
The Dark Expert Programmer Join Date: Jun 2005 Posts: 852 Rep Power: 4	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).

Jun 21st, 2006, 2:42 PM	#9
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	LOL, Narue, I promise you that I think twice before contradicting you. __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Jun 21st, 2006, 4:15 PM	#10
Narue Professional Programmer Join Date: Sep 2005 Posts: 419 Rep Power: 4	>Narue, I promise you that I think twice before contradicting you. I'm not that scary, am I? __________________ Even if the voices aren't real, they have some pretty good ideas.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Programming Forums > Application Development > C

Problem with random numbers