4
$\begingroup$

So my friend gave me this question this other day, and I've tried to start it (I'll show my logic below), but I couldn't find any efficient way to do the problem.

You start out with 1 coin. At the end of each minute, all coins are flipped simultaneously. For each heads that is flipped, you get another coin. But for every tails that is flipped, a coin is lost. (Note any new coins are not flipped until the next moment). Once there are no more coins remaining, the process stops. What is the probability that exactly after 5 minutes (that's 5 sets of flips), that the process will have stopped (so no earlier or no later)?

I've taken a few approaches to this problem. What I've tried to do is to find the total amount of possibilities for each amount of coins by the 5th moment, and then multiply that by the probability that all coins will be vanished on the 5th moment. But I'm just not able to calculate how many possible ways exist to get to each amount of total coins by the end. Does anyone have any other ideas, or perhaps a formula to solve this problem?

$\endgroup$
11
  • $\begingroup$ Hint: What's the probability that it will stop within the first minute? second minute? third minute? fourth minute? fifth minute? $\endgroup$ – Calvin Lin Jun 14 '20 at 22:49
  • $\begingroup$ Within the first minute, it should be 1/2. In the second minute it should be 1/4 multiplied by the 1/2 chance of continuing from the first round. But then I'm finding it's getting tricky in the third round and so on since the amount of coins starts to vary. $\endgroup$ – Edwards Jun 14 '20 at 22:50
  • $\begingroup$ AyamGorengPedes, I think I was told this should take the form of a fraction of a/2^b where a is odd and they're both positive integers (so it's not 0). And I think the total possibilities is capped at the 5th minute, so it's moreover finding whether the flips will end exactly at the 5th minute (preferable), or continue after the 5th minute (non-preferable), or stop before the 5th minute (non-preferable). $\endgroup$ – Edwards Jun 14 '20 at 22:56
  • $\begingroup$ @CalvinLin Do you have any other ideas? Or could you elaborate on how to calculate the third moment and so on? I'm having some difficulty computing those. $\endgroup$ – Edwards Jun 14 '20 at 23:14
  • $\begingroup$ (There's always the brute force approach) Can you set up a table with rows as "number of coins" and columns of "probability of that number of coins in N minutes". For example, P(4 coins in 2 minutes) = 1/8. From there, you can calculate P(0 coins in 5 minutes) - P(0 coins in 4 minutes). $\endgroup$ – Calvin Lin Jun 14 '20 at 23:18
6
$\begingroup$

Let $q(k)$ be the probability that the process initiated by a single coin will stop on or before $k$ minutes. We write $q(k+1)$ in terms of $q(k)$: \begin{align} q(1) &= 1/2\\ q(2) &= (1/2) + (1/2)q(1)^2 = 5/8\\ q(3) &= (1/2) + (1/2)q(2)^2 = 89/128\\ q(4) &= (1/2) + (1/2)q(3)^2 = 24305/32768\\ q(5) &= (1/2) + (1/2)q(4)^2 = 16644\hspace{0pt}74849/2147483648 \end{align}

and the probability we stop at 5 minutes exactly is: $$q(5)-q(4) = \frac{71622369}{2^{31}} \approx 0.0333517645...$$

$\endgroup$
6
  • $\begingroup$ You’re probably right, but I did this the long way (using a Markov process transition matrix, as in Wim's answer), and got $\frac{71638753}{2147483648}$. There were definitely more chances for me to have goofed than for you. I'll recheck my work later. $\endgroup$ – Steve Kass Jun 15 '20 at 1:21
  • 1
    $\begingroup$ You may want to double check your matrix for the simpler case of ending in 2, 3, or 4 minutes to isolate any mistakes. My equation $q(k+1) = (1/2) + (1/2)q(k)^2$ observes that the process initiated by two coins ending within $k$ steps is the same as each process initiated by one coin independently ending within $k$ steps (each individual coin independently generates its own descendent coins). The fact that your answer is so close to mine suggests you may have a matrix mistake associated with transitions out of a state that is rarely visited anyway. $\endgroup$ – Michael Jun 15 '20 at 4:18
  • 1
    $\begingroup$ I found my mistake and summarized my confirmation of your answer as a separate answer. Your much simpler approach is outstanding! $\endgroup$ – Steve Kass Jun 15 '20 at 16:53
  • $\begingroup$ The denominators of the probability of this game stopping after $n$ steps form the sequence here: oeis.org/A187131. $\endgroup$ – Steve Kass Jun 15 '20 at 21:10
  • $\begingroup$ I notice that my answer above renders correctly on laptop but incorrectly on iPad/iPhone. I have asked a question about the bug on meta here: math.meta.stackexchange.com/questions/31952/… $\endgroup$ – Michael Jun 19 '20 at 4:35
3
$\begingroup$

This is too long for a reply to my earlier comment, and since it provides an alternate answer, I'm posting it that way.

I confirmed Michael's answer by the brute-force approach suggested by Calvin and Wim in their answers.

I set this up as a Markov process where the state is the number of coins. (There can be from $0$ through $16$ coins after $4$ steps, which is all I needed.) The probability of transition from $i$ coins to $j$ coins is $0$ if $j$ is odd and ${i\choose {j\over2}}\cdot{1\over2^i}$ if $j$ is even. (This is left as an exercise to the reader!)

Then (thanks, Mathematica!) I computed $M^4$ for the transition matrix $M$ of the above probabilities. Then $(M^4)_{1j}$ is the probability of there being $j$ coins after $4$ steps, and thus the probability of ending after exactly $5$ steps is $\sum_{j=1}^{16}(M^4)_{1j}\cdot{1\over2^j}$. (Note that the sum doesn't start at $j=0$ because that would correspond to the game ending before the fifth step.) The nonzero terms $\left(M^4\right)_{1j}$ in the calculation ($j=2,4,6,\dots,16$), for anyone interested, are $\left(\frac{445}{4096},\frac{723}{8192},\frac{159}{4096},\frac{267}{16384},\frac{19}{4096},\frac{11}{8192},\frac{1}{4096},\frac{1}{32768}\right)$.

$\endgroup$
2
$\begingroup$

(This is not a complete solution).

There's always the brute force approach.

At time $t$, if there are $n$ coins, then the probability that there are $2k$ coins at time $t+1$ is ${n \choose k } \times \frac{1}{2^n}$.

We can come up with the following table for probability at time $t$, we have $n$ number of coins:

$\begin{array} { l | l l l l l} & 1 & 2 & 3 & 4 & 5 \\ \hline 0 & \frac{1}{2} & \frac{1}{2} \times 1 + \frac{1}{2} \times \frac{1}{4} = \frac{5}{8} & \frac{5}{8} \times 1 + \frac{1}{4} \times \frac{1}{4} + \frac{1}{8} \times \frac{1}{16} = \frac{89}{128} \\ 2 & \frac{1}{2} & \frac{1}{2} \times \frac{2}{4} = \frac{1}{4} \\ 4 & & \frac{1}{2} \times \frac{1}{4} = \frac{1}{8} \\ 6 & \\ 8 & \\ 10 & \end{array}$

Yes, it gets long and ugly, which is why I didn't complete it for 5. But, at least it could be done.

$\endgroup$
4
  • $\begingroup$ I'm trying that right now, but not very easy to calculate, and I'm interested to see any efficient solutions and the reasoning behind it. I'm still pretty new to probability, so thinking of a more effective method is difficult for me and seeing how to find it would be useful. Thanks though still! $\endgroup$ – Edwards Jun 14 '20 at 23:33
  • $\begingroup$ Just set up the equations (in excel, or computer program) and you can get the answer. Once you got it, you can see if there is "something nice" for a more elegant approach. $\endgroup$ – Calvin Lin Jun 14 '20 at 23:35
  • $\begingroup$ I don't have excel or a computer programmer on hand right now, could you get the answer for me? (I'm not 100% sure how to set a program to do it anyways) $\endgroup$ – Edwards Jun 14 '20 at 23:37
  • $\begingroup$ The calculation for stopping at round $3$ should end with ${1\over8}\times{1\over16}$, not ${1\over8}\times{1\over8}$, since that case corresponds to tossing $4$ coins. (This gives agreement with the calculation in Michael's answer.) $\endgroup$ – Barry Cipra Jun 15 '20 at 0:01
0
$\begingroup$

Try to use a Markov Matrix M. States are 0, 1, 2, 3, 4, ... and 32 coins. Calculate the probabilities for all transitions. The column represent the state before flipping the coins. The rows represent the state after flipping the coins. You will have a $33 \times 33$ matrix.

\begin{bmatrix} 1 & 0.5 & 0.25 & . & ... & .\\ 0 & 0 & . & . & ... & .\\ 0 & 0.5 & . & . & ... & .\\ 0 & 0 & . & . &... & .\\ 0 & 0 & . & . &... & .\\ ...\\ 0 & 0 & . & . &... & .\\ \end{bmatrix}

The initial state is 1 coin and can be represented as a matrix A \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \\ ... \\ 0 \\ \end{bmatrix}

The distribution after 5 rounds can be calcalated by $M^5 \times A$.

This way you can calculate the probabilities of having zero coins after 5 flips. You will still have to subtract the probabilities for having 0 coins after 1, 2, 3 or 4 flips.

$\endgroup$
4
  • $\begingroup$ Why do you stop at $6$ coins? You could have as many as $16$ after the first four rounds. $\endgroup$ – Barry Cipra Jun 14 '20 at 23:34
  • $\begingroup$ You are right. I will update it. $\endgroup$ – Wim Nevelsteen Jun 14 '20 at 23:38
  • $\begingroup$ I'll be interested to see if you can get a transition-matrix approach to work. I was thinking about it myself (which is why I thought a $7\times7$ was too small), but couldn't see any easy way to set things up. $\endgroup$ – Barry Cipra Jun 14 '20 at 23:41
  • $\begingroup$ @WimNevelsteen What fraction would you end up getting then? (I'm not that good with matrices) $\endgroup$ – Edwards Jun 14 '20 at 23:48

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.