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



## bellenuit (14 November 2009)

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 (14 November 2009)

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 (14 November 2009)

Stan 101 said:


> 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 (14 November 2009)

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 (14 November 2009)

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 (14 November 2009)

skyQuake said:


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




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 (14 November 2009)

skyQuake said:


> 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 (14 November 2009)

beerwm said:


> 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 (14 November 2009)

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 (14 November 2009)

skyQuake said:


> 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 (14 November 2009)

2020hindsight said:


> 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 (14 November 2009)

Stan 101 said:


> 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 (14 November 2009)

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 (14 November 2009)

bloomy88 said:


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




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 (14 November 2009)

Lone Wolf said:


> Here's my (flawed) logic.




Lone Wolf.

Not correct, but looking in the right direction


----------



## 2020hindsight (14 November 2009)

bellenuit said:


> 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 (14 November 2009)

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 (14 November 2009)

bellenuit said:


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




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


----------



## skyQuake (14 November 2009)

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 (14 November 2009)

Wysiwyg said:


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


----------



## lazyfish (14 November 2009)

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 (14 November 2009)

skyQuake said:


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




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 (14 November 2009)

skyQuake said:


> 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 (14 November 2009)

lazyfish said:


> I got 617. Here is the reasoning.
> 
> Assuming numbers are generated perfectly, you will get a linear distribution (i.e. not a normal distribution).
> 
> ...




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 (14 November 2009)

lazyfish said:


> I got 617. Here is the reasoning.
> 
> Assuming numbers are generated perfectly, you will get a linear distribution (i.e. not a normal distribution).
> 
> ...




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 (14 November 2009)

42

Everyone knows that.

:


----------



## Wysiwyg (14 November 2009)

lazyfish said:


> I got 617. Here is the reasoning.
> 
> Assuming numbers are generated perfectly, you will get a linear distribution (i.e. not a normal distribution).
> 
> ...



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


----------



## Wysiwyg (14 November 2009)

> 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 (14 November 2009)

Knobby22 said:


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




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 (14 November 2009)

> *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 (14 November 2009)

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 (14 November 2009)

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 (15 November 2009)

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 (16 November 2009)

brty said:


> 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 (16 November 2009)

> *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 (16 November 2009)

Wysiwyg said:


> There appears to be a contradiction with sequential and random?
> 
> Sequential = a continuous or connected series
> 
> ...




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 (16 November 2009)

brty said:


> 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 (16 November 2009)

Sdajii said:


> 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 (16 November 2009)

Wysiwyg said:


> 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. *_
> 
> ...




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 (16 November 2009)

bellenuit said:


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


----------



## bellenuit (16 November 2009)

Wysiwyg said:


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




But you are not collecting the data and working it out, otherwise you would be right every time. You are allowing 500 numbers to pass answering No to each one, but taking a note of the highest number within that 500. Then you say Yes when the computer generates a number that is higher than that. The probability is that you will be right at least 25% of the time if you use that strategy.

As an additional hint for everyone. You should ask yourself is 500 the optimum number of random numbers to let pass before making the decision. If you only let 1/5 of the random numbers pass, or 1/4 or 1/3 or perhaps more than half, 2/3 say, would your chances improve using the same strategy.


----------



## Wysiwyg (16 November 2009)

bellenuit said:


> But you are not collecting the data and working it out, otherwise you would be right every time. You are allowing 500 numbers to pass answering No to each one, but taking a note of the highest number within that 500.



 Is that not collecting data? You state "taking a note of the highest number within that 500".


----------



## skyQuake (16 November 2009)

I think i've figured it out, the optimal number to choose depends on how big the number is *at what point in the sequence.*

-Let _H_ denote the highest number so far in the series.
-Let the range of finite numbers be limited to _x_ and _-x_ (giving a range of 2_x_)
-Let _n_ denote how many numbers have already been drawn.

The *relative position* of the current highest number in the series is thus:
_x_-_H_ (ie. how many can possibly be ABOVE the current high)

Thus the probability that a higer number will not be drawn on the next draw is:
(_x_-_H_)/(2_x_) 
ie. Number of possible higher integers divided by the total amount of possible integers.

Consequently, assuming we have drawn _n_ numbers, we have (1000-_n_) numbers left to draw.

Thus the probability that no higher number will occur in the rest of the draw is given by:

[(_x_-_H_)/(2_x_)]^(1000-_n_) 


As such, it is best to wait till close to the end of the series to make the choice. H = say 0.8x early on at say n=100 would yield a very low probability that this is the highest possible number and would not be picked. But if H increases significantly and/or n approaches 1000, the probability that 'no higher number would occur' increases and you would be more likely to pick...


----------



## bellenuit (16 November 2009)

Wysiwyg said:


> Is that not collecting data? You state "taking a note of the highest number within that 500".




Who said you had to forget each number once you said No to it?  Of course the chances will always be 1 in 1000 if you simply press Yes at any number without any system or method behind your decision. But the question as stated implies you adopt an optimum strategy, and such a strategy will usually involve basing your decision for each number on the information you have gathered from the numbers that have gone before. For example, you would hardly say Yes to a number that is less than the one immediately preceding it.  

This is directly from the text of the problem.....

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

and also....

_*Assuming you are a perfect logician and will try and maximise your chances of identifying the highest number.....*_

that implies you will apply a strategic approach to trying to pick the highest number


----------



## Wysiwyg (16 November 2009)

skyQuake said:


> I think i've figured it out, the optimal number to choose depends on how big the number is *at what point in the sequence.*
> 
> -Let _H_ denote the highest number so far in the series.
> -Let the range of finite numbers be limited to _x_ and _-x_ (giving a range of 2_x_)
> ...




Okay here is a simple "test" for this formula. I will present five numbers from one thousand random numbers my computer has generated. Please answer yes or no to each number. I know what the highest number is in the 1000 so good luck.

192821239	
-616178961	
789673834	
680667335
998670174


----------



## skc (16 November 2009)

I think we are missing the probability enhancement coming from saying yes only if the number on screen is higher than all the numbers already showned. 

(A). Pass up on first n numbers. The probability you are wrong would be n/1000.

(B). Look at number (n+1), if it is the highest number so far, you answer yes. The chance of that being correct is 1/(1000-n). But you only need to make this guess 50% of the time (assuming a range so vast that the chance of the next number being higher or lower is simply 50%).

(C). The remaining 50%, number (n+1) is lower than the highest number so far. You are guaranteed to make the correct call by saying no. 

So...the probability of us being right is some sort of product or sum of the 3 terms above. And then we need to solve for the optimal n.

I have a hunch that the optimal n may in fact simply be 1, but I am struggling to put the correct formula together...


----------



## Robb (16 November 2009)

skyQuake said:


> -Let the range of finite numbers be limited to _x_ and _-x_ (giving a range of 2_x_)




You cannot use this, as the range is unknown/infinite to the person answering yes or no. ie. We could assume that a single observation of a number generted is Y, so it could be said that Y is continuously uniformly distributed, Y~U(-X,X). Ie. Y doesn't have to take an integer value?

So you would need to use some form of order statistic distribution, Y(n): max(Y1,...Yn)
http://en.wikipedia.org/wiki/Order_statistic#The_order_statistics_of_the_uniform_distribution

I just had a stat exam this morning, and not getting where to take this, i assume this is the more 'advanced' way of solving it? or Im looking at it completly from the wrong angle?


----------



## skyQuake (16 November 2009)

Wysiwyg said:


> Okay here is a simple "test" for this formula. I will present five numbers from one thousand random numbers my computer has generated. Please answer yes or no to each number. I know what the highest number is in the 1000 so good luck.
> 
> 192821239
> -616178961
> ...




