Bijections Galore

Solution 1 The key to this problem is to recognize that the probability of flipping and even number of heads and the probability of flipping an odd number of heads depends only on the existence of a singular fair coin! To see this, consider any possible sequence of flips. (eg. HTHTTTTHHHTHTHTHTTTH...).

We can make a bijection to an equally likely string TTHTTTTHHHTHTHTHTTTH... where the first head is flipped to a tail and the rest of the string remains the same. These two strings are equally likely since the first coin, has a probability $\frac{1}{2}$ of flipping heads or tails! Since the parity of even heads must flip with a single coin change, we have found a one-to-one correspondence between strings that flip an even number of heads and strings that flip and an odd number of heads. So the answer is simply $\frac{1}{2}$

Solution 2 Another way to do this problem, and similar problems without the use of fair coins is to use something known as a generating function. This is fairly technical and frankly, overpowered way to approach this problem, but it helps give insight into problems that are similar. So I am going to do something a bit strange, but after a bit of explanation, it might come to light as to why it works. Let $p_k$ be the probability that the $k^{\text{th}}$ coin flips heads. For each the $k^{\text{th}}$ coin, I will associate the binomial $x \cdot p_k + (1 - p_k)$ to it. So for instance I will associate the binomial $\frac{x}{2} + \frac{1}{2}$ to the first coin. Then, consider the polynomial formed by product of all the binomials for all the coins below:

$P(x) = \prod_{k =1}^{2018} (x \cdot p_k + (1 - p_k))$

Amazing fact : The coefficient of the $x^{i\text{th}}$ term in $P(x)$ is the probability that Ram flips $i$ heads. See if you can convince yourself as to why and check out this wiki: generating functions .

If we plug in 1 for $x$ , each individual term in the product collapses to 1 and our answer evaluates to 1. This is also equal to the sum of all the coefficients of the expanded polynomial. However, if we plug in -1, all of the odd terms in the polynomial expansion of $P(x)$ will become the negative value of their coefficient and all the even numbers will stay the same. Therefore, if we add the two values $P(1)$ and $P(-1)$ we will get twice the sum of even terms' coefficients, which is twice the probability that we flip an even number of heads! An example is shown below:

Example If we had 3 coins with probability $\frac{1}{2}$ , $\frac{1}{3}$ , and $\frac{1}{5}$ respectively. Then, $P(x)$ is:

$(\frac{x}{2} + \frac{1}{2})(\frac{x}{3} + \frac{2}{3})(\frac{x}{5} + \frac{4}{5}) = \frac{x^3}{30} + \frac{7 x^2}{30} + \frac{7x}{15} + \frac{4}{15}.$

$P(1) = 1 = \frac{1}{30} + \frac{7}{30} + \frac{7}{15} + \frac{4}{15}$ and $P(-1) = \frac{-1}{30} + \frac{7}{30} + \frac{-7}{15} + \frac{4}{15}$ . If we add them, the terms corresponding to an odd power of $x$ cancel and we are left with $P(1) + P(-1) = 2 \cdot (\frac{7}{30} + \frac{4}{15})$ , which is twice the probability we flip an even number of heads (terms that correspond to $x^2$ and $x^0$ ).

Now that we are done with the example, we calculate the probability of flipping an even number of heads as $\frac{P(1) + P(-1)}{2} = \frac{1 + P(-1)}{2}$ . Going back to the product version of our function $P$ , we see that it $\prod_{k = 1}^{2018} (-1 \cdot p_k + (1 - p_k)) = \prod_{k = 1}^{2018} (1 - 2 \cdot p_k)$ . Here is the punchline: since the probability of flipping the first coin is $\frac{1}{2}$ , this product goes to 0, and our formula yields $\frac{1}{2}$ .

What is interesting about this formula and the product that we developed for $P(-1)$ is that it reveals something deep about these problems in general. The generating function was only up to the value 2018 because we only had 2018 coins. Suppose we made the number of coins arbitrary (with a value $n$ ). In this case, our generating function would be:

$P(x) = \prod_{k =1}^{n} (x \cdot p_k + (1 - p_k))$

