# Binary search on positive integer valued random variable

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.

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.