9
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ In what way is this a puzzle? In the source it’s not even a math problem, it’s a computing exercise. Determining fairness of the game from the probabilities of each coin is a purely mechanical task, not at all a puzzle. $\endgroup$ – Rubio Dec 6 '19 at 17:22
  • 2
    $\begingroup$ The naive mechanical way to do it is really expensive if you have a large number of coins, and if you want to tell exactly for arbitrary $p_i$ then it requires arbitrary-precision arithmetic. $\endgroup$ – Gareth McCaughan Dec 6 '19 at 17:28
  • $\begingroup$ But if you're clever about it then there's a very efficient solution that doesn't require arithmetic with any more precision than the numbers you get as input. So there kinda is a puzzly element. $\endgroup$ – Gareth McCaughan Dec 6 '19 at 17:29
  • $\begingroup$ I don't think so. I am looking for a solution that works for every set of coins, and rot13 (Vg qbrf abg vaibyir nal pbzchgngvba ng nyy). Ninjed: I agree with @gareth $\endgroup$ – melfnt Dec 6 '19 at 17:31
  • 1
    $\begingroup$ (The original question goes one step further: they ask not "is this set of coins fair?" but "here's a big set of coins; how many subsets of that set of coins are fair?". Again, unfeasibly large amounts of computation needed if you do it naively, but if you understand what's going on clearly enough then you can do it efficiently.) $\endgroup$ – Gareth McCaughan Dec 6 '19 at 17:32
10
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ What is the "one of them" in your answer? $\endgroup$ – Thomas Markov Dec 6 '19 at 17:48
  • $\begingroup$ I think they meant rot13 (Ng yrnfg bar bs gurz). $\endgroup$ – melfnt Dec 6 '19 at 18:09
  • $\begingroup$ I did. I'll edit my answer to make it more explicit. [EDITED to add:] Now done. $\endgroup$ – Gareth McCaughan Dec 6 '19 at 18:33
  • $\begingroup$ Im not following. Let $p_1=.5$, and $p_2=p_3=.99$. Then the probability of two or more heads is $.99$. $\endgroup$ – Thomas Markov Dec 6 '19 at 18:49
  • 4
    $\begingroup$ Yup, but we don't care what the probability of two or more is, we care what the probability of an even number is. Whatever 2 and 3 do, exactly half the time 1 comes up the right way to make the number of heads even and exactly half the time it doesn't. $\endgroup$ – Gareth McCaughan Dec 6 '19 at 19:01
4
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.