Past exam of the mathematics course of the University of Cambridge / 2009 / ii / Paper 1 / 4H / iii

The procedure in part (i) sometimes needs five tests, for items one or two. A binary decision tree of height $N$ has at most $2^N$ leaves, so distinguishing ten possibilities requires $N\ge \lceil {\log }_{2}10\rceil =4$.

A prefix code attaining this worst-case bound isUse the same subset-testing rule. The minimum worst-case number is four, so the expected-optimal procedure is not worst-case optimal. This four-test procedure has expectation $175/55$, illustrating the small cost of imposing the smaller maximum depth.