How to assign 3 rooms to 3 people with 1 coin randomly?

Question

We are 3 friends; just checked into an airbnb flat with 3 rooms. And to make things truly random we decided to use 1 coin to assign each person a room. What's the best way to do this? (Assuming coin flip is truly random.) (One way to define 'best' is minimum number of flips)

Answer 1

Each of you pick one of the following

$$HH,HT,TH,TT$$

Flip a coin twice and whoevers sequence is flipped gets their choice of room. If none of the sequences you picked are flipped ($25\%$ chance), then flip again. Next, go down the line above and whoevers sequence is next gets to pick their room next. For example, suppose I picked $TH$ while my friend picked $HT$. We flip a coin twice and it outputs $HT$. Then they would pick first, and I would pick second. If $TT$ is outputted then loop around to $HH$. Obviously, the third person gets the last room. The expected number of coin flips is

$$2\left(1+\frac{1}{4}+\frac{1}{16}+\frac{1}{64}+\cdots\right)=2\sum_{i=0}^\infty \frac{1}{4^i}=2\frac{4}{3}=\frac{8}{3}=2.\overline{6}$$

Answer 2

Since there are six possible outcomes with equal probability, you'd b bettre off with a die, and unfortunately, the number of coin tosses cannot be bounded: With at most $k$ tosses, you can only define probabilities of the form $\frac m{2^k}$.

However, there is a nice(?) method for even more general probabilities: Start an infinite sequence of coin tosses (but don't worry, we will almost surely stop after just a few tosses) and interpret the outcomes as infinite binary number. So e.g. $HHTHHTHHHHTTTTTTHTTH\ldots$ becomes the binary number $.00100100001111110110\ldots$. Already with these 20 tosses, it is clear that our number is approximately $0.1415926\ldots$ in decimal. Now we assign the intervals $[0,\frac16)$, $[\frac16,\frac13)$, $[\frac13,\frac12)$, $[\frac12,\frac23)$, $[\frac23,\frac56)$, $[\frac56,1]$ so that each interval has length $\frac16$ (or whatever probabilty we want); also, it typically does not really matter if we assign the boundary points to the lower or upper interval. As $\frac16$ is $.0010101\ldots$ in binary, it is clear that our generated random number is $\in[0,\frac16)$ and hence we take the first of the six possible outcomes. Actually, we did way too much for the sake of insight into the example: Already after five tosses $HHTHH$, it is clear that our number will end up $\in[0,\frac16)$, hence we could have stopped there (but not earlier).