Lol can't do; The equation needs the limits. If limits not specified, its as good as finite. What can be done is say this high number is 85% of Limit.
Thanks for the link, reading up on it.



Robb said:


> You cannot use this, as the range is unknown/infinite to the person answering yes or no. ie. We could assume that a single observation of a number generted is Y, so it could be said that Y is continuously uniformly distributed, Y~U(-X,X). Ie. Y doesn't have to take an integer value?
> 
> So you would need to use some form of order statistic distribution, Y(n): max(Y1,...Yn)
> http://en.wikipedia.org/wiki/Order_statistic#The_order_statistics_of_the_uniform_distribution
> ...




Oh i was doing this under the assumption that bellenuit had changed it to a finite range.


----------



## bellenuit (16 November 2009)

skyQuake said:


> Lol can't do; The equation needs the limits. If limits not specified, its as good as finite. What can be done is say this high number is 85% of Limit.
> Thanks for the link, reading up on it.
> 
> 
> ...




Yes. After there was some anomalies encountered when infinities were involved in the maths, the range of random numbers was changed to a vast but unknown finite range. 

*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 (16 November 2009)

skyQuake said:


> Lol can't do; The equation needs the limits. If limits not specified, its as good as finite. What can be done is say this high number is 85% of Limit.



Okay thanks. Saying yes to a higher number than previous numbers narrows the chances.  :


----------



## Robb (16 November 2009)

bellenuit said:


> Yes. After there was some anomalies encountered when infinities were involved in the maths, the range of random numbers was changed to a vast but unknown finite range.
> 
> *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.*




So discrete random iid numbers then.
Well, its a conditional probability; let Y be the observed value, so Y(1) is the first observation, Y(2) is the second etc.
So the Probability that an observation is the maximum is
P(Y(1))=1/1000
P(Y(2))=1/999 given (Y(2)>Y(2)) otherwise 0
P(Y(3))=1/998 given (Y(3)>Y(1),Y(2)) otherwise 0.
....
P(Y(n))=1/(1001-n) given (Y(n)>Y(1),...,Y(n-1)) otherwise 0

hmmm... good question


----------



## schnootle (16 November 2009)

Very famous problem this one. I haven't heard it formulated this way, i believe you would be called a misogynist if you gave it its original name.

I won't let be a spoiler, but am happy to give hints for people that are having fun.


----------



## bellenuit (16 November 2009)

schnootle said:


> Very famous problem this one. I haven't heard it formulated this way, i believe you would be called a misogynist if you gave it its original name.
> 
> I won't let be a spoiler, but am happy to give hints for people that are having fun.




It's at least 35 years since I first heard this problem. It was originally formulated as numbers written on the backs of pieces of paper that were turned upside down. You were to turn a paper and nominate if that was the highest number on all the pieces of paper, including those unturned obviously. I thought I would just change the setting. 

I plan to put the solution up tonight sometime. I hope my logic is correct as I have had to recreate what I think is the correct strategy from memory. You can correct me if I'm wrong.


----------



## schnootle (16 November 2009)

bellenuit said:


> It's at least 35 years since I first heard this problem. It was originally formulated as numbers written on the backs of pieces of paper that were turned upside down. You were to turn a paper and nominate if that was the highest number on all the pieces of paper, including those unturned obviously. I thought I would just change the setting.
> 
> I plan to put the solution up tonight sometime. I hope my logic is correct as I have had to recreate what I think is the correct strategy from memory. You can correct me if I'm wrong.




You have done pretty well if you haven't seen the problem for 35 years. I will direct people to some more information when you have put up your solution.


----------



## 2020hindsight (16 November 2009)

well you're right bellenuit - it is a ripper. 
I look forward to the answer. 
THe following is not mathematically helpful whatsoever.  Just some scribling I've been doing whilst flying around the place. 

I started trying to simplify it.
That at some point of time you would have turned n numbers.
the chance of the largest in that sample would be n/1000.
then the chance of the largest being the most recently turned in that sample would be 1/n.

So - surprise surprise, the chances of the largest being the most recently turned would be (n/1000) x (1/n) which simplifies to 1/1000 lol - ...  (0.1%) 

doh ...  big deal I found myself saying.

Not sure how you take account of the fact that , in the other cases (of these) where the most recent wasn't the largest   ( = (1- 1/n) (n/1000) ) - that after "n" you keep turning , hoping that the largest is not in the disclosed numbers.

I thought 67% was a bit too much risk that you'd blown it already. 

Pure guesswork ( compare betting on one column of the roulette wheel) , my gut feel is that it is about the 33% mark,  that you turn up 333 of them, then continue until (as others have said) you get a bigger number than all the numbers to date = the biggest in the upturned pack. THen stop.  

That way ( stopping at the first opportunity after the third point) you only have 1/3 chance that you've blown it and gone too far.  And you could well get the largest  number/card at around the 50% mark - not that there's any logical reason it has to be in the middle of the pack, lol.

