The stopping rule
Locked
 
|
Although this isn't new, I just came across it (perhaps again) and was so enchanted that I wanted to share it.
Generate but don't look at three random numbers. (Have someone ensure that they are distinct. There is no constraint on the range.) Look at the first two. You are now able to guess with a better than 50% chance of being right whether the first number is larger than the unseen third.
I like this almost as much as the Monte Hall problem.
-- Russ
============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
|
|
I assume the reason for the second number is to give information about
the range of random nos? I can't see otherwise why it would be relevant. Because if you knew the range beforehand, like you do with most RNGs, then the first number is more likely to be less than the unseen number if it is less than half of the maximum, and more likely to be more if its is greater than half of the maximum. I'm also assuming that the numbers are drawn from a uniform distribution, although this is not stated. On Tue, Jun 07, 2011 at 11:11:07PM -0700, Russ Abbott wrote: > Although this isn't new, I just came across it (perhaps again) and was so > enchanted that I wanted to share it. > > Generate but don't look at three random numbers. (Have someone ensure that > they are distinct. There is no constraint on the range.) Look at the first > two. You are now able to guess with a better than 50% chance of being right > whether the first number is larger than the unseen third. > > I like this almost as much as the Monte Hall problem. > > *-- Russ * > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > lectures, archives, unsubscribe, maps at http://www.friam.org -- ---------------------------------------------------------------------------- Prof Russell Standish Phone 0425 253119 (mobile) Principal, High Performance Coders Visiting Professor of Mathematics [hidden email] University of New South Wales http://www.hpcoders.com.au ---------------------------------------------------------------------------- ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
|
Administrator
|
In reply to this post by Russ Abbott
Do you have a pointer to an explanation?
-- Owen On Jun 8, 2011, at 12:11 AM, Russ Abbott wrote: > Although this isn't new, I just came across it (perhaps again) and was so enchanted that I wanted to share it. > > Generate but don't look at three random numbers. (Have someone ensure that they are distinct. There is no constraint on the range.) Look at the first two. You are now able to guess with a better than 50% chance of being right whether the first number is larger than the unseen third. > > I like this almost as much as the Monte Hall problem. > > -- Russ > > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > lectures, archives, unsubscribe, maps at http://www.friam.org ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
|
|
Russell Standish has the right idea. If you knew the range, say the first number is higher/lower than the third depending on whether the first numbers is greater than or less than the middle of the range. Since you don't know the range, the second random number is used instead. Say higher/lower depending on whether the first number is higher/lower than the second.
Also, think about it this way. If the middle number is either greater than or less than both the first and the third, you have a 50% chance of being right. If it's between the first and the third, the strategy described will always be right. Presumably there is a non-zero probability that the second number will be between the first and the third. Therefore one has a greater than 50% chance of being right. -- Russ
On Wed, Jun 8, 2011 at 10:06 AM, Owen Densmore <[hidden email]> wrote: Do you have a pointer to an explanation? ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
|
|
How does knowing the second number establish the range ? Is there any work on this.
Sarbajit On Thu, Jun 9, 2011 at 1:15 AM, Russ Abbott <[hidden email]> wrote:
============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
|
|
It doesn't establish the range. All that's really necessary is that there be a non-zero probability that the second number falls between the first and the third. On those occasions when it does you will have the right answer. On all others you will be right 50% of the time. I saw it in a reprint of this paper. Look for David Blackwell.
What I like about this phenomenon is that it feels like action at a (mathematical) distance -- similar to the Monte Hall problem in which showing the content of one door makes it better to switch choices. (If you don't know this problem, it's worth looking up, e.g., here.) -- Russ Abbott _____________________________________________ Professor, Computer Science California State University, Los Angeles Google voice: 747-999-5105 blog: http://russabbott.blogspot.com/ vita: http://sites.google.com/site/russabbott/ _____________________________________________ On Wed, Jun 8, 2011 at 6:52 PM, Sarbajit Roy <[hidden email]> wrote: How does knowing the second number establish the range ? Is there any work on this. ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
|
|
In reply to this post by Sarbajit Roy (testing)
Ok, I'm a bad person for not reading the cited paper, but I was thinking
about problem late last night. I keep thinking that we need to make assumptions
about the distribution (regarding bounds and shape), but then I can't figure
out a combination of assumptions that really seems necessary. This is because
any distribution has a median (even if it is an incalculable median, like 1/2
infinity). Using that as the key:
Given two randomly generated numbers, odds are that one of them is above the median, the other is below the median. We need two numbers, so that we can tell which one is which. If we restrict ourselves to making a guess relative to the first number (because that's what I think Russ was saying), then when the first number is the smaller one, we guess that it is below the median (and hence the third number has more that a 50% chance of being above it). Reverse if the first number is the larger one. Of course, sometimes we are wrong, and both random numbers are on the same side of the median... but on average we are still better off guessing in this manner. If we know the shape of the distribution, it should be pretty easy to calculate the advantage. For example, if the distribution is normal, the smaller score will (on average) be one standard deviation below the mean, and hence 84% of the distribution will be above it. Eric On Wed, Jun 8, 2011 11:10 PM, Russ Abbott <[hidden email]> wrote: Eric Charles Professional Student and Assistant Professor of Psychology Penn State University Altoona, PA 16601 ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
|
|
A lucid analysis. BUT,
If we consider the median = 1/2 infinity case, we end up with 3 "equally probable" cases. a) both number below median b) both numbers above median c) one below and one above median alternatively we could get 4 "equally probable" cases 1) A below B below 2) A below B above 3) A above B below 4) A above B above I'm still unable to see how we get a "better than 50%" edge by knowing the 2nd number. The "normal" distribution would not apply to random numbers - which are evenly distributed ie. "flat". Sarbajit On Thu, Jun 9, 2011 at 5:46 PM, ERIC P. CHARLES <[hidden email]> wrote:
============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
|
|
In reply to this post by Eric Charles
Sarbajit,
Great point, but let me make it a bit more complicated. Possibilities marked with a "+" indicate situations in which we will have a probabilistic advantage in our guessing, possibilities marked with a "-" indicate situations in which we will have a probabilistic disadvantage in our guessing: 1) A below B below 1a) and A below B + 1b) and B below A - 2) A below B above + 3) A above B below + 4) A above B above 4a) and A above B + 4b) and B above A - Eric P.S. The case of a single bounded distribution is definitely the hardest for me to think about, a double bounded or unbounded distribution seems much more intuitive. Also, the restriction to guess relative to A makes it harder for me to think about. Imagine instead that all we did was guess that the third number would be above the smallest of the first two. On Thu, Jun 9, 2011 08:35 AM, Sarbajit Roy <[hidden email]> wrote: Eric Charles Professional Student and Assistant Professor of Psychology Penn State University Altoona, PA 16601 ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
|
|
The first number partitions the distribution. Unless the areas on
either side of the partition are equal, there is a greater than 50 percent chance that the second number will be drawn from the larger partition. Assuming that the three numbers are independent and identically distributed, the probability of drawing the third number from the larger partition is the same as the probability of drawing the second number from the larger partition. Basically, the second number determines whether the third number will be larger or smaller than the first. Shawn On Thu, Jun 9, 2011 at 9:09 AM, ERIC P. CHARLES <[hidden email]> wrote: > Sarbajit, > Great point, but let me make it a bit more complicated. Possibilities marked > with a "+" indicate situations in which we will have a probabilistic > advantage in our guessing, possibilities marked with a "-" indicate > situations in which we will have a probabilistic disadvantage in our > guessing: > 1) A below B below > 1a) and A below B + > 1b) and B below A - > 2) A below B above + > 3) A above B below + > 4) A above B above > 4a) and A above B + > 4b) and B above A - > > Eric > > P.S. The case of a single bounded distribution is definitely the hardest for > me to think about, a double bounded or unbounded distribution seems much > more intuitive. Also, the restriction to guess relative to A makes it harder > for me to think about. Imagine instead that all we did was guess that the > third number would be above the smallest of the first two. > > On Thu, Jun 9, 2011 08:35 AM, Sarbajit Roy <[hidden email]> wrote: > > A lucid analysis. BUT, > If we consider the median = 1/2 infinity case, we end up with 3 "equally > probable" cases. > a) both number below median > b) both numbers above median > c) one below and one above median > > alternatively we could get 4 "equally probable" cases > 1) A below B below > 2) A below B above > 3) A above B below > 4) A above B above > > I'm still unable to see how we get a "better than 50%" edge by knowing the > 2nd number. > > The "normal" distribution would not apply to random numbers - which are > evenly distributed ie. "flat". > > Sarbajit > > On Thu, Jun 9, 2011 at 5:46 PM, ERIC P. CHARLES <[hidden email]> wrote: >> >> Ok, I'm a bad person for not reading the cited paper, but I was thinking >> about problem late last night. I keep thinking that we need to make >> assumptions about the distribution (regarding bounds and shape), but then I >> can't figure out a combination of assumptions that really seems necessary. >> This is because any distribution has a median (even if it is an incalculable >> median, like 1/2 infinity). Using that as the key: >> >> Given two randomly generated numbers, odds are that one of them is above >> the median, the other is below the median. We need two numbers, so that we >> can tell which one is which. If we restrict ourselves to making a guess >> relative to the first number (because that's what I think Russ was saying), >> then when the first number is the smaller one, we guess that it is below the >> median (and hence the third number has more that a 50% chance of being above >> it). Reverse if the first number is the larger one. >> >> Of course, sometimes we are wrong, and both random numbers are on the same >> side of the median... but on average we are still better off guessing in >> this manner. If we know the shape of the distribution, it should be pretty >> easy to calculate the advantage. For example, if the distribution is normal, >> the smaller score will (on average) be one standard deviation below the >> mean, and hence 84% of the distribution will be above it. >> >> Eric >> >> On Wed, Jun 8, 2011 11:10 PM, Russ Abbott <[hidden email]> wrote: >> >> It doesn't establish the range. All that's really necessary is that there >> be a non-zero probability that the second number falls between the first and >> the third. On those occasions when it does you will have the right answer. >> On all others you will be right 50% of the time. I saw it in a reprint of >> this paper. Look for David Blackwell. >> What I like about this phenomenon is that it feels like action at a >> (mathematical) distance -- similar to the Monte Hall problem in which >> showing the content of one door makes it better to switch choices. (If you >> don't know this problem, it's worth looking up, e.g., here.) >> >> -- Russ Abbott >> _____________________________________________ >> Professor, Computer Science >> California State University, Los Angeles >> >> Google voice: 747-999-5105 >> blog: http://russabbott.blogspot.com/ >> vita: http://sites.google.com/site/russabbott/ >> _____________________________________________ >> >> >> >> On Wed, Jun 8, 2011 at 6:52 PM, Sarbajit Roy <[hidden email]> wrote: >>> >>> How does knowing the second number establish the range ? Is there any >>> work on this. >>> >>> Sarbajit >>> >>> On Thu, Jun 9, 2011 at 1:15 AM, Russ Abbott <[hidden email]> >>> wrote: >>>> >>>> Russell Standish has the right idea. If you knew the range, say the >>>> first number is higher/lower than the third depending >>>> on whether the first numbers is greater than or less than the middle of the >>>> range. Since you don't know the range, the second random number is used >>>> instead. Say higher/lower depending on whether the first number is >>>> higher/lower than the second. >>>> Also, think about it this way. If the middle number is either greater >>>> than or less than both the first and the third, you have a 50% chance of >>>> being right. If it's between the first and the third, the strategy described >>>> will always be right. Presumably there is a non-zero probability that the >>>> second number will be between the first and the third. Therefore one has a >>>> greater than 50% chance of being right. >>>> >>>> -- Russ >>>> >>>> On Wed, Jun 8, 2011 at 10:06 AM, Owen Densmore <[hidden email]> >>>> wrote: >>>>> >>>>> Do you have a pointer to an explanation? >>>>> >>>>> -- Owen >>>>> >>>>> On Jun 8, 2011, at 12:11 AM, Russ Abbott wrote: >>>>> >>>>> > Although this isn't new, I just came across it (perhaps again) and >>>>> > was so enchanted that I wanted to share it. >>>>> > >>>>> > Generate but don't look at three random numbers. (Have someone ensure >>>>> > that they are distinct. There is no constraint on the range.) Look at the >>>>> > first two. You are now able to guess with a better than 50% chance of being >>>>> > right whether the first number is larger than the unseen third. >>>>> > >>>>> > I like this almost as much as the Monte Hall problem. >>>>> > >>>>> > -- Russ >>>>> > >>>>> > ============================================================ >>>>> > FRIAM Applied Complexity Group listserv >>>>> > Meets Fridays 9a-11:30 at cafe at St. John's College >>>>> > lectures, archives, unsubscribe, maps at http://www.friam.org >>>>> >>>>> >>>>> ============================================================ >>>>> FRIAM Applied Complexity Group listserv >>>>> Meets Fridays 9a-11:30 at cafe at St. John's College >>>>> lectures, archives, unsubscribe, maps at http://www.friam.org >>>> >>>> >>>> ============================================================ >>>> FRIAM Applied Complexity Group listserv >>>> Meets Fridays 9a-11:30 at cafe at St. John's College >>>> lectures, archives, unsubscribe, maps at http://www.friam.org >>> >> >> ============================================================ >> FRIAM Applied Complexity Group listserv >> Meets Fridays 9a-11:30 at cafe at St. John's College >> lectures, archives, unsubscribe, maps at http://www.friam.org >> >> Eric Charles >> >> Professional Student and >> Assistant Professor of Psychology >> Penn State University >> Altoona, PA 16601 >> >> > > Eric Charles > > Professional Student and > Assistant Professor of Psychology > Penn State University > Altoona, PA 16601 > > > > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > lectures, archives, unsubscribe, maps at http://www.friam.org > ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
|
|
a) The assumption was that there is no constraint on the range.
b) Knowing 2 numbers (or even a hundred) tells us nothing about the range/boundary for the 3rd (or the 101st). c) So the only thing I can say is that if the 3 numbers are disclosed to the guesser in ascending order, the probability that the 3rd number is greater than the 1st approaches or equals 1 (making it well over 50%). Sarbajit On Thu, Jun 9, 2011 at 7:36 PM, <[hidden email]> wrote: The first number partitions the distribution. Unless the areas on ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
|
|
In reply to this post by Shawn Barr
1) Constraint on the
range is irrelevant, it is just a distraction.
2) Knowing the actual range or the boundaries is irrelevant, it is only a distraction. -- heck, even knowing the shape of the distribution and the actual value of the numbers is a distraction. 3) All that matters is that half the time the first number will be below the median and half the time it will be above the median (by definition of the median). As Shawn points out (providing what seems like a cleaner presentation than the one I offered), the second number only serves to help you guess whether the first number is above or below the median, and no matter what distribution you have it will on average provide at least some (Shannon-style) information. Surely guessing in this manner will often get you the wrong answer, but all that was asserted was that you would, on average guess at a better than chance level. As long as there are more than two numbers in the distribution from which the random numbers are drawn, and the three numbers are known to be distinct, it should be true - hence the reducability to the Monte Hall problem. Eric P.S. For the Monte Hall reduction, we can do it with simple ordinal judgements: Step 1, you are given a door (it does not matter how good a prize is behind that door) Step 2, you are told that a second door has a better prize behind it. Step 3, you are asked if you want to take the prize behind a third door, or stick with the first door. Because we know that what is behind the three doors is different, there are two possibilities: 1. You were shown what was behind door 2, because that was the only door with a prize better than door 1. 2. You were shown what was behind door 2, because both door 2 and 3 have better prizes than door 1, and the guy running the show flipped a coin. Option 2 is twice as likely as option 1, hence you are ever so slightly better off switching (on average). If we move to a continuous distribution, we can still pretend that it is a discontinuous-ordinal distribution, so the same logic works. If I tell you that a second random number was larger than the first... you are better off guessing that a third random number will also be better than the first. The actual shape of the distribution will determine how big an advantage you receive, but there will be an advantage no matter what. P.P.S. Thanks Shawn for your explanation, and Russ for mentioning dear old Monte. On Thu, Jun 9, 2011 01:52 PM, Sarbajit Roy <[hidden email]> wrote: Eric Charles Professional Student and Assistant Professor of Psychology Penn State University Altoona, PA 16601 ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
|
|
Errr.... guys? You might want to check the paper. It isn't three random numbers. It's two numbers written by a human opponent and a random number. A somewhat different scenario...
—R On Thu, Jun 9, 2011 at 12:39 PM, ERIC P. CHARLES <[hidden email]> wrote:
============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
|
|
Yesterday I asked whether it was easy to prove that two numbers picked at random (uniformly from the same range) will straddle the middle of the range with a 50% probability. The answer is that it is easy to prove.
Suppose that one selects a point x in the range such that the probability of picking a number below x is p and the probability of picking a number above x is 1-p. (If one is talking about the middle of the range p = 0.5) The probability of picking two numbers below x is p^2. The probability of picking two numbers x is (1-p)^2. So the probability of picking two numbers that don't straddle x is p^2 + (1-p)^2 which is 2p^2 - 2p +1. The probability of picking two numbers that straddle x is 1-2p^2 +2p -1 = 2p(1-p), which is 0.5 when p = 0.5, i.e., when x is the middle of the range. -- Russ Abbott _____________________________________________ Professor, Computer Science California State University, Los Angeles Google voice: 747-999-5105 blog: http://russabbott.blogspot.com/ vita: http://sites.google.com/site/russabbott/ _____________________________________________ On Thu, Jun 9, 2011 at 9:40 PM, Russ Abbott <[hidden email]> wrote:
============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
|
|
In reply to this post by Robert Holmes
I do not understand your explanation of why your experiment supports the stopping rule. But I would be curious as to what results you get if you try the following 2 experiments: x <- runif(1000) # generate 1000 random numbers from a uniform distribution y <- runif(1000) # generate 1000 random numbers from a uniform distribution z <- runif(1000) # generate 1000 random numbers from a uniform distribution A <- y < pmin(x, z) B <- y > pmax(x, z) print(sum(A)) print(sum(B)) I would expect comparable statistics. Joe Spinden On 6/9/11 10:40 PM, Russ Abbott wrote:
-- "Sunlight is the best disinfectant." -- Supreme Court Justice Louis D. Brandeis, 1913. ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
|
|
Right. Each is about 333.
-- Russ Abbott _____________________________________________
Professor, Computer Science California State University, Los Angeles Google voice: 747-999-5105 blog: http://russabbott.blogspot.com/ vita: http://sites.google.com/site/russabbott/ _____________________________________________ On Fri, Jun 10, 2011 at 8:03 PM, joseph spinden <[hidden email]> wrote: x <- runif(1000) # generate 1000 random numbers from a uniform distribution y <- runif(1000) # generate 1000 random numbers from a uniform distribution z <- runif(1000) # generate 1000 random numbers from a uniform distributionA <- y < pmin(x, z) B <- y > pmax(x, z) print(sum(A)) print(sum(B)) ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
|
|
Is that an experimental result, or what you think it should be ?
Joe On 6/10/11 11:42 PM, Russ Abbott wrote:
-- "Sunlight is the best disinfectant." -- Supreme Court Justice Louis D. Brandeis, 1913. ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
|
|
The numbers I sent are experimental results. But it's easy to show that if one picks three numbers at random, the probability that the third will be greater (smaller) than the other two is 1/3. The argument is similar to the argument about the middle number.
For any three numbers one of them must be the largest -- assuming that we are not allowing two of them to be equal. Each of the three numbers has an equal chance of being that largest number. Hence the third number has a 1/3 chance. Similarly it has a 1/3 chance of being the smallest.
Is that too facile an argument? Is there a mathematician out there who can say whether that is sufficient? -- Russ
On Sat, Jun 11, 2011 at 12:43 PM, joseph spinden <[hidden email]> wrote:
============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
|
|
In any case, I agree the probability is 1/3, as long as you are randomly sampling from a uniform distribution. Given your program, it would have been surprising if the "experimental" results did not approximate 1/3. But that is due to the program. I do not understand why you think the program illustrates a stopping rule or strategy. Perhaps if you stated the stopping rule or strategy explicitly in terms of your program, it would be clearer to me. Joe On 6/11/11 7:32 PM, Russ Abbott wrote:
-- "Sunlight is the best disinfectant." -- Supreme Court Justice Louis D. Brandeis, 1913. ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
«
Return to Friam
|
1 view|%1 views
| Free forum by Nabble | Edit this page |