I've come across a puzzle (Problem 10 from this list of sample interview questions):
One day, an alien comes to Earth. Every day, each alien does one of four things, each with equal probability to:
- Kill himself
- Do nothing
- Split himself into two aliens (while killing himself)
- split himself into three aliens (while killing himself)
What is the probability that the alien species eventually dies out entirely?
Unfortunately, I haven't been able to solve the problem theoretically. Then I moved on to simulate it with a basic Markov Chain and Monte Carlo simulation in mind.
This was not asked to me in an interview. I learned the problem from a friend, then found the link above while searching for mathematical solutions.
Reinterpreting the question
We start with the number of aliens
n = 1.
n has a chance to not change, be decremented by
1, be incremented by
1, and be incremented by
2, %25 for each. If
n is incremented, i.e. aliens multiplied, we repeat this procedure for
n times again. This corresponds to each alien will do its thing again. I have to put an upper limit though, so that we stop simulating and avoid a crash.
n is likely to increase and we're looping
n times again and again.
If aliens somehow go extinct, we stop simulating again since there's nothing left to simulate.
n reaches zero or the upper limit, we also record the population (it will be either zero or some number
I repeat this many times and record every result. At the end, number of zeros divided by total number of results should give me an approximation.
from random import randint import numpy as np pop_max = 100 iter_max = 100000 results = np.zeros(iter_max, dtype=int) for i in range(iter_max): n = 1 while n > 0 and n < pop_max: for j in range(n): x = randint(1, 4) if x == 1: n = n - 1 elif x == 2: continue elif x == 3: n = n + 1 elif x == 4: n = n + 2 results[i] = n print( np.bincount(results) / iter_max )
pop_max can be changed indeed, but I thought if there is 100 aliens, the probability that they go extinct would be negligibly low. This is just a guess though, I haven't done anything to calculate a (more) proper upper limit for population.
This code gives promising results, fairly close to the real answer which is approximately %41.4.
> python aliens.py 0.41393 > python aliens.py 0.41808 > python aliens.py 0.41574 > python aliens.py 0.4149 > python aliens.py 0.41505 > python aliens.py 0.41277 > python aliens.py 0.41428 > python aliens.py 0.41407 > python aliens.py 0.41676
I'm okay with the results but I can't say the same for the time this code takes. It takes around 16-17 seconds :)
How can I improve the speed? How can I optimize loops (especially the
while loop)? Maybe there's a much better approach or better models?