|Dec. 6th, 2013 @ 09:28 am Puzzle o' the Day 356!|
|This one illustrates a classic result from biology and demographics. It also makes for a pretty neat puzzle!|
The Probabilistic Amoebas from PotD 275! are back. And they've mutated! Each day, a Probabilistic Amoeba will split into a certain number of copies, with its behavior based on its idiosyncratic probability distribution.
a. (Warm-ups; mixed).
a.i. A certain breed of Probabilistic Amoeba will split into three with probability 1/4, and die otherwise. Given that it starts with one individual, what's the probability that the breed will eventually go extinct? Hint in white: What's the expected number of Amoebas in generation d? Can you use the inequality located here?
a.ii. Another breed will split into two with probability 2/3, and die otherwise. Given that it starts with one individual, what's the probability that the breed will eventually go extinct?
b. (The puzzle; medium without hints, easier with). Generalize! Consider a breed of Probabilistic Amoeba which produces n offspring on a given day with probability p_n, where n runs from 0 to infinity, and where the sum of the p_n is, of course, 1. How can you calculate d, the probability that the breed will eventually go extinct? Can you give conditions, based on the p_n, when d = 1?
Hint (in white): Let d_n be the probability that the breed goes extinct by generation n. Clearly 0 = d_0 <= d_1 <= d_2 <= . . . <= 1. Since the d_n are monotonic and bounded above, they must converge to their limit, which must be d. Also, let g(x) be the probability generating function for the Amoeba; i.e., g(x) = p_0 + p_1 x + p_2 x^2 + p_3 x^3 + . . .. These will be useful concepts.
Hint (in white): Find a way to write d_n as a function of d_(n-1), using the probability generating function. If one Amoeba will go extinct in n-1 generations with probability d_(n-1), what's the probability that two Amoebas will go extinct during the same time?
Hint (in white): It's pretty easy now if you got this far. The value of d must be where the graph of g(x) intersects a certain line (which line?). They will always intersect at x=1. Note that since g(x) is increasing and convex-up (since both g'(x) and g''(x) are always nonnegative), there is at most one other intersection point; if there is, it corresponds to d (why?). What conditions determine whether there's another intersection point?