Skip to content
Get started

Fewest yes/no questions on average

One of six suspects is guilty, with probabilities 0.40, 0.20, 0.15, 0.10, 0.10, 0.050.40,\,0.20,\,0.15,\,0.10,\,0.10,\,0.05. You may ask any yes/no question (for example "is it one of suspects 2, 4 or 5?") and get a truthful answer. Using the strategy that minimises the expected number of questions, what is that expected number?

Show hints (2)+
  1. Each strategy is a binary tree; the expected number of questions is the average leaf depth.
  2. Huffman: merge the two smallest probabilities repeatedly and add up the merged weights.

Answer

Reveal answer →

2.35 (± 0.001)

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading, Systematic & Data-Driven Trading

Related questions