Binary search on positive integer valued random variable

Question

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$.

Answer 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.