Let $X$ be a random variable taking values in $\{1,2,3,...\}$ and $\mathbb{E}(X)<+\infty$. $A$ has a realization of $X$. $B$ wants to guess what value does $A$ have and $B$ knows the distribution of $X$. Every time, $B$ can ask a yes or no question about the value $A$ has. $B$ decides to use binary search. Let $m_1$ be the median of $X$.

First, $B$ asks: is the value smaller than $m_1$? Then based on the answer, $B$ proceeds with the conditional median. So on and so fourth until $B$ knows exactly what the value is. The question is, what's the expected number of questions $B$ needs to ask using this binary search method? Is this strategy optimal?

As a concrete example, let $\mathbb{P}(X=k)=(1-p)^{k-1}p$ where $0<p<1$.


No, this strategy will not necessarily be optimal, though I think this is just due to "rounding effects" and it will always be close to optimal. A case where it isn't optimal: $2$ and $3$ have large probabilities $\frac12-\frac\epsilon2$, and $1$ has a small probability $\epsilon$. The median is $2$, but it's certainly not optimal to first ask whether the value is less than $2$.

The order on $\mathbb N$ is actually irrelevant to what you're doing; you should consider more general subsets than intervals. If you want to find a truly optimal strategy, this might lead to some knapsack-like problem where you try to build subsets of similar mass.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.