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

[bellenuit]

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



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.

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]

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



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.

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

 

[skc]

1/e to be exact.

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

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

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.

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]

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]

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]

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]

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]

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]

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]

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]

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]

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

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]

Yes me too.

Oh but I do.

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.

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]

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]

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

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]

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]

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]

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

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