Let's consider a variation of the famous number-guessing game: a random integer is sampled from $0$ to $15$ with a pre-known distribution $\{P_i\}$. For each guess count, There are two ways to guess the numbers:
(1) Guess a binary digit of the random integer, and the answer will be correct/wrong. For example, if the integer to be guessed is $1$ (binary: 0001), we can check the rightmost digit is 1.
(2) Guess directly if the random integer is a given value. The answer will be correct/wrong as well and we don't know if the integer is higher or lower than our guessed value.
Question: How to determine an optimal strategy (with minimal expectation of time of guess), given the pre-known distribution of the random integer?
For more intuition, we can consider two extreme cases: If the random integer is sampled with a uniform distribution, we should definitely stick with the first binary way to guess the number. The expected time of guess in this case will be $4$. In another case, if the random integer is $99.999\%$ likely to be $0$, we should just use the second way to guess $0$ to be the correct value. The expectation will therefore be very close to $1$, as mostly we can guess the number within one shot.
Despite the number-guessing game being a frequent topic here, I failed to find a very similar variation from the previous discussion. I would appreciate if anyone can provide any thoughts or comments on this number-guessing problem.
At every moment you know some set of possible numbers. Initially it contains all $16$ numbers. The first type of guess removes up to $8$ of them, while the second one removes only $1$ or ends the game instantly. There are $2^{16}$ possible sets, that is no too much for computation. Then for each set $S$ you can compute the expectation $e(S)$ using dynamic programming.
You need to consider sets in any order guaranteeing that all subsets of the current set are already considered. (Or alternatively you can use "lazy dynamic programming", that is recursive function with memorization, but memorization is essential.)
For each set containing a single number the expectation is $0$. Let probability of getting number $x$ be $p_x$. Since considering a set $S$ we need to deal with conditional probabilities, let $p(S) = \sum\limits_{x\in S} p_x$, then conditional probability $P\{\,x \mid S\,\} = [x \in S]\cdot \frac{p_x}{p(S)}$. Also let introduce auxiliary sets $M_i$ for $i = 0, 1, 2, 3$, containing $8$ numbers each with $i$-th digit $1$. For a set $S$, containing more elements you just compute the best expectation considering every possible move: $$e(S) = \min\{\,\min_{i = 0}^3 \left(1 + \frac{p(S \cap M_i)}{p(S)}\cdot e(S \cap M_i) + \left(1 - \frac{p(S \cap M_i)}{p(S)}\right) \cdot e(S \setminus M_i)\right),\\ \min_{x \in S} \left(\frac{p_x}{p(S)} + \left(1 - \frac{p_x}{p(S)}\right)\cdot e(S \setminus \{\,x\,\})\right)\,\}.$$ Here the first inner minimum corresponds to moves of the first type, and the second one corresponds to moves of the second type.
Note that for the empty set there is no solution, but we will multiply $e(\varnothing)$ by $0$ in our formula. So it could be any finite number.
If possible numbers are $0, 1, \ldots, n - 1$, then the total running time is $\mathrm O(2^n\cdot n)$, if you precompute all $p(S)$.