Amazing Fact 2: As long as the probability of flipping heads is between 0 and 1 for each coin, each term in our product formula for $P(-1) = \prod_{k = 1}^{n} (1 - 2 \cdot p_k)$ would be between -1 and 1, which means that we are continually multiplying by a number whose absolute value is less than 1. This means that this product gets continually closer to 0 as this number as $n \to \infty$ even if we guarantee not to include any fair coins! So, as the number of coins increases, the probability tends towards $\frac{1}{2}$ .

Ram can flip the coins in whatever order he wants without changing the answer to the problem. Let's say that that he's flipped all of the coins except for the single fair coin that he has. Whether he has an even or odd number of heads so far, the fair coin will make it a 50/50 whether there is an even or odd number after the last flip.

Let's assume Ram has N coins.

Let him flip the 2th-Nth coins first and throw the first coin at last, this won't change the probability.

Assume the probability of Ram flips 2th-Nth coins an odd number $P_o$ , an even number $P_e$ .

Assume the total probability of Ram flips 1th-Nth coins an odd number ${P_o}^{'}$ , an even number ${P_e}^{'}$ .

${P_o}^{'}=\frac{1}{2}P_o+\frac{1}{2}P_e$

${P_e}^{'}=\frac{1}{2}P_o+\frac{1}{2}P_e$

${P_e}^{'}+{P_o}^{'}=1$

Now you can see ${P_o}^{'}=\frac{1}{2}$ .

If we think in reverse order of the sequence of coins, the solution is very simple.

Let P1 denote the probability in question.

Let P2 denote the probability of flipping an even number of heads among the last 2017 coins after the first one in the sequence; thus 1-P2 denotes the probability of flipping an odd number of heads among the last 2017 coins.

Thus P1 = (1-P2) * probability of flipping the first coin head + P2 * probability of flipping the first coin tail

= (1-P2) (1/2) + P2 (1/2) = 1/2.

Here's a slightly different solution: Let us say that the $i^th$ coin has a probability of $\frac{1}{i}$ of landing heads. Obviously, the probability of it landing tails would be $1-\frac{1}{i}$ . Let us consider the sum $\frac{(2017-1)(2016-1)(2015-1)...(3-1)(2-1)(1-1)}{2018!}$ .

This would be equal to P(even heads)-P(odd heads), as every term which turns out to be positive in the numerator contains $frac{1}{i}$ an even number of times, and every negative term contains an odd number of heads. As is obvious, the above expression yields $0$ . Hence, P(even heads)=P(odd heads).

The chance is of adding +1 head is determined by p(k) on top of p(k+1) Since p(1) = 2 the chance of first coin is 50%. In this case it doesn't matter what chance p(2) .. p(n) yields for even, there is always a 50% to flip it from one way or the other.

Assume we throw the coins in order, so that the nth coin has a heads-probability of $1/\pi[n]$ where $\pi[n]$ is the nth prime.

Let $P[n]$ be the probability of having an even number of heads after throwing the nth coin. Then, we can establish the following recurrence relation:

$P[n]=\frac{1}{\pi[n]}(1-P[n-1])+(1-\frac{1}{\pi[n]})P[n-1]$ .

The equation can be explained as follows:

Left side: probability of having an even number of heads at step n. Right side, first term: multiply the probability of having an odd number of heads at step n-1 by the probability of getting heads at step n. Right side, second term: multiply the probability of having an even number of heads at step n-1 by the probability of getting tails at step n.

We can rearrange the expression as:

$P[n]=P[n-1]+\frac{(1-2P[n-1])}{\pi[n]}$

Now, we know that $P[1]$ is the probability of obtaining an even number of heads after just one throw. This means the probability of getting tails. We simply get $P[1]=1/2$ . Now let's try P[2], and focus on the term $(1-2P[n-1])$ which is clearly 0. Then, $P[2]=P[1]$ . You can iterate as many times as you want and get $P[n]=P[n-1]$ , so for any value of n you get a 1/2 probability of an even number of heads.

Not a solution, but curious nonetheless...

By writing a program in java to test the probability, I got (approximately) the correct answer of 1/2.

Doing the same thing with random probabilities instead of probability 1/p(k) gave the same answer of 1/2.

Doing it again, guaranteeing there was no coin probability of 1/2, gave me the same answer of 1/2.

This tells me that the coin bias doesn’t matter; the probability of an even number of heads, with 2018 coins, will always be 1/2.