Here's a very interesting problem sent in by Lee. Have fun playing with this.
Toby has a jar with one amoeba in it. Every minute, every amoeba turns into 0, 1, 2, or 3 amoebae with a probability of 1/4 for each case (dies, does nothing, splits into two, or splits into three). What is the probability that the amoeba population eventually dies out?If you're wondering, Lee's brother Chip created the image above. I'm guessing it has something to do with the solution.
Posts
14 comments:
My attempt at an answer is based on a hunch -- and might therefore not hold H2O.
Since there is a 25% chance for each of the four possible scenarios, I took a look at the
relationship (in outcomes) for the third and forth cases -- namely if said amoeba splits into 2 or 3. I did this because it seemed more unlikely there would be "ultimate death" in the 4th group vs. the 3rd group of 25 percenters. It appeared (when looking at the
difference in outcomes of 2 vs. 3 amoebae) that there was a 1/5 or 20% "probability difference" going on. This is a new term in Math called PD. Since the PD factor in these two "25% probable" cases is so important, I felt it would be appropriate to use the following equation to SPEEDILY get the answer for the ultimate probability that the total
amoeba population would die out.
25% x .20 = 5%
So, my answer is a 5% chance.
Max, my prob+stat stinks, but doesn't the probability have to be at least 25%? That's the probability they die out in the first round. It would seem like the probabilities that they would die in the second, third, ... rounds would just be added to that.
(BTW, I've never seen this problem before. This is all Lee's. So I get to have a little fun thinking through it with you all.)
Interesting! Thanks for the prompt reply. I can see where I need to take a look at a KEY point here -- namely the addition of probabilities in a problem like this. It DOES seem pretty obvious, now that you mention it, that we need at least a 25% (based on the four possible series of outcomes). I am therefore going to revise my answer to 30%. Let's see what Lee has to say about this.
I'd say it's about 25% or something that converges just slightly above 25%. I wrote a crude simulator that seems to grow quite rapidly (if it doesn't die out *right* away).
http://jsbin.com/uyifu
I'm thinking the same thing. The probability of die out gets smaller and smaller each successive round, so the overall probability of a die out must converge somewhere above 25%. Time to sketch out the tree diagram!
Michael, I tried the simulator. Nothing happens when I hit the "go" button. Am I missing a plugin or something?
Woohoo! 5 comments! I too don't see anything when I hit the go button. I've written a simulation (in tiny-c of course) and am interested in seeing yours work (plus maybe learning some ajax). This is a good way to go to learn more about the (approx.) answer to this problem. The observation that if it doesn't die out early it will become a huge population is true. Have fun!
I thought about it some more and it seems like it should be 1/4+1/16+1/64...(1/(4^n)).
which is about 33%. That's my updated *upper bound* answer. I think it's less than that.
I'll look at the simulator later.
OK, I fixed the simulator and added a trials feature to it. I'm getting approx 41% probability of die out.
This works with FF3:
http://jsbin.com/afoli
It works in IE although the 10000x feature is too slow in IE to be useful.
Michael - simulation works great. And is producing the correct result. I can sort of see why you came up with 1/4+1/16+1/64...1/(4^n), which is a geometric series which sums to exactly 1/(1-1/4) which equals 1.333 but this really isn't relevant to the problem at hand.
Of course the challenge is to see if a purely analytical approach to this thing can produce an exact answer for the probability.
The following might help ...
Let p be the probability extinction occurs. Since this probability is independent of time, this probability will be the same at "generation 0" (when there's a single amoeba) and at "generation 1" (at which time it might have vanished, survived or split in two or in three). The probability an amoeba and a twin "brother" both die is p^2. The probability that "triplets" all die is p^3.
A hi-rez version of this lo-rez amoeba, personally signed by the artist's cat Toby, to the first person that nails this problem.
Possibly the most interesting aspect of this thread is *not* the problem itself but the tool Michael has introduced us to, namely
http://jsbin.com
This is a webapp that allows one or more people to share, develop, and debug dynamic web pages.
Thanks Michael!
But I digress. Here's more on the problem at hand ...
You start with 1 amoeba. Let p stand for the probability its family tree dies out.
This probability is independent of the stage at which you consider it. The LHS of the equation below is the probability at generation 1. The RHS is the probability at generation 2.
p = 1/4+1/4*p+1/4*p^2+1/4*p^3
p = probability of extinction = probability it dies during 1st generation +
probability it survives 1st generation and then dies +
probability it splits in two during 1st generation and then both die +
probability it splits in three during 1st generation and then all three die
So ... we've reduced our little problem to one of solving the above equation.
Your turn.
Yeah, I just discovered jsbin myself they day earlier. Very handy stuff.
I've written a very simple program using jsbin to "solve" the equation
p=(1+p+p^2+p^3)/4
Output may be seen at
jsbin.amoeba.approx.png
You may run the program by going to
http://jsbin.com/ubiqu
An *exact* solution to this equation may be obtained by recognizing
0=(1+p+p^2+p^3)/4 - p
0=1+p+p^2+p^3 - 4p
0=1-3p+p^2+p^3
One solution to the above is p=1.
So, the above can be written
0=(p-1)(a quadratic expression)
Surely, among all the geeks out there in yofx land, *someone* can finish this thing off. Remember, there's an awesome graphic prize. Better act quick or you'll not get it.
I sent Paul Argazzi a note asking him to take a look at this problem. He got back with:
the answers are 1 (from you), and -1 plus/minus radical 2
I checked them, they worked. I had to use the quadratic formula on
y=p^2+2p-1
Or am I doing something wrong?
I got back to him with:
Bingo. Of course you are right. Well done. Thanx. Of course, as I said, it really is not that difficult a problem once you get to the stage of knowing that the other factor is p^2 +2p -1.
Getting to this stage does require that you know how to divide (1-3p+p^2+p^3) by (1-p) which isn't something everybody knows how to do. Then of course there's the need to know that when (a)(b) = 0, this means a=0 or b=0. And in our case p^2+2p-1=0 means (since it's not easily factored) that you need to use the quadratic formula.
Hmm. That's a lot of words to explain why "it's not really that difficult."
You are hereby awarded the coveted
Amoeba graphic "signed" by the artist's cat Toby.
PS - BTW, -1 plus radical 2 is of course, approx.
0.4142135623730949
which is the (approx.) answer to the original question which was
What is the probability that the amoeba population eventually dies out?
For those out there that can't get enough of this, I refer you to the paper J. Laurie Snell of Dartmouth on Generating Functions. In this paper he discusses Branching Processes. One interesting result is this: if the expected number of offspring is m after 1 generation, the expected number of offspring after n generations is m^n. In our case m=1.5 because
1(1/4) + 2(1/4) + 3(1/4) = 6/4 = 1.5
This accounts for the observation that several have noticed that if our cute little amoeba doesn't self-destruct his family tree gets very big very quickly. Here is the output from a simulation I wrote:
1.5^30
Great job, Paul! And great problem, Lee! I can't decide whether this one or the block on better. There both a lot of fun.
Post a Comment