Coin Flip Problem

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


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


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

Tags:

Combinatorics

Combinations

Probability

Related

Limit $\lim _{x \to 0}\sqrt {x+\sqrt {x+\sqrt{x+\sqrt{x...}}}}=1$ On the proof of $\;(1+x)^p\equiv1+x^p \pmod p$ The product of continuous function is continuous. Find maximum $k \in \mathbb{R}^{+}$ such that $ \frac{a^3}{(b-c)^2} + \frac{b^3}{(c-a)^2} + \frac{c^3}{(a-b)^2} \geq k (a+b+c) $ Show that $\exp\left(\frac{1}{x}\log\frac{e^{x}-1}{x}\right)$ is increasing. How to find the distance along a sphere from an angle? Volume Enclosed Between a Surface and a Plane Is there a modal logic axiom corresponding to the condition that for every world w there is some world v such that vRw? (Reverse Seriality) Let $A\in M_n(\Bbb R)$ be such that the sum of the two largest numbers in each row is $a$, and in each column is $b$. How can I prove that $a=b$? Functions $f: \mathbb{Z}^{+}\to \mathbb{R}$ satisfying $x f(y) + y f(x) = (x+y) f(x^2+y^2)$ What is $\frac{\det(\hat{\Sigma}_0)}{\det(\hat{\Sigma})}$ in terms of $\hat{\mu}_1$, $\hat{\mu}_2$ and $\hat{\Sigma}$ Why $\lim_{\varepsilon \to 0} \varepsilon \int_0^\infty \frac{z\,dz}{(z-1)^2 + \varepsilon^2z^3} = \pi$?

Recent Posts