Help explaining test questions

DavidP · 11-09-2009, 01:05 PM

Quote:

1000 numbers are generated. If you take every four numbers as a sequence then you have 250 possible sequences where you could have four even numbers. There are actually 997 potential sequences, but the 250 is a subset of the total that is easier to work with. So if the odds are minuscule that none of the 250 groups are all even, then it means that the odds are even more minuscule that none of the 997 groups are all even.

I think you are misunderstanding the question.

Here's the question repeated:

Quote:

2) 1000 random integers are generated randomly with a uniform distribution over the range 1 to 1000 inclusive. Which of the following would indicate a poor generator?

(a) the average of the numbers is about 499
(b) each number appears exactly once
(c) no four consecutive numbers are all even
(d) two of the above
(e) all of (a), (b), and (c)

My interpretation: we have 1000 random samples. Each sample can have a numeric value between 1 and 1000. When we say "four consecutive numbers" we intend to mean "four numbers in order of which they were generated" and not "four numbers in numeric order from least to greatest or greatest to least".

Every time a new random sample is generated, we look at the last 4 random samples. Are they all even? I would hope not! Sure, it might happen every once in awhile, but the chances are low. Hence, the wording of the answer:

"NO four consecutive numbers are all even"

Having no four consecutive numbers that are all even would be a good indicator that my random number generator is truly random. Having 1 or 2 sequences that are all even might even be fine as well. Having several sequences that are all even would be very very bad.

Daved · 11-09-2009, 01:14 PM

>> Having no four consecutive numbers that are all even would be a good indicator that my random number generator is truly random.

IMO, you're right about MK27's confusion, but the above is wrong. Depending on how you define it, you should expect around either 31 or 62 sequences of four consecutive even numbers when generating 1000 random numbers.

MK27 · 11-09-2009, 01:59 PM

Quote:

Originally Posted by Daved

IMO, you're right about MK27's confusion

Yeah, I was considering the final set as ordered. You're right, it almost certainly should have sequences of 4 even numbers.

DavidP · 11-09-2009, 02:22 PM

Quote:

You're right, it almost certainly should have sequences of 4 even numbers.

True, in that point I do stand corrected.

But...if it didn't...would it be a sign of a bad random number generator? I guess that's the question we have to ask ourselves.

On a sidenote, I decided to play around a bit

I wrote the following code:

Code:

#include <iostream>
#include <vector>

using namespace std;

int rand_num(int min, int max)
{
	return ((int)((rand() % max) + min));
}

int main ( void )
{
	srand(time(NULL));
	
	int num_even_sets = 0;
	
	//Generate a set of 1000 samples
	vector <int> randomSet;
	for(int i = 0; i < 1000; i++ )
	{
		randomSet.push_back(rand_num(1, 1000));
	}
	
	//Go through and analyze for sequences of 4-evens
	for (unsigned int i = 0; i < randomSet.size(); i++ )
	{
		bool even = true;
		for(unsigned int j = i; j < (i + 4) && j < randomSet.size(); j++ )
		{
			if (randomSet[j] % 2 != 0) even = false;
		}
		
		if (even) num_even_sets++;
	}
	
	cout << "Number of sets where 4 consecutive random numbers are even: " << num_even_sets << endl;
	
	return 0;
}

My results:

The minimum number of "sequences of 4 consecutive even numbers" ever generated was 45, and the max was 88. The mean was 64.

Daved · 11-09-2009, 02:30 PM