Sorry very unmathematical here, just playing around with numbers and thoughts - and approximations.  ( the same way I'd play roulette - if I were to get real pissed and play roulette that is ) 

PS But I wouldn't be surprised if it was after the second number as was suggested way back there somewhere. 

But it has been real challenging and fun in a masochistic way.  Sadomasochism - never have to say  you're sorry.


----------



## waza1960 (16 November 2009)

Lets just ask Howard Bandy .I reckon he will be able to answer correctly within seconds with 98% probability.


----------



## 2020hindsight (16 November 2009)

PS 
after this you're gonna have to give us the good oil on playing that game where people hold all those golden suitcases  - "Deal or No Deal:" I think it's called


----------



## schnootle (16 November 2009)

2020hindsight said:


> Sorry very unmathematical here, just playing around with numbers and thoughts - and approximations.  ( the same way I'd play roulette - if I were to get real pissed and play roulette that is )




Your guessing is better than you give yourself credit for


----------



## bellenuit (16 November 2009)

People seem to be now on the right track, so I will give the solution as best as I can. brty was close to the mark when he/she posted _"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"_ That is the strategy, but the number to pass over is not the optimum. 2020 was closer when he/she said _" my gut feel is that it is about the 33% mark, that you turn up 333 of them, then continue until (as others have said) you get a bigger number than all the numbers to date = the biggest in the upturned pack"._

As I mentioned at the very beginning _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_. In fact my maths has improved enormously over the last day or so when I started using the Wolfram Alpha computational engine, but more about that below. 

If you don't want to get deeply into the maths, you can derive the optimum fraction to use by evaluating for easy fractions like 1/5, 1/4, 1/3, 1/2 etc. and seeing which if these gives the greatest chance of being right. If you do this, you will find that 1/3 gives the greatest chance. Later I will show how to work out the optimum fraction using more advanced mathematics. 

So your strategy is to answer No to the first 333 numbers generated (noting the highest number among these) and then say Yes to the first number (if any) that is higher than this. This will give you the greatest chance of success. This is how you work out the probability of being right....

This strategy will give you the correct answer if the 2nd highest number is in the first third (1/3 chance) AND the highest number is not in the first third (2/3 chance). Thus you will be correct 2/9 or 22% of the time (at least).

But it will also give you the correct answer if the 3rd highest number is in the first third (1/3 chance) AND the highest and second highest numbers are not in the first third (2/3 X 2/3 chance) AND the highest number comes up before the second highest number (1/2 chance). This comes to 2/27 or 0.074 or 7.4%. Since this is a mutually exclusive result to the first, both are potential outcomes, so the chances of either happening are 29.4%.

You would also be successful if the 4th highest number is in the first third (1/3) AND the first, second and third highest are not in the first third (2/3 X 2/3 X2/3) AND the highest number is generated before the second or third highest (1/3). This is 8/243 or .033 or 3.3%. Again, as this is a mutually exclusive result, the chances of any one of these three outcomes occurring, which would give the correct result, are now up to 32.7%.

So this is almost a one in three chance, but it will increase slightly more each time you evaluate and include additional possible successful outcomes. The 667th term will be the highest you can go and this will be when the 667th highest number is in the first third AND all 666 higher numbers are not in the first 1/3 AND the highest number comes before the other 665. However, evaluating beyond a few terms is pointless, as each additional term adds proportionally less and less to the final result.

So as an approximation, the chances of success using this strategy is about 1 in 3.

Now for the heavy stuff. If any of you are not aware of the computational engine Wolfram Alpha, I urge you to go to the website http://www.wolframalpha.com/ and play around with it. It will blow your mind when you see its capabilities. There is an introductory video there that is worth watching. I will be using that website in this section.

In the advanced solution instead of using 1/3 as the fraction to turn, you need to first determine what actual fraction will yield the highest chances of success. 1/3 is close, but not the optimum fraction. 

Lets say this fraction is n, where n is between 0 and 1.

So following the above basic probability logic, using the same strategy, but this time using n rather than 1/3, we get:

This strategy will give you the correct answer if the 2nd highest number is in the first n of the generated numbers (n chance) AND the highest number is not in the first n of the generated numbers (1-n chance). Thus your chance of success is n(1-n) at least.

But it will also give you the correct answer if the 3rd highest number is in the first n of the generated numbers (n chance) AND the highest and second highest numbers are not in the first n of the generated numbers ((1-n)(1-n)) AND the highest number comes up before the second highest number (1/2). The chance of this happening is 1/2*n*(1-n)^2. Since this is a mutually exclusive result to the first, both are potential outcomes, so the chances of either happening are n(1-n) + 1/2*n*(1-n)^2.

You would also be successful if the 4th highest number is in the first n of the generated numbers (n chance) AND the first, second and third highest are not in the first n of the generated numbers ((1-n)(1-n)(1-n)) AND the highest number is generated before the second or third highest (1/3). This is 1/3*n*(1-n)^3. Again, as this is a mutually exclusive result, the chances of any one of these three outcomes occurring, each of which would each give the correct result, are now n(1-n) + 1/2*n*(1-n)^2 + 1/3*n*(1-n)^3.

This can be continued on by evaluating for the 5th and subsequent highest numbers in a similar fashion, increasing the accuracy of your answer each time. It should be apparent that including the (x+1)th highest number in the evaluation will add 1/x*n*(1-n)^x to the result for your chances of success. As the highest term you can evaluate to is the 1000*(1-n)th highest number, the complete formula for the probability of success is:

sum of 1/x*n*(1-n)^x for x =1 to 1000*(1-n)

So what we want to now do is find what value of n gives the highest value to that formula. 

The days when I could work that out are long behind me, but we can use Wolfram Alpha to help us.

Remember each additional term adds proportionally less and less to the accuracy of the answer so lets try firstly just for three terms (e.g. that the 4th highest number is in the first n etc. as described above). So we want Wolfram Alpha to evaluate this formula

global maximum sum(1/x*n*(1-n)^x) for x = 1 to 3 

So copy this line in its entirety (including the words global maximum) and paste it into the search field at www.wolframalpha.com and then hit enter or press the = sign. Wait a few seconds for the results to be calculated. There will be a section called Global Maximum. If it shows "approximate form" at the top right of that section, click on that term and it should show "exact form" You will get the formula expanded out into individual terms and then to the right of it, it shows:

0.341572   at   n~~0.422862

What that is saying is that formula is at its maximum when n is approximately 0.422862 and it evaluates to 0.341572 when n has that value. In other words, if we calculate to just 3 terms, the optimum number of random numbers to let pass is 422 (instead of 333 using the 1/3 approach), and the chance of success will be 34%.

Now lets make Wolfram Alpha really work and change the 3 in the formula to 199 so it reads "for x = 1 to 199". So we are trying to get really accurate by evaluating to 199 terms. The result under global maximum is so big, you will need to scroll down to see the result which this time shows:

0.367879   at   n~~0.367861

If you try to go higher than 199, Wolfram Alpha usually gives up, so this is as close to the optimum as we can get using that tool. In fact the optimum would be only ever so slightly different and would be:

0.367879   at   n~~0.367879

Both the optimum fraction to use to maximise the chances of success and the probability of success at that optimum value are the same. 

For those of you still awake, this fraction just happens to be 1/e, e being the natural number e. Now, ain't that interesting.

So what the final result is saying is that to maximise the chance of success, say No to the first 367 numbers (but note the highest of them). Then answer Yes to the first number that is higher than the number noted. If you follow that strategy, your chance of identifying the highest number overall (of the 1000 generated) is 36.7%.


----------



## 2020hindsight (17 November 2009)

bellenuit said:


> .... For those of you still awake, this fraction just happens to be 1/e, e being the natural number e. Now, ain't that interesting.



bellenuit
bludy hell , lol.  
so we end up in the logarithmic domain after all - 

and for someone who used to do calcs on slide rules, I (also) find that fascinating. 

cheers, and thanks for the cerebral workout there 

PS how do you pronounce your nicname anyways?  
Belly knew it?


----------



## bellenuit (17 November 2009)

2020hindsight said:


> PS how do you pronounce your nicname anyways?




Just like the gorgeous Elīna Garanča does at the very start of this song....

http://www.youtube.com/watch?v=SdlT7On7cvY


----------



## Wysiwyg (17 November 2009)

> So what the final result is saying is that to maximise the chance of success, say No to the first 367 numbers (but note the highest of them). Then answer Yes to the first number that is higher than the number noted. If you follow that strategy, your chance of identifying the highest number overall (of the 1000 generated) is 36.7%.




I question this because there is one alternative that isn't addressed. When the highest number of the 1000 is in the first 367. First, how would you know if the highest number (of 1000) was in the first 367? Second, what would be the % chance then?   Please help too 2020.


----------



## 2020hindsight (17 November 2009)

Wysiwyg said:


> I question this because there is one alternative that isn't addressed. When the highest number of the 1000 is in the first 367. First, how would you know if the highest number (of 1000) was in the first 367? Second, what would be the % chance then?   Please help too 2020.



hi wys - well for those 36.7% of trials, you went past the highest number - and that is a nono, i.e. you lose.  But (apparently) it's where some graph on some parallel universe reaches a maximum / optimum value  

PS I sorta liked your quadratic equation (from memory here) - I was thinking along the same lines at that point in time - but then couldn't convince my subconscious  etc etc . Something about the variability of the number that follow the first 367 numbers that makes it damned difficult ( for my mind anyway)


----------



## 2020hindsight (17 November 2009)

:topic
PS Let's face it, craps is also a difficult game to calculate the chances of winning (on the pass line bet at least) :-

Here are the basic rules of the Pass Line bet :-
If the first come-out roll is 2, 3, or 12 you crap out (= you lose) 
If it is a 7 or 11 it is a natural winner. (you win) 
but if it is a 4,5,6,8,9, or 10, then that becomes your "number" (= indecisive ) 

and you keep rolling till you get either that number again  (i.e. you win, albeit several rolls down the track)

or you roll a seven ( which is now the losing number, the number that noone is even game to say it's name lol)

And the casino advantage (for the pass line) turns out to be 1.41%.

But that can take a long time to calculate   (= my point of this post)

PS this game used to be played on street corners, and often by groups of not particularly educated men of all colours, especially black - 

and I find it interesting that the mathematical basis of the game there is so  damned ... "sophisticated" for want of a better word.

PS hell - just by reversing the position, you can bet against the dice = the "don't pass" line.   And the only difference between what you are betting and what the bank is betting is that you don't win with 2 - you only get your money back  = a "push".  (sometimes they push on 12 instead of a snakes-eyes) - and that is enough to change the odds to be 1.36% in the casino's favour, i.e. it is a slightly better bet that the pass line (betting withe the dice).   Ignoring the fact that betting against the dice (= don't pass),  is (often) unpopular etc ...

Again, that's  beyond the average student (or many students at least) to calculate, let alone a lot of yahoos (or whatever colour) playing dice under some streetlight for the last century or whatever - no offence meant. 

http://en.wikipedia.org/wiki/Craps


----------



## Wysiwyg (17 November 2009)

2020hindsight said:


> hi wys - well for those 36.7% of trials, you went past the highest number - and that is a nono, i.e. you lose.  But (apparently) it's where some graph on some parallel universe reaches a maximum / optimum value
> 
> PS I sorta liked your quadratic equation (from memory here) - I was thinking along the same lines at that point in time - but then couldn't convince my subconscious  etc etc . Something about the variability of the number that follow the first 367 numbers that makes it damned difficult ( for my mind anyway)



Well, to know the highest number is in the first 367 no answers, one would have to wait until the last number is drawn of the 1000.


----------



## Wysiwyg (17 November 2009)

2020hindsight said:


> :topic
> 
> 
> And the casino advantage (for the pass line) turns out to be 1.41%.
> ...




I despise dice games for the simple reason of playing backgammon. I would like a dollar for every time ol' mate rolls the BS dice to come over the top and win.  Now cards, well that is a different story. Sometimes they are almost (but not quite) transparent.


----------



## 2020hindsight (17 November 2009)

PS has anyone cracked the code on what the computer offers in "Deal or No Deal?" - I'm guessing the average of the remainder less say 10 or 15% "casino" margin (to encourage you to keep gambling)


----------



## bellenuit (17 November 2009)

Wysiwyg said:


> I question this because there is one alternative that isn't addressed. When the highest number of the 1000 is in the first 367. First, how would you know if the highest number (of 1000) was in the first 367? Second, what would be the % chance then?   Please help too 2020.




_So your strategy is to answer No to the first 333 numbers generated (noting the highest number among these) and then say Yes to the first number *(if any)* that is higher than this._

What the formula did was look at all possible outcomes and see which of those would give the correct result if the strategy was used. So if we use 1 to denote the highest number, 2 the 2nd highest etc., and [ ] to denote the first and second grouping, and dots to denote any other number than those listed, then using the simpler solution for clarity (where 1/3 is the first grouping)

The first term picks up these successful outcomes:

[... 2 ... ]  [... 1 ...] which will happen 2/9 of the time

the second terms adds these successful outcomes:

[... 3 ...]  [... 1 ... 2 ...] which will happen 2/27 of the time

the third term adds these two successful outcomes:

[... 4 ...] [... 1 ... 2 ... 3] which will happen 8/486 of the time and
[... 4 ...] [... 1 ... 3 ... 2] which will happen 8/486 of the time.

etc. for more and more terms. 

The end result is got by adding up all possible successful outcomes and we have said that this is approximately 1 in 3 or 1/3.

The unsuccessful outcomes will occur 2/3's of the time. Included in the 2/3 are these unsuccessful outcomes:

[... 1 ...] [.......] which will happen 1/3 of the time.

[... 3 ...]  [... 2 ... 1 ...] which will happen 2/27 of the time

etc. 

The outcome you mentioned is the first of these:

[... 1 ...] [.......]

When you are following the strategy you don't know whether the highest number is in the first third or not. However, from a probability point of view, it will be in the first third 1/3 of the time and that 1/3 is part of the 2/3's of the time you will be wrong.


----------



## 2020hindsight (17 November 2009)

Wysiwyg said:


> I despise dice games for the simple reason of playing backgammon. I would like a dollar for every time ol' mate rolls the BS dice to come over the top and win.



lol - isn't that the truth.   
I've had 5 double 5's in a row, then not got another for a month. - sheesh. 

try downloading "jellyfish light":-
http://www.jellyfish-backgammon.com/download/

You'd swear that the bludy computer was cheating with its rolls lol ( but it isn't) 
cheers


----------



## bellenuit (17 November 2009)

Wysiwyg said:


> Well, to know the highest number is in the first 367 no answers, one would have to wait until the last number is drawn of the 1000.




That is the case no matter what. You will have to wait until all 1000 numbers are generated before you know the one you picked is right.


----------



## Wysiwyg (17 November 2009)

Wysiwyg said:


> Well, to know the highest number is in the first 367 no answers, one would have to wait until the last number is drawn of the 1000.




I would calculate the % chance differently.

Assuming the highest number (of the 1000) is not in the first 367 'no' answers, then the first number higher than the highest number in the first 367 drawn is a 'yes' then the mathematician was wrong at least 368 times or higher up until the 'yes' call. This is variable.

Let's say the 'yes' call was on the 501st number. Therefore the mathematician was wrong at least 50% of this trial. 500 no's = 50% wrong and Chance left on the plane to Venezuela.


----------



## Wysiwyg (17 November 2009)

bellenuit said:


> That is the case no matter what. You will have to wait until all 1000 numbers are generated before you know the one you picked is right.



Theoretically the mathematician would have to say yes to the 1000th number by default because no other numbers have been higher than the highest in the first 367. Terrible chance at that rate. 100% wrong. 

Please note I do understand up until this final part.


----------



## Wysiwyg (17 November 2009)

bellenuit said:


> The outcome you mentioned is the first of these:
> 
> [... 1 ...] [.......]
> 
> When you are following the strategy you don't know whether the highest number is in the first third or not. However, from a probability point of view, it will be in the first third 1/3 of the time and that 1/3 is part of the 2/3's of the time you will be wrong.




Sorry, got caught up in 2020's posting and missed your explanation of which I thank you. Probability of the number being in the first third 1/3 of the time seems a bit presumptuous but I will accept that for discussion sake.

I promise I will never use this strategy when guessing the number of jelly beans in the jelly bean jar.


----------



## schnootle (17 November 2009)

Well done bellenuit, good memory.

I came across this problem a few years ago in another form. I think it was first called the "fiancee problem" or the "wife problem" (ie you need to decide when to stop dating and marry the best option), it is also variously called the "secretary problem" and the "sultan's dowry problem" and the "37% rule"

A better way to find the exact answer of the optimal strategy is by letting the amount of numbers go to infinity and formulating the probability as an integral. That way you can differentiate and find the maximum.

For those that want to have a look

- as the secretary
http://en.wikipedia.org/wiki/Secretary_problem
http://www.math.uah.edu/stat/urn/Secretary.xhtml

- as the dowry
http://mathworld.wolfram.com/SultansDowryProblem.html

- as the wife
http://www.mathpages.com/home/kmath018/kmath018.htm


----------



## 2020hindsight (17 November 2009)

schnootle said:


> Well done bellenuit, good memory.
> 
> I came across this problem a few years ago in another form. I think it was first called the "fiancee problem" or the "wife problem" (ie you need to decide when to stop dating and marry the best option)



so if mathematicians get a wife with the right figure, is that 37 - 24 - 36 maybe?


----------



## bellenuit (17 November 2009)

schnootle said:


> I came across this problem a few years ago in another form. I think it was first called the "fiancee problem" or the "wife problem" (ie you need to decide when to stop dating and marry the best option), it is also variously called the "secretary problem" and the "sultan's dowry problem" and the "37% rule"
> 
> A better way to find the exact answer of the optimal strategy is by letting the amount of numbers go to infinity and formulating the probability as an integral. That way you can differentiate and find the maximum.
> 
> ...




Schnootle. Thanks for all of those links. I never realised it was such a famous problem. As I said, I came across it once a very long time ago and was surprised I never encountered it again. 

One of your links referenced Martin Gardner and I would suspect that I saw it in one of his books, as I remember reading a few of them back then. 

The interesting thing about the solutions given in your various sources, is that I can hardly understand any of them. Whereas I can't solve the final formula in the solution I gave, other than using Wolfram Alpha to compute answers, at least I know how to work out what the formula is.

Since you are obviously in to this sort of thing, have you come across any good forums dedicated to problem solving (of the maths kind)?


----------



## greenmachine (17 November 2009)

I had the same solution as wikipedia. Though I was going to say reject the first 50% of numbers then select the next biggest.

Turns out the optimal number to reject is 37% but I dont fully understand why 37%...


----------



## Wysiwyg (17 November 2009)

The answer is not entirely correct when examining the "question".



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




The additional information required to arrive at the answer Bellenuit provided is ...

*You are allowed more than one pass of the numbers.* That makes way for the probability factor. One pass of the numbers is a hope that the highest number is not in the first 367 numbers. 

Subsequent passes then opens up the probability factor because the probability (or chance) is based on previous passes.


----------



## bellenuit (17 November 2009)

greenmachine said:


> I had the same solution as wikipedia. Though I was going to say reject the first 50% of numbers then select the next biggest.
> 
> Turns out the optimal number to reject is 37% but I dont fully understand why 37%...




1/e to be exact. 

If you look at either my solution or those reference by schnootle, they arrive at a formula that shows the chances of success based on using a fraction n to represent the fraction of the total number of generated random numbers to allow pass by. 

If you plug in different values for n, the formula will spit out different answers as to what the probability of success is. Though it requires pretty heavy maths (for me at least) to evaluate, it turns out the formula gives the greatest chance of success when n = 1/e or 0.367879. e is the natural number e, which is a constant found quite often in nature (a bit like pi), such as formulae that depict the rate of decay of radioactive materials etc (sorry if you know that already). It also happens that when n has that value, the probability of success is also 1/e.


----------



## schnootle (17 November 2009)

bellenuit said:


> Since you are obviously in to this sort of thing, have you come across any good forums dedicated to problem solving (of the maths kind)?




sorry i cant really help you there, certaintly nothing as vibrant as ASF. I read a webcomic called XKCD which often has references to these sort of elegant famous problems. There is often debate on the associated blog on things like paradoxes, like this one

http://blag.xkcd.com/2008/09/09/the-goddamn-airplane-on-the-goddamn-treadmill/

I am a sucker for a good paradox. If you want you brain to hurt the "Monty Hall Problem" is excellent, guaranteed to confuse and annoy anyone that hasn't seen it.

http://en.wikipedia.org/wiki/Monty_Hall_problem

And the Two Envelopes Paradox is great as well

http://en.wikipedia.org/wiki/Two_envelopes_problem


----------



## bellenuit (17 November 2009)

Wysiwyg said:


> The answer is not entirely correct when examining the "question".
> 
> 
> 
> ...




The probability of success is the same no matter whether you do it once or 1 million times. 

You are getting hung up on the highest number possibly being in the first 367 numbers. That doesn't matter. There will be some times it will be in the first 367 numbers and times that it isn't. Even when it isn't in the 1st 367 numbers, that doesn't mean you are going to be right. If the 3rd highest number is the highest number in the first 367, but the 2nd highest number comes out before the first, you will be wrong also, because the strategy has you answering Yes to the 2nd highest number in that event.


----------



## Wysiwyg (17 November 2009)

Wysiwyg said:


> The answer is not entirely correct when examining the "question".
> 
> 
> 
> ...




On one pass the chances of the highest number being in the second 500 gives an even better chance of success at 50%.


----------



## skc (17 November 2009)

bellenuit said:


> 1/e to be exact.




Thank you bellenuit for an interesting problem. You make me wasted a good few hours though 




Wysiwyg said:


> The answer is not entirely correct when examining the "question".
> 
> The additional information required to arrive at the answer Bellenuit provided is ...
> 
> ...




You don't seem to grasp the basic concept of probability, or you seem too hung up on the wording of the questions.... 

The answer 1/e is true regardless of however times the logician gets to do the activity / test. That's the _probability_ - i.e. chance of being right. Doesn't mean he will be right or wrong this time. It just that the _probability _of getting it right is maximised.


----------



## Wysiwyg (17 November 2009)

skc said:


> Thank you bellenuit for an interesting problem. You make me wasted a good few hours though




Yes me too.


> *You don't seem to grasp the basic concept of probability*, or you seem too hung up on the wording of the questions....
> 
> The answer 1/e is true regardless of however times the logician gets to do the activity / test. That's the _probability_ - i.e. chance of being right. Doesn't mean he will be right or wrong this time. It just that the _probability _of getting it right is maximised.



Oh but I do. 



> 1 : *supported by evidence strong enough to establish presumption* but not proof <a probable hypothesis>
> 2 : establishing a probability <probable evidence>
> 3 : likely to be or become true or real <probable outcome>




I can presume that there is a 50% chance of the highest number being in the
second half of the 1000 and I would be absolutely 100% correct.


----------



## bellenuit (17 November 2009)

Wysiwyg said:


> On one pass the chances of the highest number being in the second 500 gives an even better chance of success at 50%.




Using the 500 to let pass (1/2 as the ratio) to match your example, the chances of the highest number being in the 2nd group is always 1/2, whether its the first, second or umteenth pass. Just because the highest number is in the second pass doesn't mean it will be chosen. I even gave you some examples above.

Your chances don't change with each pass as each game is completely independent of each other.


----------



## Wysiwyg (17 November 2009)

bellenuit said:


> Using the 500 to let pass (1/2 as the ratio) to match your example, the chances of the highest number being in the 2nd group is always 1/2, whether its the first, second or umteenth pass. *Just because the* *highest number is in the second pass doesn't mean it will be chosen.* I even gave you some examples above.
> 
> Your chances don't change with each pass as each game is completely independent of each other.



As with the 37% model there is no guarantee of the correct number being chosen. I guess the only conclusive evidence is to try this practically. One using the 37% model and one using the 50% model.

Three results are possible. 37% model is right, 50% model is right, both are wrong.


----------



## schnootle (17 November 2009)

Wysiwyg said:


> As with the 37% model there is no guarantee of the correct number being chosen. I guess the only conclusive evidence is to try this practically.




1000s of mathematians for 100 years are unlikely to be wrong.

Just ran a quick simulation, heres the plot


----------



## skc (17 November 2009)

Wysiwyg said:


> As with the 37% model there is no guarantee of the correct number being chosen. I guess the only conclusive evidence is to try this practically. One using the 37% model and one using the 50% model.
> 
> Three results are possible. 37% model is right, 50% model is right, both are wrong.




Of course the 37% model doesn't guarantee the correct number being chosen. IT'S A PROBABILITY!!!


----------



## Wysiwyg (17 November 2009)

schnootle said:


> 1000s of mathematians for 100 years are unlikely to be wrong.
> 
> Just ran a quick simulation, heres the plot



This exacts my confusion. Mathematically it is factual, practically there is greater chance with the 50% model.

By the way how did you establish a graph with one pass?


----------



## Sdajii (17 November 2009)

2020hindsight said:


> PS has anyone cracked the code on what the computer offers in "Deal or No Deal?" - I'm guessing the average of the remainder less say 10 or 15% "casino" margin (to encourage you to keep gambling)




I wondered that too, and spent a while trying to work it out. It turned out that there is no exact formula they use, and a lot of human input is used. They often put jokes in (like when the person says at the start that they want to win $20,000, a $19,999 offer is likely to come up, or if they say they want to buy a Mazda 323 they'll get an offer of $323 etc). Generally the offer is approximately the average of the remaining figures minus 10-30% but sometimes the offer will be drastically lower than the average, and occasionally it will even be higher. The lower offers tend to come either after a very high case is knocked out (probably for dramatic effect), or when the median value of the cases is much lower than the mean (because this is a much riskier position for the player and they will be more likely to want to take the safe option). 

I suspect they have a complex formula which takes the mean and median values into account and puts a low weight on upper outlying values. This figure would be immediately displayed to the 'banker' (probably also with the median, mean and other values) and he can quickly enter a figure based on it (using any humourous figure within the general range of the calculated suggestion). I suspect they may have multiple formulae which are all displayed to the 'banker' at once, some being used at different times (eg, there is a recommended one for when the player seems confident, happy, worried, etc) and also the formulae most frequently used probably change between the beginning and end of the game.

Yes, I am a nerd.

Incidentally, I have been on the show twice (once our block was not called up all day, the other I was one of the idiots on the podium), and I have won a grand total of nothing! Two days wasted! I have watched a total of seven games played (I didn't stick around for the last two games on the second day), including the one I was a minor contestent on. They invited me back, but I decided enough was enough, and third time lucky wasn't enticing enough.

As for the random number guessing game, I think there might be a small flaw, and the optimal strategy might include one more variable (clearly making it slightly better, although calculating how much that extremely slight edge would be might be nasty), but I will need more time to go through the thread to see if it has already been brought up. It would mean sometimes making your guess earlier and sometimes not taking a maximum value to date after the 370th value, and waiting for another. I am quite certain that the best strategy is not to rigidly put you name on the highest value to date after the 370th no matter what.

After looking at the solution, I see I was on the right track, but I would have had a lot of trouble working out exactly where the point to start waiting for a higher figure was. I probably would have guessed closer to 500, and I think my gut feeling was a little above 500.


----------



## schnootle (17 November 2009)

Wysiwyg said:


> This exacts my confusion. Mathematically it is factual, practically there is greater chance with the 50% model.
> 
> By the way how did you establish a graph with one pass?




I assumed a perfectly uniform distribution of numbers. That graph is what you would get in the limit of trials.

With 1000 trials of 1000 numbers testing all strategies brute force you 
get this graph.

Here is my python code for the trial for anyone that is interested

from numpy import *
from pylab import *

stop_times = arange(1,1001)
win_counts = zeros(1000)

for k in range(0,len(stop_times)):

	for j in range(0,1000):

		r = rand(1000)

		gone = r[0:stop_times[k]]
		coming = r[stop_times[k]+1:1000]

		max_gone = max(gone)

		chosen = 0
		for i in range(stop_times[k]+1,1000):

			if r_ > max_gone:
				chosen = r
				break

		if chosen == max(r):
			win_counts[k]+=1

	print k

plot(stop_times,win_counts)
xlabel("stopping time")
ylabel("number of right out of 1000")
show()_


----------



## bellenuit (17 November 2009)

schnootle said:


> sorry i cant really help you there, certaintly nothing as vibrant as ASF. I read a webcomic called XKCD which often has references to these sort of elegant famous problems. There is often debate on the associated blog on things like paradoxes, like this one
> 
> http://blag.xkcd.com/2008/09/09/the-goddamn-airplane-on-the-goddamn-treadmill/
> 
> ...




Thanks for those links. 

I think I am going to gave fun with the airplane problem as I can see the merit in the opposing arguments. 

I heard the Monty Hall problem before and although confused at first, I now have no problem with it. 

The Two Envelopes is new to me too and quite interesting, but the explanation given quickly points out the fallacy.


----------



## bellenuit (17 November 2009)

Wysiwyg said:


> Yes me too.
> 
> Oh but I do.
> 
> ...




No you wouldn't. You would be correct in saying that there is a 50% chance of the highest number being in the second half, but concluding that you would then have a 100% chance of picking it is clearly wrong, as I have already shown you in an example. Here are lots of examples that you would not be correct on (where the numbers denote the highest by order, 1 being the highest, 2 the 2nd highest etc..). Notation as before. All of these have the highest number in the second group, but the strategy would not have picked it.

[... 3 ...] [... 2 ... 1 ...]
[... 4 ...] [... 2 ... 1 ...] or [... 4 ...] [... 3 ... 1 ...] 
etc. for 5, 6, 7 etc being the highest in the first group and any number higher than that coming before the 1 in the second group

The only time you could be 100% sure that if the highest number is in the 2nd half that you have 100% chance of picking it, is this unique case....

[... 2 ...] [... 1 ...]

That will only happen 25% of the time because it requires the 2nd highest number to be in the first half which will only happen 1/2 the time as well. So 1/2 X 1/2 is the probability of that happening.


----------



## Wysiwyg (17 November 2009)

schnootle said:


> I assumed a perfectly uniform distribution of numbers. That graph is what you would get in the limit of trials.
> 
> With 1000 trials of 1000 numbers testing all strategies brute force you
> get this graph.



Thanks schnootle, cool name by the way.

I'm going to let this thread go now and admit it is a system based on probabilities derived from trials. I wonder if a statistical probability can be generated for a coin head or tail turn?


----------



## bellenuit (17 November 2009)

Wysiwyg said:


> .... and admit it is a system based on probabilities derived from trials.




Wrong there too. The determination of 1/e to be the optimum ratio and 1/e being the probability of success at that ratio were derived purely from the information given using probability theory. It was straightforward mathematics, though difficult mathematics for those not so used to it. No trial was needed to get to that result.

Schnootle's graph was just to assist those who had difficulty accepting the result by graphing the chances of success based on different choices of ratio, so that it was visually obvious which ratio was closest to the optimum.


----------



## skc (17 November 2009)

Wysiwyg said:


> Thanks schnootle, cool name by the way.
> 
> I'm going to let this thread go now and admit it is a system based on probabilities derived from trials. I wonder if a statistical probability can be generated for a coin head or tail turn?




Probability was derived by math. Schnootle merely illustrated it by trials.

You can calculate the probability of a coin toss using pure maths... 1 out of 2 possible outcomes = 50%. Then illustrate it with a trial... tossing a coin a million times and get 499350 heads and 500650 tails. 

The probability remains correct regardless of what the trial might say. The actual result from the tosses has no bearing on the probability.


----------



## bellenuit (18 November 2009)

schnootle said:


> Just ran a quick simulation, heres the plot




I wonder if the solution to this problem has applications in other areas, such as the stock market. 

The sample would probably be too small to be relevant, but I'm thinking along the lines of trading a stock by buying low one month and selling high the next.

Assume there are 21 trading days in a month. Monitor the share price of a particular stock for the first 7 trading days and note the lowest price it reaches. Then if it goes lower than that in the following 14 trading days, buy it at that lower price. If the fluctuations are perfectly random, there would be about a 1 in 3 chance of picking the lowest price for that month. Monitoring wouldn't really require you to do much more than just look at the past 7 days trading data at the end of the 7th day. This data should be available from many sources, including most online brokers. Then put in a Good Until Cancelled buy order at just under that lowest price. Then the next month use the strategy to try and get the highest price for that month as your trigger to sell. 

There are some economists, for example Burton Malkiel who wrote _A Random Walk Down Wall Street_, who hold that share price movements are indistinguishable from completely random movements (I assume in the absence of news that might effect the stock).

Long terms trends, such as an average growth in the share price of 10% pa say, would probably not make much difference to the strategy. 

You would have to be alert for other influences that might dramatically effect the price, but in the absence of those, it mightn't be a bad strategy to determine when to enter and exit the market. 

Just a thought.


----------



## schnootle (18 November 2009)

bellenuit said:


> I wonder if the solution to this problem has applications in other areas, such as the stock market.
> 
> Just a thought.




Interesting thought, however i dont think you would have much luck. The random number game is built on the fact that you know the numbers are sampled from a uniform distribution and you know how many numbers there are. We know neither about the stock market over any interval.

Market prices are often modelled as a random walk, meaning that each price movement is independent of the last (ie the price movement is driven by white noise) - this doesn't mean we know its probability distribution and it certainly wont be uniform, it is probably closer to gaussian.


----------



## 2020hindsight (18 November 2009)

schnootle said:


> ...this doesn't mean we know its probability distribution and it certainly wont be uniform, it is probably closer to gaussian.




and probably closer still to guessin. - as Buffet would say (paraphrased) - "we're all like Cinderella trying to stick around as close to midnight as possible - but we're dancing in a room where the clocks have no hands".  



> "Success in investing doesn't correlate with I.Q. once you're above the level of 25.  Once you have ordinary intelligence, what you need is the temperament to control the urges that get other people into trouble in investing."  - Warren Buffett
> 
> "If Calculus or Algebra were required to be a great investor, I'd have to go back to delivering newspapers." - Warren Buffett
> 
> "There seems to be some perverse human characteristic that likes to make easy things difficult." - Warren Buffett




PS But it's interesting that wives can be chosen that way - lol  I guess the girls would same the same thing about us.


----------



## Wysiwyg (18 November 2009)

2020hindsight said:


> - "we're all like Cinderella trying to stick around as close to midnight as possible - but we're dancing in a room where the clocks have no hands".



I like that one. 

Oh I meant to tell you I tried the jellyfish backgammon for an hour and then promptly removed the program. Strangely the computer 'often' drew more doubles, drew the exact numbers it needed and the last straw was when I finally drew double sixes, jellyfish followed with two double sixes in a row. 

And it doubles up all the time which was annoying.


----------



## bellenuit (18 November 2009)

schnootle said:


> Market prices are often modelled as a random walk, meaning that each price movement is independent of the last (ie the price movement is driven by white noise) - this doesn't mean we know its probability distribution and it certainly wont be uniform, it is probably closer to gaussian.




You are right. It is probably as long ago since I read _A Random Walk Down Wall Street_ as it is since I first encountered this problem. If I recall correctly the randomness he was modelling was based purely on a 50% chance that the next move would be up or down 1 unit from where it currently is, similar to walking, which is where the title obviously comes from.


----------



## brty (18 November 2009)

bellenuit,



> There are some economists, for example Burton Malkiel who wrote A Random Walk Down Wall Street, who hold that share price movements are indistinguishable from completely random movements




Which is why they are no good at trading...

What is a random movement?? Can anybody prove that such a thing exists??

Every man and his dog can quickly and easily see that a stock say BHP has moved up from ~$36 to $41 over the last 2 weeks. Consciously or subconsciously this will affect what many participants in the market do with this stock tomorrow. For an event to be compared with 'random' there can be no memory from prior events, clearly in this case memory comes into it.

All the 'information' about randomness and markets is written by those who don't have a clue what's going on. Money is being transferred from those without a clue to those that do know.

brty


----------



## bellenuit (19 November 2009)

brty said:


> Which is why they are no good at trading...
> 
> What is a random movement?? Can anybody prove that such a thing exists??
> 
> ...




To be fair to Burton Malkiel, I actually misstated what he wrote by that statement and Schnootle corrected me. 

I'm really digging into my memory, but he generated graphs of a hypothetical share where the next move was completely random in the sense that it could be up or down (maybe sideways too), but only by 1 unit from where it currently is. The next move after that would be randomly up or down (or sideways) one unit from the new point. So this has the memory of prior events that you mentioned as each move can only be 1 unit away at most from where the previous move ended. 

He then showed those graphs to stock chartists who look for the typical patterns that chartists look for (head and shoulder patterns etc.) and mixed then in with some charts of actual stocks. Apparently the chartists could not tell which were the hypothetical stocks and which were the real.

I am not trying to defend his arguments and can't in any case as I remember so little from the book. But it is a fairly well respected work in the industry, so I wouldn't dismiss him offhand.


----------



## brty (19 November 2009)

bellenuit,

I am not having a go at you at all, I apologise if it came across that way. I am having a go at "random", a concept I do not believe in.

This bit is what annoys me about randomness and peoples acceptance of it....



> he generated graphs of a hypothetical share where the next move was completely random




I seriously doubt the graph was completely random, because it was produced by a computer that had been given instructions. 

The task of a trader is to make money from movements, not to identify if a chart is a stock or made up. Were any systems tested on the data presented?? I think not (I have his book and read it, it is full of holes and excuses, from memory)

brty


----------



## schnootle (19 November 2009)

brty said:


> I seriously doubt the graph was completely random, because it was produced by a computer that had been given instructions.
> 
> brty




some pseudo-random numbers are pretty bloody good, and besides he may have used other sources of randomness - like atmospheric noise http://www.random.org/

A lot of incredibly smart people have used valid arguments and rigor on both sides of the random walk / efficient markets hypothesis, we cant discount either

But i suppose the proof of the pudding is in the eating, if you have been making money using nothing but charting techniques then that is a valid argument too.


----------



## 2020hindsight (19 November 2009)

Wysiwyg said:


> I tried the jellyfish backgammon for an hour and then promptly removed the program. Strangely the computer 'often' drew more doubles, drew the exact numbers it needed and the last straw was when I finally drew double sixes, jellyfish followed with two double sixes in a row.
> 
> And it doubles up all the time which was annoying.



Lol - yep,  One certainly gets the feeling that the games have been made intentionally "interesting" -  It may not be random - although you can force it to be random, see d) below -  but  I don't believe it's rigged,  for the following reasons :-

 [Disclaimer ... I'm fairly sure this applies to Jellyfish Lite - don't waste too much time on it in case I'm wrong - assuming you can be bothered reading this as well lol - I currently only have access to my work computer- and don't usually play games on it to confirm ... so the following is from memory]

a) each sequence of rolls is logged in the memory as "a prerecorded game"  and can be repeated - 
b) and in the re-run you can try alternative rolls at various "checkpoints" and see if you'd have won if you'd jumped left instead of right etc (gotta feeling it gives hints as well) 
c) you can even swap roles (or rolls if you prefer) with the computer, i.e. he gets the white rolls, you get the brown, -  That way for instance he'd have rolled the double six, and you'd have countered with two double sixes lol.
d) if you're not happy with those "prerecorded games / roll sequences", you can make a sequence of your own choosing - i.e. rolling dice in the background - then there's no question of the rolls being random

