Past exam of the computer science course of the University of Oxford / 2015 / Probability and computing / 3 / b / Solution

Betty's scheme is biased for every $n\ge 2$. The output $H^n{T}^n$ occurs precisely when the first $n$ tosses are heads: the algorithm stops there and appends $n$ tails. ThusFor comparison, take the output $(HT{)}^n$. Its first $2n-2$ symbols contain $n-1$ heads and $n-1$ tails, so neither stopping threshold has been reached. The next symbol is the $n$th head, at which point the last tail is appended. Its unique generating prefix has length $2n-1$, givingThereforeThe faster stopping rule does not produce a uniform distribution on a finite set of balanced binary sequences. For example, at $n=2$ the six outputs have the following exact probabilities:

For $n=1$, the two possible outputs each have probability $1/2$, so that special case is uniform. For $n=0$, simply return the empty output.