>> if it didn't...would it be a sign of a bad random number generator?
Yes. If the odds of it happening are somewhere between 1 in 10^7 and 1 in 10^27 (I believe my calculation and CornedBee's calculation bound the probability), then if it does happen it is a sign of a bad generator. If the odds of it not happening were more like 1 in 3, then you could ascribe it to just chance, but with such great odds it is fairly certain that the number is wrong.

Also, my 125 to 500 number above was wrong. I had written a program, too, but there was a bug that caused the bad data. I think your results make sense (something that has a 1/16 probability will happen about 62 times out of 997 tries).

I wonder how many times do you have to run the program before it ever gave a result of 0? And more importantly, if it gave a result of 0 while you were still testing it, you'd probably assume there was a bug.

Mario F. · 11-09-2009, 06:11 PM

I'm totally at loss why question 2 is meriting such a long debate.
I don't need to write a piece of code to prove my point (which coincides with DavidP). Please do not think I'm being cocksure. It's just that I trully can't see where the problem is.

Let's work by elimination:

Premise:
It is said the RNG aims at having a uniform distribution

Step 1.
Answer (a) the average of the numbers is about 499
This one is a nobrainer. 499 is at the top of the bell curve. It's an acceptable result. It's in fact an expectable result coming of a uniform distribution RNG. Option a is not and cannot be a part of the answer. So this eliminates answer a and e.

Step 2.
Answer (b) each number appears exactly once
I cannot even start to fathom the odds for this to happen. They are huge. About the amount of starts on our galaxy? Help me with the math please:

What are the odds of a 6 sided dice throwing all possible numbers on 6 throws?
The first time we throw it's doesn't matter what number we get: 6/6
The second time one of the numbers was exhausted: 5/6
The third time we already can only throw 4 numbers: 4/6
And so forth: 3/6, 2/6 and finally the last throw there's only one number we can throw: 1/6

So the odds are: 6/6 * (5/6) * (4/6) * (3/6) * (2/6) * (1/6) = 0.015

Now do that for a dice with 1000 sides!

So b has to be the answer or part of the answer.

Step 3.
Answer (c) no four consecutive numbers are all even

Quote:

Quote:
You're right, it almost certainly should have sequences of 4 even numbers.

But...if it didn't...would it be a sign of a bad random number generator? I guess that's the question we have to ask ourselves.

This is my point of contention.

My interest for CornedBee calculation was raised here:
"Likelihood of four numbers containing at least one odd number: 15/16". And I'm not sure why the decision was made to then count the number of 4 number sequences in 1000 numbers. I think that alone demonstrates that c is not a correct answer. Which also eliminates d.

Daved · 11-09-2009, 06:20 PM

Could you clarify what you're saying Mario? The answer is d, because both b and c are correct. I'm not sure if you're disagreeing, or if we're just confused by the double and triple negatives.

Mario F. · 11-09-2009, 08:12 PM

I'm arguing the answer is b.

(c) can't be correct. It states "no four consecutive numbers are all even". And yet, it was confirmed the likelihood of four numbers containing at least one odd number is 15/16. That's ~93% chance an odd number will show up in a sequence of 4 numbers.

Next we get to the problem of how to calculate 4 number sequences. And I think we are accepting the "naive" approach too easily. It can't be correct because we are overlapping numbers and their odds.

Let's get back to a smaller numbers: The dice.
How many combinations of two numbers exist on 6 throws? 5. What's the odds of an odd number to show on 1 pair of numbers? 1/2. According to the "naive" approach this would mean 1/2^5 = 0.03. That's the odds of getting at least an odd number on every sequence of 2 throws after throwing the dice 6 times. That can't be correct. We know the odds of an odd number are 1/2.

Instead, I argue all we need is to calculate the odds of an odd number to show in one pair of throws. That calculation is unbounded. We do not need to look at the total of throws. The odds will remain the same.

Going back to the 1000 numbers and 1000 throws, what's the odds of an odd number to show in a sequence of 4 numbers? 15/16. And that's all we need to know. The odds aren't going to change because we throw 997 sequences of 4 numbers. The 15/16 calculation is the unbounded event. And all we need to know to reach the conclusion 93% chance of an odd number to show in a sequence of 4 numbers is a likely event. Thus this eliminates c.

EDIT:

Just for curiosity sake, help me if I'm getting this wrong:
The odds for (b) I think are calculated as follows (using my dice example on the previous post):

1000! / 1000^1000 = 4.023e-433
The odds I believe are "bigger" than the number of stars in the universe

Daved · 11-09-2009, 08:53 PM

I think you're misunderstanding c.

The question isn't whether there exist four even numbers in a single arbitrary sequence of four numbers. The question is whether there is exist four even numbers in any sequence of four numbers. So you're right that if you arbitrarily picked four consecutively generated numbers, there's a 93% chance that one will be odd, but that's not what the question is asking. It's asking you to go through the entire list of 1000 generated numbers and see if there are any groups of four consecutive even numbers.

It's not the most straightforward question, and even if you understand what it's asking the answer isn't exactly intuitive. Perhaps that explains why it's such a long debate.

Mario F. · 11-09-2009, 09:51 PM

Yup. I'm seeing your point.
Of course! You are right. I'm misunderstanding it.

Mario F. · 11-09-2009, 10:10 PM

And to prove your point I did resort to some code.

Only, since I'm teaching myself C#, I should stick to it...
Apologies not given

Code:

static void Main()
{
    Console.WriteLine("x = 1000 throws before no four consecutive numbers are all even");
    Console.WriteLine("Started at: {0} ", DateTime.Now);

    Random r = new Random();
    int num;
    byte nEvens = 0;
    long x = 0; // int64

    while(true)
    {
        x++;
        nEvens = 0;

        if(x % 1000000 == 0) // report every million sequences of 1000 throws
            Console.WriteLine("=> Still working at x = {0} => {1}", x, DateTime.Now);

        int i = 0;
        for(; i < 1000; i++)
        {
            num = r.Next(1, 1001); // [min, max[

            if(num % 2 == 0 && ++nEvens == 4) // short-circuit eval.
                break; // a sequence of 4 even numbers.
            else
            {
                if(num % 2 != 0)
                    nEvens = 0; // it's an odd. Reset.
            }
        }

        if(i == 1000)
            break; // no sequence of 4 even numbers!
    }

    Console.WriteLine("x = {0}", x);
    Console.WriteLine("Ended at: {0} ", DateTime.Now);

    Console.ReadLine();
}

Output until I ^C

Quote:

x = 1000 throws before no four consecutive numbers are all even
Started at: 10-11-2009 04:07:40
=> Still working at x = 1000000 => 10-11-2009 04:07:42
=> Still working at x = 2000000 => 10-11-2009 04:07:45
=> Still working at x = 3000000 => 10-11-2009 04:07:47
=> Still working at x = 4000000 => 10-11-2009 04:07:50
=> Still working at x = 5000000 => 10-11-2009 04:07:52
=> Still working at x = 6000000 => 10-11-2009 04:07:55
=> Still working at x = 7000000 => 10-11-2009 04:07:57
=> Still working at x = 8000000 => 10-11-2009 04:07:59
=> Still working at x = 9000000 => 10-11-2009 04:08:02
=> Still working at x = 10000000 => 10-11-2009 04:08:04
=> Still working at x = 11000000 => 10-11-2009 04:08:07
=> Still working at x = 12000000 => 10-11-2009 04:08:09
=> Still working at x = 13000000 => 10-11-2009 04:08:11
=> Still working at x = 14000000 => 10-11-2009 04:08:14
=> Still working at x = 15000000 => 10-11-2009 04:08:16
=> Still working at x = 16000000 => 10-11-2009 04:08:19
=> Still working at x = 17000000 => 10-11-2009 04:08:21
=> Still working at x = 18000000 => 10-11-2009 04:08:24
=> Still working at x = 19000000 => 10-11-2009 04:08:26

EDIT:
Removed the int[4] array and replaced it by a single int; "num". It was a leftover from a first approach and didn't remove it until now.

DavidP · 11-09-2009, 11:10 PM

So here is the real conclusion we have come to: professors really need to word their questions better!

11-09-2009, 01:14 PM	#17
Daved Registered User Join Date: Jan 2005 Posts: 7,252	>> Having no four consecutive numbers that are all even would be a good indicator that my random number generator is truly random. IMO, you're right about MK27's confusion, but the above is wrong. Depending on how you define it, you should expect around either 31 or 62 sequences of four consecutive even numbers when generating 1000 random numbers. Last edited by Daved; 11-09-2009 at 02:33 PM. Reason: bug in program meant wrong numbers in post
Daved is offline

11-09-2009, 02:30 PM	#20
Daved Registered User Join Date: Jan 2005 Posts: 7,252	>> if it didn't...would it be a sign of a bad random number generator? Yes. If the odds of it happening are somewhere between 1 in 10^7 and 1 in 10^27 (I believe my calculation and CornedBee's calculation bound the probability), then if it does happen it is a sign of a bad generator. If the odds of it not happening were more like 1 in 3, then you could ascribe it to just chance, but with such great odds it is fairly certain that the number is wrong. Also, my 125 to 500 number above was wrong. I had written a program, too, but there was a bug that caused the bad data. I think your results make sense (something that has a 1/16 probability will happen about 62 times out of 997 tries). I wonder how many times do you have to run the program before it ever gave a result of 0? And more importantly, if it gave a result of 0 while you were still testing it, you'd probably assume there was a bug.
Daved is offline

