Random selection by coin toss I have 81 episodes of Midsomer Murders. I have watched them all, so I like to pick one "at random" to watch now. Can I randomly select one by dividing them in half over and over, flipping a coin each time to pick which half to keep until I get down to one? If I get an odd number at any stage, because I'm not fussy about the arithmetic, I just let one half be one larger than the other. I had been assigning heads to the lower half every time, but it occurred to me that in order to get episode 1, I'd have had to flip six heads in a row. So, I started letting heads be the upper half every other toss. My problem is that this is starting to feel like voodoo because I can't get my head around the problem, like Rosencrantz (or was it the other one?). Can I select an episode at random with coin tosses, and if so, how?
 A: If you flip your coin 7 times the result can be thought of as a random binary number between 1 and 128. (As you have more than 64 episodes you will in fact need the 7th flip). If you are lucky enough to obtain a number in your desired range of 1 to 81 then you have randomly selected your episode. If you do not then hopefully you have a lot of time and can repeat the above process until you get a result in the desired range.
A: If you flip a coin up to $n$ times, you can select among any number
of possible outcomes up to $2^n$, but the probability of each outcome
will be some integer multiple of $\left(\frac12\right)^n$.
The number $81$ is not an integer multiple of $\left(\frac12\right)^n$
for any integer $n$, so in selecting the next episode that you will watch,
you must either accept that some episodes will be more likely to be chosen
than others, or you must accept a procedure that relies on an
unbounded number of tosses of the coin.
(With probability $1$, such a procedure will eventually select an episode,
but there is at least a small non-zero probability that you will have
to flip the coin a very large number of times.)
If you intend to keep watching additional episodes, however,
you can equalize the likelihood of each episode in the long run,
even though you flip the coin only six or seven times to make each selection.
Each time you want to watch another episode at random, always follow
the same procedure for assigning the larger half when you have an
odd number of episodes to choose among.
But after you have watched one episode, when you want to choose the
one to watch next, treat episode $1$ as if it came after episode $81$.
That is, episode $1$ will be in the "upper" half of the episodes
(along with episode $81$) until it is either selected or eliminated.
For the third watching, treat episodes $1$ and $2$ as if they came
after episode $81$, in that sequence.
Each time you want to watch an episode, take the "first" episode in the
sequence you used last time, and make it the new "last" episode.
It will still be the case that each time you select an episode,
some episodes will be more likely than others to be selected;
specifically, there will be $47$ episodes that each have
$\frac{1}{64}$ chance to be selected, and an additional
$34$ episodes each of which has a $\frac{1}{128}$ chance to be selected.
But on average, over the course of $81$ watchings, episode $1$ will have
a $\frac{1}{64}$ chance to be selected on each of $47$ separate occasions,
and a $\frac{1}{128}$ chance to be selected on each of $34$ separate
occasions, so the expected number of times you will watch it is exactly $1$;
and the same is true for every other episode.
