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

[lazyfish]

I got 617. Here is the reasoning.

Assuming numbers are generated perfectly, you will get a linear distribution (i.e. not a normal distribution).

My strategy is to wait for n numbers to be generated before calling the next number that is greater than all the existing numbers the largest number.

After n number has been generated, the chances of having the highest number already being generated is n/1000. The chances of having (any of) the remaining numbers being greater than all the exisiting numbers is (1000-n)/(n+1). At 617, n/1000 = (1000-n)/(n+1).

Could be wrong, of course

 

[bellenuit]

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.

skyQuake. You are certainly getting hot.

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

That statement is correct, but it only has proved what we already know and that is that each number has a probability of 1 in 1000 of being the highest. But the simple strategy I gave (which is not the correct one) says to stop at the first number that is higher than all preceding numbers, not to just stop at any number at random.

So that strategy will give you the correct answer if the first number is not the highest number (999/1000) AND the second one is (1/999), which is as you say 1 in 1000 or .001

BUT, it will also give you the correct answer if the first number is not the highest (999/1000) AND the second number is not the highest (998/1000) AND the second number is lower than the first number (1/2) AND the third number is the highest (1/998).

(999*998*1*1) / (1000 *1000 *2*998) = .0004995

And as these are mutually exclusive events, the probability of either happening (which means you win) is now 0.0014995

BUT you can add to that number some more. It will also give you the correct answer if the first three numbers are not the highest and are generated so that the first is higher than the second which is higher than the third AND the fourth number is the highest. This again mutually exclusive event to the first two increases the chances still further. To fully evaluate the chances of that strategy working, you would need to follow the above calculations through till every mutually exclusive result has been evaluated and added together.

That's why I mentioned at the beginning that the problem can be approximately solved using basic probability theory, but an exact answer requires more than I know (I think it brings in Taylor Series etc).

 

[bellenuit]

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.

That would make it a very different problem. You would then be able to make assumptions about a number being highest based on its actual value, without reference to the other numbers. The reason a vast but unknown range is used is that the problem is dealing only with relative values, not absolute values.

 

[skyQuake]

I got 617. Here is the reasoning.

Assuming numbers are generated perfectly, you will get a linear distribution (i.e. not a normal distribution).

My strategy is to wait for n numbers to be generated before calling the next number that is greater than all the existing numbers the largest number.

After n number has been generated, the chances of having the highest number already being generated is n/1000.

The chances of having (any of) the remaining numbers being greater than all the exisiting numbers is (1000-n)/(n+1). At 617, n/1000 = (1000-n)/(n+1).

Could be wrong, of course

Shouldn't that be (1000-n)/1000 ? -

If n/1000 is the probability that the highest number is already generated, then (1000-n)/1000 [or 1-n/1000] would be the chance that one of the remaining numbers being higher than anything already generated.

 

[bellenuit]

I got 617. Here is the reasoning.

Assuming numbers are generated perfectly, you will get a linear distribution (i.e. not a normal distribution).

My strategy is to wait for n numbers to be generated before calling the next number that is greater than all the existing numbers the largest number.

After n number has been generated, the chances of having the highest number already being generated is n/1000. The chances of having (any of) the remaining numbers being greater than all the exisiting numbers is (1000-n)/(n+1). At 617, n/1000 = (1000-n)/(n+1).

Could be wrong, of course

Lazyfish.

You raised the bar a bit further and are on the right track.

Unfortunately I will be away from my PC until tomorrow and can't respond further till then

 

[geea]

42

Everyone knows that.

:

 

[Wysiwyg]

I got 617. Here is the reasoning.

Assuming numbers are generated perfectly, you will get a linear distribution (i.e. not a normal distribution).

My strategy is to wait for n numbers to be generated before calling the next number that is greater than all the existing numbers the largest number.

After n number has been generated, the chances of having the highest number already being generated is n/1000. The chances of having (any of) the remaining numbers being greater than all the exisiting numbers is (1000-n)/(n+1). At 617, n/1000 = (1000-n)/(n+1).

Could be wrong, of course

All good but how many goes at it do you want? Are you saying at the 617th number you would answer yes?

 

[Wysiwyg]

After n number has been generated, the chances of having the highest number already being generated is n/1000. The chances of having (any of) the remaining numbers being greater than all the exisiting numbers is (1000-n)/(n+1). At 617, n/1000 = (1000-n)/(n+1).

I don't think this is a hindsight exercise where you can go back after so many trials and errors.

 

[bellenuit]

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

Knobby. Even if the odds of the highest number being a positive number is 50%, just picking a number at random that is a positive number instead of just any number only increases your chances to 1 in 500, not 1 in 2.

However, I am not even sure that it is safe to say that there is a 50% chance of it being a positive number. I think any maths involving infinity is suss, as you can often get multiple conflicting outcomes (infinity + 1 = infinity + 2 would imply 1 = 2). You get similar issues when dividing by zero, that's why it is not allowed in maths and computers will spit a dummy when they encounter it. Let's stick to my amended statement to avoid these problems:

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.

 

[Wysiwyg]

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.

No logic here. Simply another assumption.

 

[bellenuit]

Restatement of problem with the infinity range removed:

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. 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 of the 1000 numbers printed)?

 

[Garpal Gumnut]

Bellenuit you are a very annoying person and will either increase or decrease the number of insomniacs on ASF, which is I feel a clue in solving this problem.

I was never good on probability but am learning.

gg

 

[brty]

By waiting until the first 500 numbers have been drawn,and then putting your name to the first number that is higher than any in the first 500, should give a probability of 1 in 4 of being correct.

