The other day I found a puzzle on the internet, that loooked simple to solve, at first. Hmm, it was more involved than I expected, and it made me to rehearse some long forgotten maths. I had a lot of fum solving it. But don't worry, this forum is all about programming, so read on. You will not be bored, I guarantee, or else you will be entitled for a refund ;)
The situation is this: we have six unbiased coins. Now, in round 1 we toss them all, and remove all those that landed heads up. In round 2 we toss all the remaining coins, remove again all those landing head op, et cetera, until there are no more coins left. The question is: what is the average number of rounds?
Question 1 can you write code that simulates this process? Give for N in the range (1, 1000) the average number of rounds. To test your outcomes: the average is (very) roughly equal to 1.5 + base_of_2_log(N), where N is the starting number of coins.
Question 2 But we can derive the discrete density function. To save on typing, let v = 0.5, the chance for a coin to land on heads. If we have one coin, then the chance of needing k tosses is v^k. We get as average the series
E(1) = 1*v + 2*v^2 + 3*v^3 + ... (ad infinitum).
If you are a little handy in manipulating this kind of series, you will have no difficulty to find that E(1) = 2.
If we have N coins, and the random variable X(i) denotes the number of tosses needed for coin i, then we are looking for the density of the random variable Y = max(X(1), X(2), ..., X(n)). We get:
the chance that Y = k, or P[Y = k], = [1 - v^k]^N - [1 - v^(k - 1)]^N.
(Note: in the derivation of this formula, you might get the factor v / (1 - v). But since this is equal to 1, I left it out).
Can you give a good approximation of the average, from the definition of it and the above formula, for number of coins 1 ... 1000, and compare these to the outcomes of challenge 1?
Question 3 For small values of N, a perhaps easier way is as follows. Suppose we have 1 coin. Then for sure we toss 1 time. And with a chance of v the coin is landing tails up, and we have the same situation as before. That leads to the simple formula:
E(1) = 1 + v*E(1), and so we find that E(1) = 2.
When we have two coins, things get slightly more complex. We get the following formula:
E(2) = 1 + (2 * v^2 * E(1)) + (v^2 * E(2)). Solving this, we get that E(2) = 8 / 3.
And proceeding this way, we arrive at the lovely recursion relation: