Timeline for Amoeba Interview Question
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 11, 2018 at 22:02 | comment | added | Carl | The answer that would not allow a $P=1$ solution to a more correct amoeba hypothesis is given here. It is arrived at with careful notation. | |
| Nov 22, 2010 at 21:53 | comment | added | whuber♦ | @shabbychef: One way to rule out P=1 is to study the evolution of the probability generating function. The pgf is obtained by starting with t (representing an initial population of 1) and iteratively replacing t by (1+t+t^2+t^3)/4. For any starting value of t less than 1, a graphic easily shows the iterates converge to Sqrt(2)-1. In particular, the pgf is staying away from 1, showing it cannot converge to 1 everywhere, which would represent complete extinction. This is why "the 1 isn't plausible." | |
| Nov 22, 2010 at 15:18 | comment | added | whuber♦ | That's clear, Mike, but what's your point? Aren't we talking about how to rule out 1 as a solution? By the way, it's obvious (by inspection and/or by understanding the problem) that 1 will be a solution. This reduces it to a quadratic equation which one can easily solve on the spot. That's not usually the point of an interview question, though. The asker is probably probing to see what the applicant actively knows about stochastic processes, Brownian motion, the Ito calculus, etc., and how they go about solving problems, not whether they can solve this particular question. | |
| Nov 21, 2010 at 23:04 | comment | added | Mike Anderson | @shabbychef -- thanks for the edit. I didn't realize we could use embedded TeX for math! @whuber -- shabbychef's statement $E_k = E_1^k$ is just a variation on my statement about the extinction probability, just add expectations instead of multiplying probabilities. Nice work, shab. | |
| Nov 21, 2010 at 21:02 | comment | added | whuber♦ | @shabbychef It's not so obvious to me. You can have the expectation grow exponentially (or even faster) while the probability of dying out still approaches unity. (For example, consider a stochastic process in which the population either quadruples in each generation or dies out entirely, each with equal chances. The expectation at generation n is 2^n but the probability of extinction is 1.) Thus there is no inherent contradiction; your argument needs something additional. | |
| Nov 21, 2010 at 19:50 | vote | accept | AME | ||
| Nov 21, 2010 at 18:41 | history | edited | user88 | CC BY-SA 2.5 |
TeXified.; added 4 characters in body
|
| Nov 21, 2010 at 18:03 | comment | added | shabbychef | The reason 1 is not a root is easily seen by considering the expected number of Amoeba after $k$ steps, call it $E_k$. One can easily show that $E_k = E_1^k$. Because the probability of each outcome is $1/4,$ we have $E_1 = 3/2$, and so $E_k$ grows without bound in $k$. This clearly does not gibe with $P = 1$. | |
| Nov 21, 2010 at 11:47 | history | answered | Mike Anderson | CC BY-SA 2.5 |