Intereting Posts

A differentiable manifold of class $\mathcal{C}^{r}$ tangent to $E^{\pm}$ and representable as graph
Proof of lack of pure prime producing polynomials.
Is it always true that $\det(A^2+B^2)\geq0$?
How do we justify functions on the Ordinals
How prove this $\frac{a}{(bc-a^2)^2}+\frac{b}{(ca-b^2)^2}+\frac{c}{(ab-c^2)^2}=0$
Show that an integral domain with finitely many ideals is a field
Errors in math research papers
$3\times3$ linear system organization
Product rule for logarithms works on any non-zero value?
Integral domain without prime elements which is not a field
Cantor set: Lebesgue measure and uncountability
How does one calculate the amount of time required for computation?
Can a quotient field ever be finitely generated as an algebra?
Why is the generalized quaternion group $Q_n$ not a semi-direct product?
How to show set of all bounded, analytic function forms a Banach space?

There is a game where you get to pick a number between 1 and 1000 and then the system will tell if you guessed to high or too low. Using a binary search you can find the answer in a maximum of ten guesses (2^10 = 1024) , but how would I go about calculating the average number of guesses required to guess the given method, assuming the user uses this binary chop method?

- How to find $E(X_1X_2X_3)$ given the joint CDF?
- How to get started on this statistics problem?
- Do the lengths of all three segments necessarily have the same distribution?
- Probability of rolling 6 when throwing k dice one by one vs all at once.
- Filled suit vs. triple quads, which is more likely to happen first on average?
- Evaluating the distribution involving a Brownian motion.
- Expectation of an Absolute Value that is the Standard Normal?
- Is this urn puzzle solvable?
- Joint density function of X and X+Y, standard normal random variables
- Probability of a certain ball drawn from one box given that other balls were drawn

Let us take the more ideal case of guessing integers between $1$ and $2^{10}-1=1111111111_2$ writing in base $2$ from now on without explicitly writing subscript $2$ each time. Then the algorithm for the guesses will be like this:

- The initial guess is $1\overline 0$ where $\overline 0$ means fill up with zeros until we have a ten digit number
- Write the $n$-th guess as $g_n=x_n1\overline 0$ where $x_n$ is a binary string of length $(n-1)$
- If the game responds by “higher”, the next guess is $g_{n+1}=x_n11\overline 0$
- If the game responds by “lower”, the next guess is $g_{n+1}=x_n01\overline 0$
- If the game responds by “correct” we are done after $n$ guesses

So we see that the game terminates whenever there are only zeros remaining right of $x_n1$. Then note that there are $2^{n-1}$ binary strings $x_n$ of length $(n-1)$. So $2^{n-1}$ numbers are guessed after exactly $n$ guesses. So for this setup the expected number of guesses will be, returning to writing in base $10$:

$$

\frac{1}{2^{10}-1}\sum_{n=1}^{10}n\cdot 2^{n-1}=\frac{9217}{1023}\approx9.00978

$$

So the average case here is very close to the worst case of $10$ guesses. This could seem odd at first, but *odd* is also the clue here … Half of the time it takes $10$ guesses to reveal that the randomly picked number $x$ is in fact odd. The first $9$ guesses fills up with zeros which in base $2$ means “divisible by $2$”. One quarter of the time $x$ is divisible by $2^2=4$ forcing the algorithm to make $9$ guesses before succes. And so on.

I wrote the following code in Python:

```
L=[1,1000]
G={}
for n in range(1,11):
i=0
while i<len(L)-1:
guess = int(0.5*(L[i]+L[i+1]+1))
if guess not in L:
L = L[:i+1]+[guess]+L[i+1:]
i+=1
G[guess] = n
i+=1
S=0
for g in G:
S+=G[g]
print (10+S+10)
```

which responded with $8987$, so the average for the $1$ to $1000$ case, assuming that we always make the guess of the rounded average of the limits of the interval we know that $x$ belongs to, must be $8.987$ guesses.

Let $c$ be the target number somewhere between lower bound $1$ and upper bound $n$, inclusive. We will search at the value $M = \lceil\frac{n}{2}\rceil$. If we’re told that the guess is too high, we will set $n=M-1$ and try the search again. Otherwise, we will set the lower bound to $M+1$ and search again. However, what really matters is $c$’s position relative to the bounds, so this is also the same as starting a new search with lower bound $1$ and upper bound $n-M$ with a new target number $c-M$.