11-09-2009, 06:20 PM	#22
Daved Registered User Join Date: Jan 2005 Posts: 7,252	Could you clarify what you're saying Mario? The answer is d, because both b and c are correct. I'm not sure if you're disagreeing, or if we're just confused by the double and triple negatives.
Daved is offline

11-09-2009, 08:12 PM	#23
Mario F. (?<!re)tired Join Date: May 2006 Location: Portugal Posts: 5,654	I'm arguing the answer is b. (c) can't be correct. It states "no four consecutive numbers are all even". And yet, it was confirmed the likelihood of four numbers containing at least one odd number is 15/16. That's ~93% chance an odd number will show up in a sequence of 4 numbers. Next we get to the problem of how to calculate 4 number sequences. And I think we are accepting the "naive" approach too easily. It can't be correct because we are overlapping numbers and their odds. Let's get back to a smaller numbers: The dice. How many combinations of two numbers exist on 6 throws? 5. What's the odds of an odd number to show on 1 pair of numbers? 1/2. According to the "naive" approach this would mean 1/2^5 = 0.03. That's the odds of getting at least an odd number on every sequence of 2 throws after throwing the dice 6 times. That can't be correct. We know the odds of an odd number are 1/2. Instead, I argue all we need is to calculate the odds of an odd number to show in one pair of throws. That calculation is unbounded. We do not need to look at the total of throws. The odds will remain the same. Going back to the 1000 numbers and 1000 throws, what's the odds of an odd number to show in a sequence of 4 numbers? 15/16. And that's all we need to know. The odds aren't going to change because we throw 997 sequences of 4 numbers. The 15/16 calculation is the unbounded event. And all we need to know to reach the conclusion 93% chance of an odd number to show in a sequence of 4 numbers is a likely event. Thus this eliminates c. EDIT: Just for curiosity sake, help me if I'm getting this wrong: The odds for (b) I think are calculated as follows (using my dice example on the previous post): 1000! / 1000^1000 = 4.023e-433 The odds I believe are "bigger" than the number of stars in the universe __________________ Originally Posted by brewbuck: Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster. Last edited by Mario F.; 11-09-2009 at 08:33 PM.
Mario F. is offline

