0

The game works as follows:

  • You start with $n$ coins, all facing heads before flipping. You are instructed to select any $k$ coins at random and invert them. This process is done for $x$ rounds. Find the expected number of heads after the above process.

Found this problem from an old math contest, thoughts on how to approach it?

JMP
  • 21,771
paraxor
  • 3

1 Answers1

0

Hints

  • A coin will end up showing heads if it gets flipped an even number of times.
  • By symmetry,$$P(\text{coin}\ \ c\ \ \text{gets flipped an even number of times})$$ is the same for all coins.
  • Therefore, if $\ H\ $ is the number of coins showing heads after $\ x\ $ rounds of flipping, then\begin{align} E(H)&=\sum_{c=1}^nP(\text{coin}\ \ c\ \ \text{gets flipped an even number of times})\\ &=n\,P(\text{coin}\ \ 1\ \ \text{gets flipped an even number of times}) \end{align}
  • The probability that coin $\ 1\ $ gets flipped in any given round is $\ \frac{k}{n}\ $, independently of whether it got flipped in any other round.
  • Therefore, the distribution of the number of times coin $\ 1\ $ gets flipped in $\ x\ $ rounds is binomially distributed with parameters $\ x\ $ and $\ p=\frac{k}{n}\ $:\begin{align} P(\text{coin}\ \ 1\ \ \text{gets flipped}\ \ r\ \ \text{times})={x\choose r}\left(\frac{k}{n}\right)^r\left(1-\frac{k}{n}\right)^{n-r}\ . \end{align} Can you now see how to evaluate $\ E(H)\ $?
  • I agree with Gareth Ma's comment below that the result he cites (which I wasn't aware of) is also worth noting.
lonza leggiera
  • 28,646
  • 2
  • 12
  • 33
  • 3
    I think it is worth noting that the explicit formula for binomial distribution isn't even needed here, since you only need the probability that the outcome is even, for which you have a nice symmetry argument, see here. In particular, the probability that $X \sim Bin(n, p)$ is even is $\frac{1}{2} + \frac{1}{2}(1 - 2p)^n$, which is probably what's needed in the original problem to simplify calculations (since $(1 - 2p)^n$ is negligible). – Gareth Ma Feb 13 '23 at 10:27
  • I agree, and have now noted it in my answer. Thank you for pointing out the result, which I wasn't aware of (though I did wonder whether there was some such simple formula). – lonza leggiera Feb 13 '23 at 11:00
  • This can actually be generalised to something called the roots of unity formula, which is that for $f(x) = a_0 + a_1x + a_2x^2 + \cdots$, we can evaluate the sum $a_0 + a_k + a_{2k} + \cdots$ by $\frac{1}{n}\sum_{i = 0}^n f(\zeta_k^i)$, where $\zeta_k$ is the primitive $k$-th root of unity. This relies on the fact that $\sum_i \zeta_k^{ij} = 0$ when $j \not\equiv 0 \pmod{k}$, and $n$ otherwise. There is also a circle method that is used in e.g. fourier analysis (and as far as i know, the circle method) – Gareth Ma Feb 13 '23 at 11:15
  • See also https://math.stackexchange.com/questions/1149270/probability-that-binomial-random-variable-is-even – kludg Feb 13 '23 at 14:07