The Random Number Generator - One of the best Maths problems ever IMO

[bellenuit]

This is a maths problems I came across a very long time ago and at the time I thought it one of the best I ever heard. Strangely enough I have never come across it again.

You can get an approximate answer with very basic probability theory, but to get the exact answer requires a better knowledge of maths than I have. Perhaps some of you out there might be able to work out the "perfect" answer. But just using basic probability theory you get a very interesting result, that is just a percent or two away from the exact answer, but nevertheless an answer that most would at first find incredible.

You have a simple computer program that sequentially generates 1000 perfectly random numbers in the range minus to plus infinity. After generating a random number it displays it on the screen and then asks this question: "Of the 1000 numbers being generated in this series, is this number the highest, Yes or No?".

If you answer No, it will print the number it displayed on the output listing so that you have a record of what the number was for whatever calculations you might want to do. It will then generate and display another random number and again ask the same question. It continues doing this until you answer Yes or it has generated and printed 1000 random numbers.

However, if you answer Yes, it will print the number on the output listing and print your name beside it. Then, without stopping, it will generate and print the remaining random numbers until the series of 1000 has been finished.

The question is: Assuming you are a perfect logician and will try and maximise your chances of identifying the highest number, what is your chance of doing so (i.e. that your name will be printed beside the highest number)?

There are no tricks to this question. Don't get hung up about the practicality of printing or assimilating what could be numbers with billions of digits. The reason the range is minus to plus infinity is so that there is no information from the number itself when viewed in isolation (otherwise a number generated that was close to a finite upper boundary would be a good candidate to say Yes to). Also, the computer program is not trying to beat you. It just produces perfectly random numbers and performs the simple tasks indicated.

Remember you can only say Yes against the current number. You cannot indicate that a previous to the current number was the highest.

If you have heard the problem before and know the answer, perhaps wait a bit so that others can give it a try.

 

[Stan 101]

I'd say 1 in 1000 minus the number of numbers you have already rejected as not being the highest number, if I understand the question correctly.



cheers,

 

[bellenuit]

I'd say 1 in 1000 minus the number of numbers you have already rejected as not being the highest number, if I understand the question correctly.



cheers,

Stan, I'm not sure I understand that.

Your chances are clearly 1 in 1000 if you have no strategy whatsoever and simply randomly stop at any number and answer Yes to it. When you say "I'd say 1 in 1000 minus the number of numbers you have already rejected as not being the highest number" are you suggesting less than 1 in 1000?

Do you mean that the chances improve as you go along, so that if you haven't said Yes up until the last number is generated that you now have a 100% chance being right by selecting the final number? That clearly isn't the case.

Remember you are to assume you are a perfect logician and will try and maximise your chances of identifying the highest number. So depending on what strategy you adopt, your chances will be fixed for that strategy. For the sake of example let's say the optimum strategy has a 1 in 100 chance of being correct. Then what I am saying is that if you adopt that strategy, you will get the highest number on average of 1 in 100 attempts.

 

[beerwm]

Once the first number is generated, wouldnt that be the highest - as you only have 1 number to choose from? answer 'yes'

therefore generating 999 random numbers without stopping.

 

[skyQuake]

Since there are no limits to the random number generator you will never be sure whether the number is "high" or "low"

eg. If you get 25 as first number. There are infinity numbers above that and below that. Its as good as 0
If you get -1trillion. There are still infinity numbers above and below that.
The numbers generated will not form a standard distribution so thats down the drain.
So to the logician, each number is effectively 0 till the last number comes out.

As such, a logician will be unable to decide whether the number is the highest till the LAST number comes out. (Because each number revealed has an infinite amount of numbers above and below it)

The logician can only make the choice at the last number. The probability that this number is the highest number is 1 in 1000.

I think thats right

EDIT: Well since you said a 'simple' computer program, integer overflow will be at +-4.29 Billion; So that would probably make decision making easier

 

[2020hindsight]

Since there are no limits to the random number generator you will never be sure whether the number is "high" or "low"

eg. If you get 25 as first number. There are infinity numbers above that and below that. Its as good as 0
If you get -1trillion. There are still infinity numbers above and below that.
The numbers generated will not form a standard distribution so thats down the drain.
So to the logician, each number is effectively 0 till the last number comes out.

As such, a logician will be unable to decide whether the number is the highest till the LAST number comes out. (Because each number revealed has an infinite amount of numbers above and below it)

The logician can only make the choice at the last number. The probability that this number is the highest number is 1 in 1000.

I think thats right

EDIT: Well since you said a 'simple' computer program, integer overflow will be at +-4.29 Billion; So that would probably make decision making easier

lol
...
like ... which is bigger? infinity minus 1, or infinity minus 2 ? - or are they the same?

PS say bellenuit, is it ok to use a range of say +/- 1 million? why does it have to be +/- infinity?

 

