Coin Flips and Dice Rolls

Trivial Cases
We want to simulate an $n$-sided die by flipping a biased coin. Our goal is to simultaneously minimize the number of coins and flips. If $n=1$ we don't need any flips. If $n=2^k$ we only need to flip a fair coin $\log n$ times.


Using 1 Coin
Interestingly, you can simulate an $n$-sided die using only 1 coin and $\,3 \log n\,$ flips. The only caveat is that I can't give you the bias of the coin explicitly. Suppose we have a coin with bias $b$. We have $n$ numbered bins and we want to map each individual sequence of $f$ flips to a bin such that each bin has probability $1/n$. There are ${f \choose k}$ sequences that have $k$ heads. For each $k$, we map $\left\lfloor {f \choose k}(n-1)^{-1} \right\rfloor$ of these to the first $n-1$ bins, and put the remainder in the last bin. By construction, the first $n-1$ bins have the same probability, so it remains to show that the last bin is filled to $1/n$. Let $R(b)$ be the probability of the last bin. Then
$$
\begin{align}
R(b) &= \sum_{k=0}^f r_k \; b^k \; (1-b)^{f-k} \\ & \\
r_k &= \small{{f \choose k} \;\; (\text{mod } n-1)}
\end{align}
$$
We have $\,R(0) = 1\,$ and if we take $f$ large enough such that $\,R(1/2)<1/n$, then by continuity and the intermediate value theorem there must be a $b'$ such that $\,R(b') = 1/n$. Noting the bound $\,R(1/2) < 2^{-f} f n\,$ we find that $\,f-\log f > 2 \log n\,$ implies $\,R(1/2) < 1/n$. Choosing $\,f = 3\log n\,$ satisfies the inequality and we are done.

We can make this prettier if we don't care about minimizing $f$. Suppose $n$ is one more than an odd prime and let $f=n-1$. Then there are no remainders since $n-1 \choose k$ is always a multiple of $n-1$. Thus $R(b) = b^{n-1} + (1-b)^{n-1}$ which clearly has a solution $R(b) = 1/n$. For cases where $n$ is not one more than an odd prime, use Dirichlet's Theorem to get a multiple of $n$ that is.



Using 2 Coins
The best I can do with two coins is $\sim 2\log n$ flips. Let one coin be fair and one coin have bias $1/n$. Let $f$ be such that $2^f \geq (n-1)^2$. Flip the fair coin $f$ times and the $1/n$ coin once. There are $2^{f+1}$ total outcomes, half of which have probability $\tfrac{1}{ 2^fn}$ and the other half have probability $\tfrac{n-1}{2^f n}$. Label the former $L$ and the latter $H$. We want to group these outcomes into bins of probability $\tfrac{2^f}{2^fn}$.

Add as many $H$ outcomes as possible to the first bin and denote the number $h_1 \geq n-1$. Fill the remainder with $t_1 < n-1 $ of the $T$ outcomes. Repeat for the next bin, and then the next, and so on. Because $h_i>t_i$, we run out of $H$ outcomes first and can fill the remaining bins with $L$ outcomes.



Remarks
A few more interesting observations. Let $F(n)$ be the minimum number of flips needed using a mutable coin (you can change the bias every flip). If $n=ab$, then we can "roll" an $a$ and $b$-sided die and take the result $b (r_a -1) + r_b$. Also, if $n = a+b$, then we flip an $a/n$-biased coin and then roll either an $a$ or $b$-sided die depending on whether the coin flip came up heads or tails. So we get the recurrence relations

$$ \begin{align}
F(ab) &\leq F(a) + F(b) \\ \; \\
F(a+b) &\leq 1 + \text{max}\{F(a), F(b)\} \\
\end{align}
$$

The second relation let's us simulate an $n=2^k + 2^{\ell}_{(k > \ell)}$-sided die using 2 coins and $k+1$ flips.


_________________________________________________________________________________

Counting Trees with Subtrees

Suppose we want to count the number of binary trees that contain exactly $k$ distinct subtrees. A recent Stack Exchange thread asked this question and with the help of two other users I wrote a post describing a few methods of enumeration (see link). We submitted the sequence to OEIS and it was just recently approved.


_________________________________________________________________________________

The Four Color Theorem

The four color theorem states that no more than four colors are required to color the countries of a map so that no two adjacent countries share the same color. To gain an intuition for why this is true, lets try to construct a counterexample

                              

In the left picture we have four countries Red, Blue, Yellow, and Black. We must add the fifth country Green such that all countries touch all other countries. However, we notice that if Green is adjacent to Red, Blue and Yellow, then no matter how we draw it, it encloses a country thereby disconnecting it from Black. An example is shown in the picture on the right where Yellow becomes disconnected from Black (and so you can color them the same color). This seems like it would be an easy theorem to prove using some sort of topological argument, however the only known proofs rely on the aid of a computer. The Supreme Fascist remains unforthcoming.


If you construct a graph by turning each face into a vertex you can rephrase the four color theorem as a statement of vertex colorings of planar graphs. For a graph to be 4-colorable, it is certainly necessary that it not contain a $K_5$ subgraph. But is this condition sufficient? The answer is no, and here is a counterexample

This graph has a chromatic number of 5 but it does not have a $K_5$ subgraph. It also does not contain a subdivision of $K_5$, so it also serves as a counterexample to Hajós' conjecture (first disproved by Catlin in 1979). On the other hand, by contracting both red--pink edges we find that $K_5$ is a minor of this graph, so Hadwiger's conjecture still stands.

_________________________________________________________________________________