e) my goal was (still is) to beat the computer (first time up) on any one game no matter which set of rolls I play, white or brown.   Lol - still working on that one, - there has been a long  pause in my efforts towards that goal as well.  Note that you can set the difficulty level a few down from "maximum" - makes the bludy computer a bit more "human" in the errors department lol.

PS - you mention doubling - it sure sharpens up your skills with respect to reading a game and knowing when to double.  - "know when you hold , when to fold" etc.  Like, you double when you think you have a 70% chance of winning as they say - lol - I used to play 3 other blokes once a week for a few dollars.  One bloke thought he was playing poker - and when you doubled him - no sooner was the doubling cube turned, and he'd double you back - claiming you were "bluffing" lol.  (like ... the facts are out there for all to see)   - He contributed the most dollars to the kitty. 

PS when I said back there that I rolled 5 double 5's in a row, then not again for a month - I was talking real dice.   So much for the "randomness of dice", lol


----------



## 2020hindsight (19 November 2009)

Summary :- Theory and practice are the same in theory. In practice they are different.


----------



## 2020hindsight (19 November 2009)

Variant to that "wife-choosing game" - you put 4 blokes and 4 girls in a room - you ask em to pair up "for life" - and you work out a tactic - employed by the men and girls alike - whereby the sum of the mismatches in partners as finally self-chosen is minimised.

