Nov 17, 2023
From Raven Deerwater comes a metapuzzle of coin flipping: If you flip three (independent) fair coins, there are four possible outcomes: You can get three heads, with a probability of 1/8. You can get two heads, with a probability of 3/8. You can get one heads, with a probability of 3/8. You can get zero heads, with a probability of 1/8. Now suppose you are flipping three coins, and you do this eight times. What is the probability that you’ll get exactly one occurrence of three heads, three occurrences of two heads, three occurrences of one heads, and one occurrence of zero heads? (Note that these eight occurrences can happen in any order.)
Extra Credit
Again, suppose you are flipping three fair and independent coins, and you do this eight times. Among the four possible outcomes (three heads, two heads, one heads, zero heads), the outcome that happens to occur most frequently—but, importantly, I’m not saying which one this is!—occurs a times. The next most frequent outcome occurs b times. The next most frequent after that occurs c times. And the least frequent occurs d times. Note that a+b+c+d = 8, and that a ≥ b ≥ c ≥ d. (Yes, equalities are allowed here). Which ordered quadruple (a, b, c, d) is most likely?
Original puzzle: \(\frac{25515}{524288} \approx 4.9\%\)
Extra Credit: (4, 3, 1, 0) most likely at around 17%
Explanation:
For the original problem, let X be a random variable denoting one of the 165 possible outcomes of the experiment described in the puzzle. Why there are 165 I will explain later. For example, one outcome could be X = (1, 3, 3, 1). That is, we had one occurrence of 3H, 3 occurrences of 2H, 3 occurrences 1H, and 1 occurrence of 0H in our one experiment.
Now, it turns out that X is actually a random variable following a multinomial distribution. Its PMF is as follows:
\begin{align} &P(X = (x_1, x_2, x_3, x_4)) \\ \\ & = \frac{8!}{x_1! x_2! x_3! x_4!} \left(\frac{1}{8}\right)^{x_1} \left(\frac{3}{8}\right)^{x_2} \left(\frac{3}{8}\right)^{x_3} \left(\frac{1}{8}\right)^{x_4} \\ \end{align}
Therefore:
\begin{align} &P(X = (1, 3, 3, 1)) \\ \\ & = \frac{8!}{1! 3! 3! 1!} \left(\frac{1}{8}\right)^{1} \left(\frac{3}{8}\right)^{3} \left(\frac{3}{8}\right)^{3} \left(\frac{1}{8}\right)^{1} \\ \\ &= 1120 \times 729 / 16777216 \\ \\ &= \boxed{\frac{25515}{524288}} \\ \\ &\approx 0.049 \\ \end{align}
Therefore, despite the outcome aligning with expectation, there is still approximately only 4.9% chance that this particular outcome actually realizing.
In a string of 8 tosses, we can have the four distinct outcomes occuring in any frequency (a, b, c, d) so long as a + b + c + d = 8 and a, b, c, d being non-negative. The total number of possible outcomes for X is the same as asking how many ways in which we can partition 8 object into four distinct bins, where a bin can be empty. This is equivalent to asking how many ways we can arrange 3 sticks over 11 empty slots. Why? Each stick would act as a partition of 8 remaining empty slots, where each partition is demarcated either between the edge and the closest stick or between two consecutive sticks. In short, there will be 4 partitions in total and some partition can contain zero empty slots. The total possible distinct partitions is simply \(\binom{11}{3} = 165\).
For extra credit, I used MATLAB to help me obtain an empirical answer via Monte-Carlo with 1 million simulations, where each simulation is tossing the coin 8 times and counting the frequency of each distinct outcome and arranging each outcome in descending order. After arranging for each simulation, we have a "coin profile" appearing. In this case, we will only have 15 distinct profiles, a combinatorics problem that I will leave to my curious readers to prove.
It is interesting to note that here, (4 3 1 0) is the most probable at around 0.17 (17% of all outcomes). It is vastly greater than (3 3 1 1), of which one contributing case, [1 3 3 1], is the most common occurrence. This can be explained by the fact that the above graph illustrates the most common distributions of coin toss occurrences as a whole instead of looking at specific cases. For example, (4 3 1 0) can be obtained with 4 2H, 3 1H, 1 0H, and 0 3H cases, as well as 4 1H, 3 2H, 1 0H, and 0 3H cases. (4 3 1 0) can be constructed with more individual realizations than say (3 3 1 1), which explains the seeming paradox.
Below are the raw MATLAB code in case anyone would like to reproduce the presented result.
%% Monte-Carlo 1M Simulations
numTrials = 1e6;
% Each row of the main matrix is a distinct profile
totalCoinProfile = [3 3 1 1]; % initialize to some possible profile
totalProfileCount = zeros(1, 1);
for k = 1:numTrials
fprintf('Trial: %d\n', k);
coinProfile = getCoinProfileOneTrial();
[hit, loc] = ismember(coinProfile, totalCoinProfile, 'rows');
if ~hit
totalCoinProfile = [totalCoinProfile; coinProfile]; %#ok Add profile to the main matrix
[rows, ~] = size(totalCoinProfile);
totalProfileCount(rows) = 1; % initialize the count
else
totalProfileCount(loc) = totalProfileCount(loc) + 1;
end
end
totalProfileCount = totalProfileCount/numTrials;
% For one simulation
function coinProfile = getCoinProfileOneTrial()
% Monte Carlo of one trial coin profile
% (tossing three fair coins 8 times and count number of heads showing
% up
coinProfile = zeros(1, 4); % four outcomes
% idx 1: 3H, idx 2: 2H, idx 3: 1H, idx 4: 0H
numTosses = 8;
for k = 1:numTosses
headCount = sum(rand(3, 1) < 1/2);
coinProfile(4 - headCount) = coinProfile(4 - headCount) + 1;
end
coinProfile = sort(coinProfile, 'descend');
end