0
$\begingroup$

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?

$\endgroup$
7
  • 1
    $\begingroup$ Isolate the half of the integers with the greatest probability. First question is whether the chosen integer is one of them. $\endgroup$ – BruceET Jul 24 '20 at 3:33
  • $\begingroup$ @dynamic89 I believe you mean something like $\lceil \log_2(100)\rceil+1=7$. What you write as an equality is not. $\endgroup$ – Glen_b Jul 24 '20 at 10:50
  • $\begingroup$ @Glen_b that's exactly what I mean! Thanks! It's just from binary search. By the way I have a thought... instead of splitting the array in half, we could spilt the array at the point where the sum of the weights on the left equal to the sum of the weights on the right. However the worst case is the same as before but hopefully this is better in expectation? $\endgroup$ – dynamic89 Jul 24 '20 at 13:14
  • 1
    $\begingroup$ Entropy is your friend :-). Generally, the answer depends on how many times A can play this game and what the payoff is. Perhaps you have in mind a strategy with the smallest expected number of attempts? $\endgroup$ – whuber Jul 24 '20 at 13:39
  • 1
    $\begingroup$ See en.wikipedia.org/wiki/Entropy_encoding. $\endgroup$ – whuber Jul 24 '20 at 16:34
0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ This is on the right track, but your algorithm for constructing the code is not optimal. You need to list the probabilities in order from smallest to largest, combine the two smallest (by adding them), re-sort the list, and continue. The pattern of combinations determines branches in a binary tree with the individual probabilities at the leaves. Encode each leaf with the sequence of branches needed to reach it: that's the optimal (lowest-entropy) code that maps each input character into a single output binary string. E.g., an optimal code for $(1/6,1/4,1/4,1/3)$ is 00, 01, 10, 11. $\endgroup$ – whuber Aug 13 '20 at 18:31
  • $\begingroup$ Reference: en.wikipedia.org/wiki/Huffman_coding#Compression. $\endgroup$ – whuber Aug 13 '20 at 19:29
  • $\begingroup$ I see. coincidentally my codes have the same properties to the ones produced by huffman tree greedy method. the tree produced codes for $(1/2, 1/8, 1/16, 1/16, 1/16, 1/16, 1/16, 1/16)$, 0, 100, 1010, 1011, 1100,1101,1110,1111. the average code length is $3.5$ compared to the entropy $2.375$. The inefficiency is due to the skewed distribution perhaps. $\endgroup$ – dynamic89 Aug 13 '20 at 21:41
  • $\begingroup$ Your method worked only because your example is very special: all the probabilities are integral powers of $2.$ When I applied your top-down approach (starting with the highest probability of $1/3$) to my little example, the resulting code had a higher entropy. $\endgroup$ – whuber Aug 13 '20 at 21:44
  • $\begingroup$ ah I see what you mean. I wrote $(1/2, 1/8, 1/16, 1/16, 1/16, 1/16, 1/16, 1/16)$ but when I computed the code I started with the lowest. In your example if I start with the highest I'll have 3 digit codes. $\endgroup$ – dynamic89 Aug 13 '20 at 21:50

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.