Hang on, I think I just described "reality"  - "So this is reality, hope it didn't mess up your mind "

REminds me , when I was a student, there was a Computer Ball - where we all put our names in a hat, - together with a six page questionnaire - and the computer sorted us into "double blind dates".   One of my friends married his partner of that night - still super happy together.  

Only later did the computer programmer ( one of our number) admit that all he did was match us up on question 18 ... "political leaning" lol


----------



## 2020hindsight (19 November 2009)

schnootle said:


> some pseudo-random numbers are pretty bloody good, and besides he may have used other sources of randomness - like atmospheric noise



even randomness has to be defined m8 - like .. chosen from pink noise vs white noise etc


----------



## bellenuit (19 November 2009)

brty said:


> bellenuit,
> 
> I am not having a go at you at all, I apologise if it came across that way.
> 
> brty




brty, no apologies needed. It didn't come across that way at all to me.


----------



## skc (19 November 2009)

bellenuit said:


> To be fair to Burton Malkiel, I actually misstated what he wrote by that statement and Schnootle corrected me.
> 
> I'm really digging into my memory, but he generated graphs of a hypothetical share where the next move was completely random in the sense that it could be up or down (maybe sideways too), but only by 1 unit from where it currently is. The next move after that would be randomly up or down (or sideways) one unit from the new point. So this has the memory of prior events that you mentioned as each move can only be 1 unit away at most from where the previous move ended.
> 
> ...