The odds of the two highest numbers being in the second 500 numbers is 1 in 4.

The odds of the 3 highest numbers being in the second 500 numbers is 1 in 8.

The odds of the 4 highest numbers being in the second 500 numbers is 1 in 16.

etc, etc.

Therefore the odds of selecting the highest number by waiting for the first 500 to go by is 1 in 2 (that you haven't missed it) plus the odds of your selection being beaten by a higher number later on, also ~1 in 2.

There is a 50% chance that you chose no number (by waiting for 500 to go by), so the chance of your number being correct if you did select from the second 500 is also 50%.

brty

PS, However I don't believe in random, just humans inability to correctly predict the odds.

 

[bellenuit]

By waiting until the first 500 numbers have been drawn,and then putting your name to the first number that is higher than any in the first 500, should give a probability of 1 in 4 of being correct.

brty. A good strategy, but not the optimum strategy. BTW, your probability of being correct with your strategy is better than 1 in 4. Quite an advance from 1 in 1000, which is most people's reaction, including mine, when first confronted with the problem.

I will put the answer up tomorrow evening (Monday WST), if it hasn't been solved by then.

 

[Wysiwyg]

sequentially generates 1000 perfectly random numbers

There appears to be a contradiction with sequential and random?

Sequential = a continuous or connected series

Random = a haphazard course; without definite aim, direction, rule, or method

Also the question needs to state that many attempts can be made through trial and error

There seems to be a vital requirement that has been omitted and because of this I can see the answer is going to be full of holes

 

[Sdajii]

There appears to be a contradiction with sequential and random?

Sequential = a continuous or connected series

Random = a haphazard course; without definite aim, direction, rule, or method

Also the question needs to state that many attempts can be made through trial and error

There seems to be a vital requirement that has been omitted and because of this I can see the answer is going to be full of holes

The sequentially bit just means the numbers are drawn one after another. The sequence is 1, 2, 3, 4 etc etc up to 1,000 (as opposed to all being selected at once and being unordered). The value of each number in the sequence is the random part.

You can make as many attempts as you like, and on each particular trial you might end up with different odds at different points within that trial, but there is one optimal strategy (which I admit, I have no idea of; my best attempt was a similar idea to brty's, which apparently is not ideal). Whatever that optimal strategy is, it will have a certain probability of success which you can calculate before the trial begins. Obviously, once a trial is part way through, the odds of success will have changed, but that isn't relevant to the question being asked. The only problem I saw with the original question was that it wrongly assumed you could randomly pick finite numbers within infinite boundaries, but that has been fixed. If it wasn't close to 2am I wouldn't be so tired and I would probably have more hope of working it out, but I suspect I would still fail.

I'm looking forward to seeing the solution!

 

[Wysiwyg]

By waiting until the first 500 numbers have been drawn,and then putting your name to the first number that is higher than any in the first 500, should give a probability of 1 in 4 of being correct.
brty

PS, However I don't believe in random, just humans inability to correctly predict the odds.

That is an assumption there will be a number higher after the first 500.

The second 500 numbers could all be lower numbers than the highest in the first 500 numbers. So you could still wait until the 1000th number before knowing the highest number was in the first 500.

Where does 1 in 4 odds come from you just said no to 500 numbers while the highest number could have been in there but you don't know and you won't know until all numbers are drawn.

 

[Wysiwyg]

The sequentially bit just means the numbers are drawn one after another. The sequence is 1, 2, 3, 4 etc etc up to 1,000 (as opposed to all being selected at once and being unordered). The value of each number in the sequence is the random part.
I'm looking forward to seeing the solution!

Well it would be more accurate and better English to say ...

You have a simple computer program that generates 1000 perfectly random numbers within a finite, but vast range.

This sentence explains the next step in the operation ...

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?".

 

[bellenuit]

Well it would be more accurate and better English to say ...

You have a simple computer program that generates 1000 perfectly random numbers within a finite, but vast range.

This sentence explains the next step in the operation ...

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?".

Wysiwyg,

I don't agree that the question as formulated is confusing...

You said there was a contradiction between sequential and random. That would be the case if I said it generates sequential random numbers, but I said it sequentially generates random numbers. There is no contradiction there.

You have a simple computer program that sequentially generates 1000 perfectly random numbers within a finite, but vast range.

Regarding your question as to where brty got the 1 in 4 from. If you just note the highest number in the first 500 (responding No to all of them) and then you pick the first number that is higher than that, you will have (at least) a 1 in 4 chance of being correct.

You would expect that over many attempts, 50% of the time the 2nd highest number will be in the first 500 and 50% of the time the highest number will NOT be in the first 500. If both of those events occur together, that strategy will give a successful outcome. The odds of both occurring together are 1/2 X 1/2 or 1 in 4. So you know that strategy has a (at least) 1 in 4 chance of giving you the highest number.

 

[Wysiwyg]

Wysiwyg,

I don't agree that the question as formulated is confusing...

You said there was a contradiction between sequential and random. That would be the case if I said it generates sequential random numbers, but I said it sequentially generates random numbers. There is no contradiction there.

Okay.

Regarding your question as to where brty got the 1 in 4 from. If you just note the highest number in the first 500 (responding No to all of them) and then you pick the first number that is higher than that, you will have (at least) a 1 in 4 chance of being correct.

Bellenuit, any formula works upon the knowing of the numbers. The likelihood of answering yes correctly the first time is 1 in 1000. Everyone seems to be collecting the data and working it out. It is easy to eliminate numbers and increase the odds if the numbers are known. That is not part of the stated operation.