[bloomy88]

Since there are no limits to the random number generator you will never be sure whether the number is "high" or "low"

eg. If you get 25 as first number. There are infinity numbers above that and below that. Its as good as 0
If you get -1trillion. There are still infinity numbers above and below that.
The numbers generated will not form a standard distribution so thats down the drain.

I agree with you up until your point there

If you wait until the last number you will have one number that is currently the 'highest' of the all the 999 numbers you have so far generated.

Since there are infinite numbers either side of that number you theoretically have a 50-50 chance of being higher or lower than the highest number...

Therefore, I you wait until the the last number it has a 50% chance of being below the current highest number (in which case you lose) but also a 50% chance of being above the highest number and therefore you say 'YES" and you win the game.

50-50 chance is the best that you would get...

Is that right bellenuit?
Cheers

 

[bellenuit]

Once the first number is generated, wouldnt that be the highest - as you only have 1 number to choose from? answer 'yes'

therefore generating 999 random numbers without stopping.

No. You must have indicated Yes to the highest number of all the 1000 numbers generated. The printout at the end will show 1000 numbers. If you said No to every number as it was generated, you obviously have lost as there will be no Yes on the list. Otherwise there will be just one Yes on the output list. Those preceding the number with the Yes are those you viewed and responded No to. Those following the number with the Yes are those that were then generated to make the series of 1000 complete. Your Yes must be the highest number of all those 1000 numbers listed, not just those that have gone before.

 

[Lone Wolf]

I'd pick the second number.

Here's my (flawed) logic.

In the end there will be 1000 numbers generated. You are trying to pick the highest of the 1000 numbers.

The first number comes up:
Chance of number 1 being highest = 1 / 1000 = 0.1%
Chance of having already discarded the highest number is 0 / 1000 = 0%
Decision:
The chance of this being the highest is low enough for me to say no.

The second number comes up:
Chance of number 2 being highest = 1 / 999 = 0.1001%
Chance of having already discarded the highest number is 1 / 1000 = 0.1%
Decision:
The probability that this number is the highest is greater than the first number. Also, the probability that this is the correct number is greater than the probability that I've already discarded the highest number. I choose this one.

(just to see)
The third number comes up:
Chance of number 3 being highest = 1 / 998 = 0.1002%
Chance of having already discarded the highest number is 2 / 1000 = 0.2%
Decision:
The chance that I've already discarded the highest number is greater than the chance of this being the correct number. Should have taken number 2.

I've said it... but I don't like it. If you compare the second number to the first, by discarding the first number I have increased my probability of being correct by 0.0001% in exchange for a 0.1% chance that I'm already wrong. That doesn't sound like a good deal to me. But the way my mind works, if I reach into a lucky dip of 1000 tickets, the chance of me pulling out the winning ticket is so small that I'd never take the first one I touch. I have never won a lucky dip.

 

[bellenuit]

The logician can only make the choice at the last number. The probability that this number is the highest number is 1 in 1000.

skyQuake. But 1 in a 1000 is exactly the same odds as if you stopped at any number with no strategy whatsoever and simply said Yes without even looking at it. Lets say you were to adopt the very simple strategy of "I will say Yes to first number generated that is higher than any of the preceding numbers generated (So if 8, 45 comes out you say Yes to the second number 45 or if 8, 2, 67 comes out you say Yes to the third number 67). That strategy would certainly have a better chance of being correct than simply saying Yes to any number at random, which has just 1 in 1000 of being correct.

As an aside, 1 in 1000 is not the worst chance. You could obviously have a strategy that will give you a lesser chance than that of winning. For instance, if the strategy was to stop at the first number that is lower than the preceding number then you have a zero chance of winning.

 

[bellenuit]

lol
PS say bellenuit, is it ok to use a range of say +/- 1 million? why does it have to be +/- infinity?

2020. No, because you would then know what a large number is without reference to what has been generated so far. skyQuake was spot on in regards to that. Minus to Plus Infinity gives you no sense of what a big number is, as there are an infinite number of numbers above every other number. But if the max was + 1 million, then if the number 1 million was generated you would be safe to say Yes to that number without even caring what other numbers were listed.

I don't want to overcomplicate the question, but you could use a lesser range provided the strategy didn't rely on comparing the number to the top of the range. I wrote a computer program one time to verify the answer by seeing if it got it correct approximately that number of times (It did). In the program I used a lesser range as that was all the computer was capable of.

 

[Wysiwyg]

I'd say 1 in 1000 minus the number of numbers you have already rejected as not being the highest number, if I understand the question correctly.
cheers,

I think, Stan 101, the chance of 1 in 1000 would remain the same with every attempt. A higher or lower number than the previous number may be higher or lower than the remaining numbers at every attempt. Process of elimination is not possible.

 

[skyQuake]

bellenuit:

Yeh the odds depend on the strategy. The logician will do the logical thing i explained above; even though the odds are exactly the same.

In ur example saying yes to the next highest number generated would be same as 1:1000 odds.

Eg. 8, 45, etc...

if you say yes @ 45, the probability that this is the highest number is 1 in 999
But that ignores the risk you take by not picking number 1 as the highest number. (1 in 1000) ie. That 8 could have been followed by numbers ALL lower than it.

So probability no1 is greatest P(1)=1/1000 (probability no1 is not the greatest = 999/1000)
Probability no2 is greatest P(2) = 1/999 * 999/1000 = 1/1000 (probability no. 2 is the largest number times the probability that no.1 isnt the largest number)
etc

So thus IMO, 1/1000 is the best u can do. But bloomy sounds perfectly correct too lol.

Lonewolf: You need to multiple the probabilities as they are sequential events.

 

[bellenuit]

I agree with you up until your point there

If you wait until the last number you will have one number that is currently the 'highest' of the all the 999 numbers you have so far generated.

Since there are infinite numbers either side of that number you theoretically have a 50-50 chance of being higher or lower than the highest number...

Therefore, I you wait until the the last number it has a 50% chance of being below the current highest number (in which case you lose) but also a 50% chance of being above the highest number and therefore you say 'YES" and you win the game.

50-50 chance is the best that you would get...

Is that right bellenuit?
Cheers

Bloomy. Now you have put me into a quandary. Unlike what I said in my previous post, perhaps I shouldn't have used plus or minus infinity as mathematics becomes fuzzy when dealing with the infinities.

You answer is very logical and though it would appear to be correct to say that there is a 50 - 50 chance of the last being higher than the preceding highest, we know that since it is a perfect random number generator, each number has a 1 in 1000 chance of being the highest and the last number is no different from any other.

Perhaps, to remove the anomalies of dealing with infinities, I should rephrase the first line of the problem as follows:

You have a simple computer program that sequentially generates 1000 perfectly random numbers within a finite, but vast range. You do not know what the range is, other than that it is finite.

That should remove the infinity issues while at the same time giving you no information as to what a large number is.

 

[bellenuit]

Here's my (flawed) logic.

Lone Wolf.

Not correct, but looking in the right direction

 

[2020hindsight]

2020. No, because you would then know what a large number is without reference to what has been generated so far.

thanks for that - I'll think about it - probably for a week or so lol ( got a busy one ahead of me) cheers.

PS I just found it interesting that you glossed over the "simple computer program" with it's random numbers between +/- infinity, lol not sure I've seen such a program
cheers

 

[Knobby22]

Range - infinity to + infinity, 1000 numbers.

I think the answer intuitively is 50.4%. I really should do the maths and will have a go at it when I am on holiday next week.

Here's the logic. If you have 1000 random numbers then on average 50% will be above zero so you would say no to any number below zero. Instantly you can increase the odds of being right to above 50%. Probability of being right is 1/2 + 1/500 so if you said yes based on this the probability is 50.2%

Now what is difficult is that the number could be anywhere from 0 to infinity that needs to beat you and infinity is obviously a large number. You can probably state that you only chose yes to a number if it is sufficiently large you may be able to logically argue that you can approach a probability of have a 2/500 chance of being right. i.e. 50.4%.

Am I close bellenuit??

 

[bloomy88]

Bloomy. Now you have put me into a quandary. Unlike what I said in my previous post, perhaps I shouldn't have used plus or minus infinity as mathematics becomes fuzzy when dealing with the infinities.

You answer is very logical and though it would appear to be correct to say that there is a 50 - 50 chance of the last being higher than the preceding highest, we know that since it is a perfect random number generator, each number has a 1 in 1000 chance of being the highest and the last number is no different from any other.

Perhaps, to remove the anomalies of dealing with infinities, I should rephrase the first line of the problem as follows:

You have a simple computer program that sequentially generates 1000 perfectly random numbers within a finite, but vast range. You do not know what the range is, other than that it is finite.

That should remove the infinity issues while at the same time giving you no information as to what a large number is.

Haha cheers, ill have to think again now...
Look forward to seeing the correct answer

 

[skyQuake]

Finite range? Might as well make it +-1000, and 10 repetitions.
Now someone with monte carl please test it out

The difference between infinite and finite range just makes it easier to define a high number.

 

[Wysiwyg]

I think, Stan 101, the chance of 1 in 1000 would remain the same with every attempt. A higher or lower number than the previous number may be higher or lower than the remaining numbers at every attempt. Process of elimination is not possible.

Just a further thought and based purely on assumption , if the first number presented by the computer for a yes/no answer is not the highest number (of the 1000 generated) and the second number presented is higher than the first number it would lower the chances and so on if each successive number was higher than the previous. That is a possible scenario.

The problem still exists after the first drawn number at to when to say yes. Assuming the first number is not the highest number.