All he's proved is that:

1. Using random generator can produce charts that look like real.

2. Real share charts can look like those produced by random generator.

3. Chartists can't tell the two apart.

It doesn't follow that real shares follow a random pattern. There is a leap in logic there imo.


----------



## brty (19 November 2009)

schnootle,



> he may have used other sources of randomness - like atmospheric noise




How is atmospheric noise random?? There is a huge leap between we can't predict it/calculate it, and something that is random. Random means no order to outcomes, not we can't predict the outcome. Therefore things appear random to those without a clue as to what is driving an event /(series of events).

The fallback line for the random believers when challenged that nothing is random, is along the lines of "as good as random", which really means 'we have not worked out how to calculate it yet'.

The concept of random is something that exists in the minds of mathematicians, not in the real universe, yet the concept has permeated all types of thinking in the modern world.

brty


----------



## Wysiwyg (19 November 2009)

2020hindsight said:


> even randomness has to be defined m8 - like .. chosen from pink noise vs white noise etc




Part of my debate here was the illusion that mathematicians create with the chance "theory". Is the graph provided by schnootle showing the statistical reality or a proven reality? Nothing wrong with those results. Wrong 63% of the time is terrible odds but the chances are better than 0 and less than 50%.

Take this formula below to any game of chance and see how it stacks up.  Oh and remember your if's.



