A box full of unfair coins

Question

Lolek and Bolek are arguing on whose turn is to take out the trash.

They have a box with $n$ coins. when the coin $i$ is thrown, the probability that it lands on heads is $p_i$.

They decided to make a game: they throw all the $n$ coins and count how many heads they get. If they get an odd number of heads it's Lolek's turn to take out the trash, otherwise it's Bolek's turn.

Given the values for $n$ and for each $p_i$ how can you tell whether the game is fair or not?

Source: this ipsc problem: https://ipsc.ksp.sk/2012/real/problems/f.html

For the ones who downvoted: this is not a textbook-style problem. I am searching for an efficient algorithmic procedure that, given the set of coins, tells whether the game is fair or not. I'm not searching for a long formula that depends on $n$ and $p_i$

Answer 1

A set of coins is fair in the relevant sense if and only if

at least one of them comes up heads with probability exactly 1/2.

Proof (slightly highbrow, sorry):

Consider the product, over all the coins, of $(pX-(1-p))$. The coefficient of $X^n$ in this is the probability of getting exactly $n$ heads. So if we set $X=-1$ we get the expectation of a value that's $+1$ if we have an even number of heads and $-1$ if not; our coins are fair iff this value is zero. This value is the product of $2p-1$, and is zero iff one of the factors is zero.

Alternative kinda-equivalent proof (simpler ideas but needs you to know a theorem):

Let $X_i$ be the random variable that's $\pm1$ depending on which way coin $i$ comes up. The product of all these is $\pm1$ depending on the parity of the number of heads. So odd and even are equally likely iff the expectation is 0. But the expectation of a product of independent random variables equals the product of their expectations, so odd and even are equally likely iff the product of the expectations of the $X_i$ is 0. And the expectation of $X_i$ is zero iff coin $i$ is equally likely to come up heads or tails.

(Neil W suggested, in comments, taking that second approach. I'd avoided it because the other way seemed quicker and more first-principles-y, but the second way may well be easier to follow and/or easier to grasp intuitively.)

Answer 2

Same answer, different proof.

The only way the game can be fair is if one or more of the coins is fair, i.e. $\exists i | p_i = 0.5$. If any coin is fair, the game must be fair.

Proof by induction on $n$.

Obviously, this is true for $n=1$, as there is only the one coin.

Then assume it is true for all $k: 1 \leq k \leq n-1$.

Let $q$ be the probability that flipping coins $1$ through $n-1$ yields an odd number of heads. Define the function $f$ to be the probability that flipping all the coins yields an odd number of heads, as a funciton of $p_{n}$ The probability that the game is fair is now:
$$ f(p_n) = p_n q + (1-p_n)(1-q) = 1 - p_n - q + 2p_nq $$

Obviously:

If either $p_n = \frac12$ or $q=\frac12$, then $f(p+n) = \frac12$ and the game is fair. The derivative of $f$ is:

$$f'(p_n) = \frac{d f(p_n)}{d p_n} = -1 + 2q$$

Clearly,

This only has a zero if $q = \frac12$, in which case it is alyways zero. Thus, if $q \neq \frac12$, then there can be only one value of $f(p_n)$ which is equal to $\frac12$, and that is when $p_n = \frac12$. Ergo, the game is fair if and only if either $p_n = \frac12$ or $q=\frac12$. Per the assumption, $q=\frac12$ implies that one of the first $n-1$ coins is fair.
Thus, we have shown that the statement is true for $n=1$ and that truth for all values of $k: 1 \leq k \leq n=-1$ implies it must be true for $n$. This completes the proof by induction.

QED

Answer 3

Given the wording of "whose turn it is", we are left to assume that taking out the trash will be a recurring event. In this way, we can guarantee fairness regardless of $n$ and $p_i$ by simply recording who did it last and alternating each time.

The coin flipping only needs to occur for the very first time, but on a sufficiently large timeline, one sample will not affect the overall fairness of the system.