number search optimal strategy
June 4, 2018 8:50 AM Subscribe
I recall hearing about a "golden number" when playing a number guessing game, such as "guess the selected number between 1 and 100 when after guessing you are told your guess is high or low". Most online references recommend successively dividing the remaining range in half, but i recall reading that a strategy of dividing the remaining range roughly 1/3 and 2/3 allows you to eliminate 2/3 of the range often enough that it results in less guesses on average. Anybody ever heard of this?
Best answer: Golden Section search maybe? It's not really for number search though, it's for finding the minimum of a unimodal function. Dividing an interval by the Golden Ratio has you making a cut at about 62%, or near 2/3.
posted by Nelson at 8:58 AM on June 4, 2018
posted by Nelson at 8:58 AM on June 4, 2018
Binary search is optimal unless you know something more about the distribution of numbers that you're searching over. For example, if you knew that the values were clustered around 50.
There is also uniform binary search which uses a lookup table instead of just taking the midpoint.
posted by dilaudid at 9:13 AM on June 4, 2018 [3 favorites]
There is also uniform binary search which uses a lookup table instead of just taking the midpoint.
posted by dilaudid at 9:13 AM on June 4, 2018 [3 favorites]
Binary search is optimal unless you know something more about the distribution of numbers that you're searching over. For example, if you knew that the values were clustered around 50.
There's another example of this on this Cornell prof's webpage. (I remember this example from an old Martin Gardner column, though I don't know whether it was original to him.) If you're asked to guess a card that is drawn from a deck with one Ace, two twos, three threes, and so forth up to nine nines, the first question you should ask is "is the card a four, five, or nine?"
However, if you try to perform this process for a situation in which all options have equal probability, you end up with decisions between two roughly equal groups at all stages, so an equal division algorithm is optimal.
posted by Johnny Assay at 9:39 AM on June 4, 2018
There's another example of this on this Cornell prof's webpage. (I remember this example from an old Martin Gardner column, though I don't know whether it was original to him.) If you're asked to guess a card that is drawn from a deck with one Ace, two twos, three threes, and so forth up to nine nines, the first question you should ask is "is the card a four, five, or nine?"
However, if you try to perform this process for a situation in which all options have equal probability, you end up with decisions between two roughly equal groups at all stages, so an equal division algorithm is optimal.
posted by Johnny Assay at 9:39 AM on June 4, 2018
I don't think this is quite what you're after, but your question reminded me of this 538 riddle and its solution.
posted by schroedingersgirl at 10:16 AM on June 4, 2018 [1 favorite]
posted by schroedingersgirl at 10:16 AM on June 4, 2018 [1 favorite]
If you're guessing something that is a real amount of something that can be counted, like pennies in a jar or people in a city, then if you are told LOWER -- then guessing less than half makes sense because of the logarithmic distribution of countable things, a.k.a. power law.
If you're guessing a "random" number like a die roll or number picked out of a hat or something that isn't a count, then binary search is better.
posted by seanmpuckett at 10:17 AM on June 4, 2018
If you're guessing a "random" number like a die roll or number picked out of a hat or something that isn't a count, then binary search is better.
posted by seanmpuckett at 10:17 AM on June 4, 2018
To distill the common principle behind most of these comments: If you can ask questions with a binary answer (high/low, yes/no), you generally do best by asking questions for which each answer has a 50% chance of occurring. The optimality of this strategy can be explained using the concept of informational entropy.
posted by aws17576 at 10:35 AM on June 4, 2018 [1 favorite]
posted by aws17576 at 10:35 AM on June 4, 2018 [1 favorite]
As far as the 1/3 and 2/3 breakdown is concerned, could you be thinking of the problem where a gambler is guessing at a random number between 1 and 100, and the question is 'what is the probability the gambler will not guess right even 1 time in 100 guesses?'
Because the answer in that case turns out to be very close to 1/e, which is ~1/3, which means that the probability of guessing right is ~2/3, of course.
And the more guesses you add, with the proviso that the number of guesses equals the number of numbers the gambler chooses from, the closer the answer is to 1/e, because the general term for the probability of never guessing right is (1-1/n)^n, and (1-1/n)^n converges to 1/e as n goes to infinity.
posted by jamjam at 11:24 AM on June 4, 2018
Because the answer in that case turns out to be very close to 1/e, which is ~1/3, which means that the probability of guessing right is ~2/3, of course.
And the more guesses you add, with the proviso that the number of guesses equals the number of numbers the gambler chooses from, the closer the answer is to 1/e, because the general term for the probability of never guessing right is (1-1/n)^n, and (1-1/n)^n converges to 1/e as n goes to infinity.
posted by jamjam at 11:24 AM on June 4, 2018
Your change makes the worst case slower than binary search which has a worst case of 7 with the example given, given that 2^7>100. They both have the same best case of 1.
posted by w0mbat at 6:29 PM on June 4, 2018
posted by w0mbat at 6:29 PM on June 4, 2018
« Older The dreaded "career development" conversation. | What's it like to be a guest at a medical... Newer »
This thread is closed to new comments.
posted by btfreek at 8:53 AM on June 4, 2018 [2 favorites]