> A discrete-time martingale is a discrete-time stochastic process (i.e., a sequence of random variables) X1, X2, X3, ... that satisfies for all n
> 
> \mathbf{E} ( \vert X_n \vert )< \infty
> 
> ...


----------



## schnootle (19 November 2009)

brty said:


> schnootle,
> 
> How is atmospheric noise random?
> 
> brty




Yes you could argue that atmospheric noise is deterministic, however its complexity is such that in practice it is an excellent source of entropy.



brty said:


> The concept of random is something that exists in the minds of mathematicians, not in the real universe, yet the concept has permeated all types of thinking in the modern world.




Now we are in the sticky "does god play dice" territory. Pre-Quantum Mechanics the concept of randomness may have been only a mathematical construct, now physicist love it too. If you agree with quantum mechanics then everything at the quantum level is inherently unpredictable, then radio-active decay is an perfect source or randomness.

Quantum mechanics as a theory as been incredibly successful, so it is entirely possible that randomness is intrinsic to the universe - not just a mathematical concept.


----------



## Wysiwyg (19 November 2009)

schnootle said:


> Quantum mechanics as a theory as been incredibly successful,* so it is entirely **possible that randomness is intrinsic to the universe* - not just a mathematical concept.



My observation of the universe has evidence that everything is in order. Organics are observed to reproduce with the same species and choose their food for example. Whereas non-organics are harder to define but since they are required for organics to exist, then the order is there too.