11-09-2009, 08:53 PM	#24
Daved Registered User Join Date: Jan 2005 Posts: 7,252	I think you're misunderstanding c. The question isn't whether there exist four even numbers in a single arbitrary sequence of four numbers. The question is whether there is exist four even numbers in any sequence of four numbers. So you're right that if you arbitrarily picked four consecutively generated numbers, there's a 93% chance that one will be odd, but that's not what the question is asking. It's asking you to go through the entire list of 1000 generated numbers and see if there are any groups of four consecutive even numbers. It's not the most straightforward question, and even if you understand what it's asking the answer isn't exactly intuitive. Perhaps that explains why it's such a long debate.
Daved is offline

11-09-2009, 09:51 PM	#25
Mario F. (?<!re)tired Join Date: May 2006 Location: Portugal Posts: 5,654	Yup. I'm seeing your point. Of course! You are right. I'm misunderstanding it. __________________ Originally Posted by brewbuck: Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.
Mario F. is offline

11-09-2009, 11:10 PM	#27
DavidP l'Anziano Join Date: Aug 2001 Posts: 2,627	So here is the real conclusion we have come to: professors really need to word their questions better! __________________ My Website "Circular logic is good because it is."
DavidP is offline

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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Computer Programmer Aptitude Battery Test (CPAB)	scotty101	General Discussions	40	02-22-2010 11:49 PM
Newbie needs help..	xpress urself	C++ Programming	3	07-26-2007 07:22 PM
A very long list of questions... maybe to long...	Ravens'sWrath	C Programming	16	05-16-2007 05:36 AM
My C++ test is COMING!!...	[Z-D]	C++ Programming	52	12-01-2006 08:02 PM
Bitwise Test Questions	Mister C	C Programming	9	11-27-2002 06:06 PM