Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/iii/paper-224/3/b/solution

The type class is
We first prove a multinomial-mode lemma. If has the multinomial law with parameters and an -type , then is a mode. Indeed, if and , moving one count from to changes the probability by the factor
Repeated transfers reach without decreasing probability. There are at most count vectors, so the modal vector has probability at least .
Every string in has -probability
The lemma therefore gives
and hence

New to topics? Read the docs here!