guessing a number between 1 and 100 Person A chooses an integer between 1 and 100 at random, then B can guess that number in (at most) 7 attempts, i.e. $\log_2(100)+1=7$. What if now A chooses an integer from a distribution that is known to B (B knows the probability of each number being selected but does not know the number). Can B use this extra information to guess that number in fewer attempts? What would be the best strategy here?
 A: Thanks to whuber's suggestions. I think the problem can be solved as follows. For simplicity let's assume there are eight numbers $1,\cdots,8$, picked with probabilities $1/2, 1/8, 1/16, 1/16, 1/16, 1/16, 1/16, 1/16$. We can encode the numbers as follows.
\begin{align}
&1:1,\>\>\>{\rm entropy}=8/16\\
&2:011,\>\>\>{\rm entropy}=6/16\\
&3:0100,\>\>\>{\rm entropy}=4/16\\
&4:0101,\>\>\>{\rm entropy}=4/16\\
&5:0010,\>\>\>{\rm entropy}=4/16\\
&6:0001,\>\>\>{\rm entropy}=4/16\\
&7:0000,\>\>\>{\rm entropy}=4/16\\
&8:0011,\>\>\>{\rm entropy}=4/16\\
\end{align}
since 1 has the biggest entropy, the first question I ask is "is the first digit 1", because this question gives the biggest information gain, if the answer is yes then we guessed the number, if no, next question I ask if the second digit $1$ and so on. So the expected number of questions asked to guess the number is the entropy $2.375$.
In the case where the probabilities are all equal, every question asked can get rid of half of the numbers, so that's binary search.
