What would the probability of winning on the 1st try through 7th try of a guessing game that asks use to guess a integer from 1 – 100 and provides feedback of whether it is "higher" or "lower" than the actual integer.
For example, the random integer is 78.
I guess 50. It's low.
I then guess 75. It's low.
I then guess 88. It's high.
etc …
Obviously, the % chance to win on the first guess is 1/100 or 1%. What about the second one through 7th?
Given the probabilities, what payout structure should I use so that the "house" has a slight advantage?
(I'm trying to program a hi/lo "wager" program that allows users to bet on their selections)
Best Answer
The probability of guessing correctly on exactly the $n$-th guess is at best $\frac{2^{n-1}}{100}$. Suppose your strategy for the $n$-th guess is to guess the number $f_n(k)$ where $k$ is a string of $n-1$ $H$'s and $L$'s, and $f_n$ is a function from the set of these strings to the numbers $1-100$ that can possibly be the correct answer. Denote by $S_k$ the subset of $\{1,\ldots,100\}$ that returns the string $k$ when you apply your guessing algorithm. Then the probability of guessing correctly on precisely the $n$-th guess is $$\sum_k P(\textrm{string k returned}) \:P(\textrm{correct guess} \: | \: \textrm{string k returned}) = \sum_k \frac{|S_k|}{100} \frac{1}{|S_k|} \leq \frac{2^{n-1}}{100},$$ where we are summing over the strings $k$ that can actually occur when applying your guessing algorithm. It is easy to show that there indeed exists an algorithm that produces the optimal probabilities.