This recursive process ends in two possible ways: We either stop when we find the target number, or we stop if the lower and upper bounds are the same (in which case only one search is performed).

Let $F(n)$ represent the expected number of searches needed to find the unknown target number, where $F(0) = 0$ and $F(1) = 1$.

Overall, there is a $\frac{M-1}{n}$ probability that $c < M$, a $\frac{1}{n}$ probability that $c=M$, and a $\frac{n-M}{n}$ probability that $c>M$.

$$F(n) = \left(\frac{M-1}{n}\right)\left(1+F(M-1)\right) + \left(\frac{1}{n}\right)\left(1\right) + \left(\frac{n-M}{n}\right)\left(1+F(n-M)\right)$$

Multiply by $n$, simplify things a bit, and substitute in the full value for $M$:

$$nF(n) = \left(\left\lceil\frac{n}{2}\right\rceil-1\right)F\left(\left\lceil\frac{n}{2}\right\rceil-1\right) + n + \left(n-\left\lceil\frac{n}{2}\right\rceil\right)F\left(n-\left\lceil\frac{n}{2}\right\rceil\right)$$

Let $S(n) = nF(n)$ and $T(n) = S(n) – S(n-1)$, yielding:

$$T(n) = \left(n-\left\lceil\frac{n}{2}\right\rceil\right)F\left(n-\left\lceil\frac{n}{2}\right\rceil\right) – \left(n-\left\lceil\frac{n}{2}\right\rceil-1\right)F\left(n-\left\lceil\frac{n}{2}\right\rceil-1\right) + 1$$

Based on the definitions $S(n)$ and $T(n)$, this is equivalent to the following:

$$T(n) = S\left(n-\left\lceil\frac{n}{2}\right\rceil\right) – S\left(n-\left\lceil\frac{n}{2}\right\rceil-1\right) +1 = T\left(n-\left\lceil\frac{n}{2}\right\rceil\right)+ 1 = T\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+1$$

In other words, $T(n) = \lfloor \log_2(n)\rfloor + 1$. But we want $F(n)$, not just $T(n)$. Thankfully, since $T(n) = S(n) – S(n-1) = nF(n) – (n-1)F(n-1)$, the sum over many $T(k)$ values cancels out intermediate terms, giving us $nF(n)$. After dividing by $n$, we finally isolate $F(n)$:

$$F(n) = \frac{1}{n}\sum_{k=1}^{n} T(k) = 1 + \frac{1}{n}\sum_{k=1}^{n}\lfloor \log_2(k)\rfloor$$

This summation actually has a closed form as well:

$$F(n) = 1 + \frac{1}{n}\left((n+1)\lfloor \log_2(n)\rfloor – 2(2^{\lfloor \log_2(n)\rfloor} – 1)\right)$$

To offer a Python program in the same spirit as String’s answer:

```
from fractions import Fraction
from math import log
def F(n):
if n==0: return 0
lg = int(log(n,2))
return 1 + Fraction(1,n)*((n+1)*lg - 2*(2**lg-1))
```

For $n=1000$ the result is $\frac{8987}{1000} = 8.987$.

- Proving $\int_0^{\pi } f(x) \, \mathrm{d}x = n\pi$
- drawing at least one colored ball of each from urn in a case of large populations
- What does $\sum_{i=1}^{10} 2$ mean exactly?
- An issue with approximations of a recurrence sequence
- Can an underdetermined system have a unique solution?
- All solutions of $a+b+c=abc$ in natural numbers
- “Number of Decompositions into $k$ Powers of $p$”-Counting Functions
- Sum of stars and bars
- Verifying Touchard's Identity
- Strange Recurrence: What is it asymptotic to?
- Is $f_n$ uniformly convergent on $(0,\infty)$?
- How do you find the factorial of a decimal or negative number and what does it show us?
- How many zeroes are in 100!
- Is $\mathbb{R}$ a subset of $\mathbb{R}^2$?
- Sufficient conditions to conclude that $\lim_{a \to 0^{+}} \int_{0}^{\infty} f(x) e^{-ax} \, dx = \int_{0}^{\infty} f(x) \, dx$