Brain Teasers Optical Illusions Puzzle Hunts Codes & Ciphers Mechanical Puzzles
Personal Links
Browse Teasers
Search Teasers


Probability puzzles require you to weigh all the possibilities and pick the most likely outcome.


Puzzle ID:#8705
Fun:*** (2.23)
Difficulty:*** (2.92)
Submitted By:something*us****
Corrected By:Winner4600




A jar begins with one amoeba. Every minute, every amoeba turns into 0, 1, 2, or 3 amoebas with a probability of 25% for each case (dies, does nothing, splits into 2, or splits into 3). What is the probability that the amoeba population eventually dies out?


If p is the probability that a single amoeba's descendants will die out eventually, the probability that N amoebas' descendants will all die out eventually must be p^N, since each amoeba is independent of every other amoeba. Also, the probability that a single amoeba's descendants will die out must be independent of time when averaged over all the possibilities. At t=0, the probability is p, at t=1 the probability is 0.25(p^0+p^1+p^2+p^3), and these probabilities must be equal. Extinction probability p is a root of f(p)=p. In this case, p = sqrt(2)-1.
The generating function for the sequence P(n,i), which gives the probability of i amoebas after n minutes, is f^n(x), where f^n(x) == f^(n-1) ( f(x) ), f^0(x) == x . That is, f^n is the nth composition of f with itself.

Then f^n(0) gives the probability of 0 amoebas after n minutes, since f^n(0) = P(n,0). We then note that:

f^(n+1)(x) = ( 1 + f^n(x) + (f^n(x))^2 + (f^n(x))^3 )/4

so that if f^(n+1)(0) -> f^n(0) we can solve the equation.
The generating function also gives an expression for the expectation value of the number of amoebas after n minutes. This is d/dx(f^n(x)) evaluated at x=1. Using the chain rule we get f'(f^(n-1)(x))*d/dx(f^(n-1)(x)) and since f'(1) = 1.5 and f(1) = 1, we see that the result is just 1.5^n, as might be expected.


What Next?


See another brain teaser just like this one...

Or, just get a random brain teaser

If you become a registered user you can vote on this brain teaser, keep track of
which ones you have seen, and even make your own.


Back to Top

Online Now
9 users and 668 guests

Users In Chat
Follow Braingle!
Fold 'N Fly Paper Airplanes
Easy to follow folding instructions and videos.
Copyright © 1999-2017 | FAQ | Widgets | Links | Green | Subscribe | Contact | Privacy | Conditions | Advertise | Braingle Time: 3:58 pm
Sign In Create a free account