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?

  • 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 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 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 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 at 13:39
  • 1
    $\begingroup$ See en.wikipedia.org/wiki/Entropy_encoding. $\endgroup$ – whuber Jul 24 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.