Random biased coin
Suppose we pick biased coin at random, so that tails probability $\theta$ is itself uniformly distributed on $[0, 1]$. What is the distribution of number of tails if we toss this coin $n$ times?
For specific values of $\theta$ distribution has a peak around $n\theta$.
| 0 | 1 | 2 | 3 | 4 |
| 0 | 1 | 2 | 3 | 4 |
| 0 | 1 | 2 | 3 | 4 |
What is surprising, is that if we “add up” these distributions for all values of $\theta$, we’ll get equal probabilities for all possible numbers of tails:
| 0 | 1 | 2 | 3 | 4 |
One can verify it by checking that for all $k$
\[\int_0^1 {n\choose k} \theta^{k}(1-\theta)^{n-k} \,d\theta = \frac{1}{n+1},\]but that’s boring.
Instead, consider alternative formulation of this experiment. First we pick $\theta$ uniformly. Then, instead of flipping coins, we choose values of $y_1, …, y_n$ independently and uniformly from $[0, 1]$. We say that coin $i$ produces tails iff $y_i < \theta$, which happens with probability exactly $\theta$. Then number of tails is the number of $y_i$ that fall to the left of $\theta$, or, equivalently, zero-based index of symbol $\theta$ in the sequence $\theta, y_1, …, y_n$ sorted by values of respective variables. For example, if these values can be arranged as
\[y_2 < y_3 < y_1 < \theta < y_4,\]we observe three tails.
Since all these random variables are independent and have the same continuous distribution, sorted sequence $\theta, y_1, …, y_n$ is random permutation with all possible orders being equiprobable, thus $\theta$ is equally likely to appear in any of $n + 1$ positions. \(\tag*{$\blacksquare$}\)