A Fun Puzzle from Probability
- Get link
- Other Apps
Here is a problem that came up a few days ago and I'm still thinking about:
Unfortunately, this strategy leads to a dead end. Instead, I use a clever interpretation of the problem that leads to a very simple and elegant solution. My key insight came from seeing an infinite continued fraction problem, which uses a simple technique to define the value of the continued fraction in terms of itself. That same approach can be used for the amoebae problem.
The first thing to notice is that when an amoebae splits into multiple amoebae, each amoebae acts independently from the others but with the same probability distribution. Thus they are independent and identically distributed random variables. First we define $x$ to be the probability of population starting from 1 amoeba of eventually dying out. Then we try to write an expression for x in terms of itself that we can solve. We find
$$ x = \frac{1}{4} + \frac{1}{4} x + \frac{1}{4} x^2 + \frac{1}{4} x^3 $$ This equation must hold because the single amoeba can die immediately with probability $\frac{1}{4}$, it can stay the same ($\frac{1}{4}$) then eventually die ($x$) with probability $\frac{1}{4} x$, it can multiply in two ($\frac{1}{4}$) then both children eventually die ($x^2$) with probability $\frac{1}{4} x^2$, or it can multiply in three ($\frac{1}{4}$) then all three children eventually die ($x^3$) with probability $\frac{1}{4} x^3$. Since these events are mutaully exclusive, the stated equation must hold.
To determine the extinction probability, we must solve this equation for $x$. Solving the equation is fairly straightforward because $1$ is a root of the equation, meaning the cubic equation can be easily reduced to a quadratic equation, which we can solve easily. The real valued solutions to this equation on the interval $[0,1]$ are $ x = 1 $ and $ x = \sqrt{2} - 1 $.
Thus, either the amoebae go extinct no matter what or the they go extinct with probability $ x \approx 0.41 $. It turns out that the answer is $ \sqrt{2} - 1 $, however I have not been able to prove this yet. I verified the result by running a computer simulation and also found a fact that if the expected number of offspring is greater than 1, then the probability of eventual extinction is less than 1. Here the expected number of offspring is (0+1+2+3)/4 = 1.5. I have not found any proof of this result, but it intuitively makes sense that the answer isn't $x=1$ in this case.
There is an amoebae in a box. At each time step, it either multiplies in 2, multiplies in 3, stays the same, or dies - all with equal probability. What is the probability that eventually, all the amoebae die out?
Solution
One can quickly see that the probability is at least $\frac{1}{4}$ because there is a $\frac{1}{4}$ chance of dying on the first time step. Similarly, you could die on the first time step ($\frac{1}{4}$), stay the same then die ($\frac{1}{4^2}$), etc. Thus, the probability of eventual extinction is at least $\sum_{n=1}^{\infty} \frac{1}{4^n}$.Unfortunately, this strategy leads to a dead end. Instead, I use a clever interpretation of the problem that leads to a very simple and elegant solution. My key insight came from seeing an infinite continued fraction problem, which uses a simple technique to define the value of the continued fraction in terms of itself. That same approach can be used for the amoebae problem.
The first thing to notice is that when an amoebae splits into multiple amoebae, each amoebae acts independently from the others but with the same probability distribution. Thus they are independent and identically distributed random variables. First we define $x$ to be the probability of population starting from 1 amoeba of eventually dying out. Then we try to write an expression for x in terms of itself that we can solve. We find
$$ x = \frac{1}{4} + \frac{1}{4} x + \frac{1}{4} x^2 + \frac{1}{4} x^3 $$ This equation must hold because the single amoeba can die immediately with probability $\frac{1}{4}$, it can stay the same ($\frac{1}{4}$) then eventually die ($x$) with probability $\frac{1}{4} x$, it can multiply in two ($\frac{1}{4}$) then both children eventually die ($x^2$) with probability $\frac{1}{4} x^2$, or it can multiply in three ($\frac{1}{4}$) then all three children eventually die ($x^3$) with probability $\frac{1}{4} x^3$. Since these events are mutaully exclusive, the stated equation must hold.
To determine the extinction probability, we must solve this equation for $x$. Solving the equation is fairly straightforward because $1$ is a root of the equation, meaning the cubic equation can be easily reduced to a quadratic equation, which we can solve easily. The real valued solutions to this equation on the interval $[0,1]$ are $ x = 1 $ and $ x = \sqrt{2} - 1 $.
Thus, either the amoebae go extinct no matter what or the they go extinct with probability $ x \approx 0.41 $. It turns out that the answer is $ \sqrt{2} - 1 $, however I have not been able to prove this yet. I verified the result by running a computer simulation and also found a fact that if the expected number of offspring is greater than 1, then the probability of eventual extinction is less than 1. Here the expected number of offspring is (0+1+2+3)/4 = 1.5. I have not found any proof of this result, but it intuitively makes sense that the answer isn't $x=1$ in this case.
- Get link
- Other Apps
Comments
Post a Comment