----------



## brty (19 November 2009)

schnootle,



> The randomness claimed for quantum mechanics has no foundation in mathematics and it appears to be impossible to construct such a foundation. This does not make it wrong but suggests there are problems in our existing conceptual framework. It also means that physicists when arguing about these issues are debating philosophy with no objective way of deciding the issue.




from....

http://www.mtnmath.com/whatrh/node77.html

Is quantum mechanics fact, or a series of concepts and theories that seem to mimmick/explain reality?? 

This bit....



> everything at the quantum level is inherently unpredictable




...is only because we have not worked out how to do it, does not mean it is random.

brty


----------



## schnootle (19 November 2009)

brty said:


> ...is only because we have not worked out how to do it, does not mean it is random.
> 
> brty




Perhaps, personally i am still on the fence with the whole random vs deterministic thing. There are persuasive arguments on both sides


----------



## akkopower (13 July 2011)

My solution to the rng problem is simple and determining the probability of successfully using this strategy is not difficult. 

The solution is

ignore the first number.
if the second number is larger than the first, choose it, else
if the third number is larger than the first, choose it, else
if the fourth number is larger than the first, choose it, else
-
follow the pattern
-
if the second last number is larger than the first, choose it, else
if the last number is larger than the first, choose it, else
choose the last number even though you know it is not the highest.

Using this strategy I determined that the probability of picking the highest number is slightly larger than 0.25. More preciously 0.25*(999)/(998).

In this rng problem there are 1000 numbers, if we let the number of numbers be a variable say, n. Then the probability of choosing the highest number using this strategy is,

p = 0.25*(n-1)/(n-2).

How to determine the form of p:

I looked at a simplified problem with n=3 determined the probability of success using this strategy and found it to be p = 50% = 1/4 * 2 

then I looked at n=4 and found p = 37.5% = 1/8 * 3 

then I looked at n=5 and found p = 25% = 1/12 * 4

which leads to the pattern p = 0.25*(n-1)/(n-2).

I assume that the same analysis I used to determine the above will hold for any n. Why wouldn't it? 

Anyone disagree/ agree with the method or with p  = 0.25*(999)/(998).


----------



## bellenuit (13 July 2011)

akkopower said:


> The solution is
> 
> ignore the first number.
> if the second number is larger than the first, choose it, else
> ...




Remember the question was:

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

So the answer given previously had a higher chance of success than your method, as its probability of success was 1/e, or 0.37, compared to your 0.25.


----------



## cynic (16 May 2015)

bellenuit said:


> What thread was that? I thought I might have posted it on ASF before, but the only puzzle thread I could find was this one and it wasn't here.




I think it may have been this one.


----------



## bellenuit (17 May 2015)

cynic said:


> I think it may have been this one.




Thanks.

The Wikipedia link to the solution of the Secretary Problem - http://en.wikipedia.org/wiki/Secretary_problem - has this version of the problem called the Googol Game. The Googol Game apparently was the original and was first published in Scientific American by Martin Gardner in 1960 in his regular Mathematical Games column.

Gardner wrote several puzzle type books which were collections of his puzzles from SA. I read most of them when I was a lot younger and knew math a lot better than I do now. They are worth having a read if you come across them in bookstores, but they are all online as e-books anyway. He had a brilliant mind. He died 5 years ago. More on him here:

http://en.wikipedia.org/wiki/Martin_Gardner


----------

