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

[bellenuit]

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]

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]

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]

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

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]

:topic


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

But that can take a long time to calculate

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.

And the only difference between what you are betting and what the ank 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. But betting against the dice is (often) unpopular etc.

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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

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]

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]

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]

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]

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