Author |
Topic: The bacterium (Read 12777 times) |
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
 |
Re: The bacterium
« Reply #25 on: Nov 5th, 2003, 12:54am » |
 Quote  Modify
|
on Nov 4th, 2003, 11:10pm, TimMann wrote:Therefore the process converges to the absorbing state. With probability 1, the colony eventually dies out.
See the reference I gave in this thread. |
|
I disagree, there is a difference between the two problems, and that's a very important difference. That problem has a finite state-space, this one does not. The colony can get arbitrarily far away from the absorbing state, just like in a 3d random walk.
'infinity' is another absorbing state in a sense..
|
| « Last Edit: Nov 5th, 2003, 12:56am by towr » |
 IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: The bacterium
« Reply #26 on: Nov 5th, 2003, 2:01am » |
Quote Modify
|
on Nov 4th, 2003, 4:54pm, Icarus wrote:
But so far I haven't found the method that allowed towr to produce the answer so easily. |
|
Compute the n-th partial product:
If you factor the terms, the (k-1) terms on top cancel with terms to the left, and the (k2+k+1) terms cancel with terms to the right, leaving you with 2/3 at the beginning and (n2+n+1)/(n(n+1)) at the end.
Factoring further to (k-1)(k-w)(k+w+1)/[(k+1)(k+w)(k-w-1)] makes the telescoping more obvious.
Personally I tried looking at prod(1+1/k2)/prod(1-1/k2) to see if that worked out any nicer, but I didn't know what to do with
[sum]n odd 2(Zeta(3n)-1)/n. Then I figured that must be the limit of partial products towr was taking.
|
|
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: The bacterium
« Reply #27 on: Nov 6th, 2003, 12:00am » |
Quote Modify
|
on Nov 5th, 2003, 12:54am, towr wrote:
I disagree, there is a difference between the two problems, and that's a very important difference. That problem has a finite state-space, this one does not. |
|
Oops, you're quite right. The reasoning I gave doesn't work when you have an infinite state space.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
pjay
Newbie
Gender:
Posts: 30
|
|
Re: The bacterium
« Reply #28 on: Dec 25th, 2003, 12:13pm » |
Quote Modify
|
This is a great problem, and as is the case with some the gerat ones, there is tons of literature concerning this process. In general assume that the bacteria has an arbitrary offspring distribution (in our case the offspring distribution is bernoulli: 0 with prob 1-p and 2 with prob p) with finite mean. The process is then referred to as a branching process, or a Galton-Watson process (biologists prefer the latter). Anyways, a good reference on this process is Durrett (1995). a whole book was written on this process by Athreya circa 1970 which answers all your questions and much much more (the book is entitled Branching Processes).
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: The bacterium
« Reply #29 on: Apr 27th, 2004, 4:20pm » |
Quote Modify
|
Is it really so complicated? I just did this.
p = probability of 1 cell splitting.
q = probability of the colony surviving from one cell.
To survive, a colony must split and at least one side must survive.
q = p*(prob(one side survives))
= p*(1 - prob(both sides die))
= p*(1 - prob(one side dies)2 )
= p*(1 - (1 - prov(one side survives))2 )
= p*(1 - (1 - q)2)
= p*(2*q - q2)
q = p*(2*q - q2)
Either q is 0 or 1 = p*(2 - q), i.e. q = 2 - 1/p
But for p<1/2, q would be <0. So for p<1/2, the solution q=0 is valid.
For p=1/2, q is zero either way.
For p>1/2, I assume q can not be zero because the probability of increasing in number is larger than the probability of decreasing. So I think the solution is:
For p<=1/2, the colony eventually dies.
For p>1/2, the survival probability is 2-1/p.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: The bacterium
« Reply #30 on: Jan 23rd, 2005, 5:57pm » |
Quote Modify
|
on Jan 22nd, 2003, 10:01am, william wu wrote:| So in general, if the number of kids a bacterium has is given by the random variable X, and the probability that a bacterium has k kids is given by the distribution P(X = k), what property should this distribution have to ensure that the colony propagates forever? Also, when does the border case ensure immortality? |
|
Apparently this problem hasn't been solved on this forum yet.
Let Xn be the population in the nth generation, X0=1. Let an=P(Xn=0) be the probability that the population has died out by the nth generation, and let a=lim an be the probability the colony goes extinct.
(1) Find an expression for an+1 in terms of an and the distribution of X1.
(2) Give necessary and sufficient conditions for a=1.
(3) Examine the rate of convergence, an [to] a (to be made more explicit later).
|
| « Last Edit: Jan 25th, 2005, 4:11pm by Eigenray » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: The bacterium
« Reply #31 on: Mar 15th, 2005, 5:29pm » |
Quote Modify
|
I guess I'll answer the first (easy) part:
on Jan 23rd, 2005, 5:57pm, Eigenray wrote:
(1) Find an expression for an+1 in terms of an and the distribution of X1. |
|
If pk=P(X1=k), then
an+1 = P(Xn+1=0) = [sum]k=0[infty] P(X1=k)P(Xn+1=0 | X1=k) = [sum] pkank.
Now, when does lim an = 1 ?
|
|
IP Logged |
|
|
|
iyerkri
Newbie
 
Gender:
Posts: 17
|
|
Re: The bacterium
« Reply #32 on: Mar 29th, 2005, 8:36am » |
Quote Modify
|
on Jan 22nd, 2003, 1:15am, william wu wrote:My almost complete solution below -- i invite someone else to finish it -- using the newly implemented hide tags:
To make things easier to think about for me, I will compute the probability that the colony becomes extinct. Then the probability of immortality = 1 - probability of extinction. Denote the probability of extinction by s.
A 1st generation: the very first bacterium
/ \
B C 2nd generation: two kids
Denote the first bacterium by A. A can make either 0 or 2 kids for the next generation. These are disjoint events, so from the total probabiility theorem (which basically just adds up all possible cases that can create a desired result):
s = (prob. A dies) + (prob. A splits)*(prob. A's kids have immortal family trees | prob. A splits)
s = (1-p) + p*s2
Reasoning: In the case where A makes 0 kids, the colony is dead from the start. This happens with probability 1-p, since it is the complementary event to the first bacterium splitting. Then we have an addition sign, because we wish to consider a completely disjoint event where A has 2 kids. (Formally said, given two events E and F, Pr(E OR F) = Pr(E) + Pr(F) if Pr(E AND F) = 0.) Note that the colony will now become extinct only if BOTH family trees created by A's kids become extinct. Now for the somewhat clever part, I claim this extinction probability, given that A splitted, is s2. This can be deduced from two facts:
1) The probability distribution of offspring for a single bacterium is identical across all generations. That is, if we denote X as a random variable returning the number of kids a bacterium has, then
P(X = 2) = p
P(X = 0) = 1-p
P(X = anything else) = 0
regardless of where in history the bacterium is. Thus you would expect the prob. of extinction for B's tree = prob. of extinction for C's tree = prob. of extinction for A's tree = s.
2) The trees produced by B and C develop independently of each other. Thus the probability that B's tree becomes extinct AND C's tree becomes extinct = probability that B's tree becomes extinct * probability that C's tree becomes extinct. (When you have two independent events, the probability of their intersection is the product of the individual probabilities.)
If you're convinced, now all we have to do is solve our quadratic equation for s!
s = (1-p) + p*s2
0 = p*s2 - s + (1-p)
refresher: roots of quadr = { -b +/- sqrt(b2 - 4ac) } / (2a)
Plugging stuff in gives us two possible solutions for s (you can verify it yourself)
s = 1, or
s = (1-p) / p
How do you know which value for s is valid? I'll let someone else finish this up.
|
|
The solution to the problem is the smallest positive solution to the quadratic you wrote. it can be shown using standard argument, that the probability of extinction is atleast as small as any solution to the quadratic. For more info, see branching process in any probablity textbook.
~kris
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: The bacterium
« Reply #33 on: Mar 30th, 2005, 12:36am » |
Quote Modify
|
on Jan 23rd, 2005, 5:57pm, Eigenray wrote:
Apparently this problem hasn't been solved on this forum yet.
Let Xn be the population in the nth generation, X0=1. Let an=P(Xn=0) be the probability that the population has died out by the nth generation, and let a=lim an be the probability the colony goes extinct.
(1) Find an expression for an+1 in terms of an and the distribution of X1.
(2) Give necessary and sufficient conditions for a=1.
(3) Examine the rate of convergence, an [to] a (to be made more explicit later). |
|
More generally, given independent and identically distributed random variables X1, X2, ... with finite expectation, we have that [sum]Xi will go to infinity when EX > 0, will go to -infinity when EX < 0, and will oscillate between positive and negative infinitely often when EX = 0 (with probability 1, of course). So for this problem, the bacteria will die out with probability 1 when the expected change in the number of bacteria each step is nonpositive.
In terms of P(x) = [sum] pkxk, we get the value of a by observing where a0 = 0 goes after repeated application of P; this is just the smallest nonnegative root of P(x) - x = 0. Note that P(x) - x is convex, so it will have a root smaller than 1 if and only if the derivative at 1 is positive. But
d(P(x)-x)/dx (1) = [sum] k pk - 1
which is indeed the expected rate of change of the population, so it agrees with the above.
(3) The rate of convergence of Pi(x) to a point depends on the multiplicity of the limit as a root of P(x) - x = 0. If the multiplicity is one, the rate of convergence will be geometric - you can imagine that the curve is almost linear near the limit. For multiplicity k > 1 I believe |Pi(x) - L| will be theta (i-1/(k-1)), based on (for example) about xn-1applications of (x - xn) being required to decrease a small epsilon by a constant factor. For this problem we can only get k=2, and only for a root of 1 (since it's convex and 1 is a root). So we only get slower convergence in the case
P(x) - x = c(x-1)2Q(x)
where Q(x) has no positive roots. We can probably say more about Q(x), I dunno...
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: The bacterium
« Reply #34 on: Mar 30th, 2005, 12:50pm » |
Quote Modify
|
on Mar 30th, 2005, 12:36am, Deedlit wrote:
More generally, given independent and identically distributed random variables X1, X2, ... with finite expectation, we have that [sum]Xi will go to infinity when EX > 0, will go to -infinity when EX < 0, and will oscillate between positive and negative infinitely often when EX = 0 (with probability 1, of course). So for this problem, the bacteria will die out with probability 1 when the expected change in the number of bacteria each step is nonpositive. |
|
I'm not sure how exactly this applies to the problem?
Quote:| Note that P(x) - x is convex, so it will have a root smaller than 1 if and only if the derivative at 1 is positive. |
|
That's it in a nutshell. Quite elegant, no? The only exception is if P(x)=x for all x, i.e., the bacterium just sits there for all eternity.
Now to make (3) more precise:
(a) If EX1>1, show that the probability that the colony ever dies out, given that it's alive at time n, decays exponentially. That is,
P(extinction | Xn > 0) < Ce-cn
for some C,c > 0.
(b) If EX1=1, p0>0, and [sum]pkk2 is finite, show that
c/n < P(Xn>0) < C/n
for some c,C>0. This is a lot trickier.
|
| « Last Edit: Mar 30th, 2005, 12:56pm by Eigenray » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: The bacterium
« Reply #35 on: Mar 31st, 2005, 12:48am » |
Quote Modify
|
on Mar 30th, 2005, 12:50pm, Eigenray wrote:
I'm not sure how exactly this applies to the problem?
|
|
It solves it, doesn't it? The bacteria always die if and only if EX <= 0, or in your terminology, when EX1 <= 1. But random variables are a lot more general, and can include arbitrary real values and continuous distributions.
Quote:
That's it in a nutshell. Quite elegant, no? The only exception is if P(x)=x for all x, i.e., the bacterium just sits there for all eternity.
|
|
Heh... I actually wouldn't have thought to go beyond "smallest root" if not for the random variable answer above - I was curious how the two answers were related.
Quote:
Now to make (3) more precise:
(a) If EX1>1, show that the probability that the colony ever dies out, given that it's alive at time n, decays exponentially. That is,
P(extinction | Xn > 0) < Ce-cn
for some C,c > 0.
|
|
Since the root has multiplicity one, we can draw a tangent line T(x) to P(x) at x=a, and T(x) <= P(x) for x < a. Then we have
T(x) = m(x-a) + a, m < 1
T(a-x) = a - mx
Ti(a-x) = a - mix
Pi(a-x) >= a - mix
P(extinction | Xi > 0) = (a - Pi(0) ) / (1 - Pi(0) ) < mia / (1-a).
Quote:
(b) If EX1=1, p0>0, and [sum]pkk2 is finite, show that
c/n < P(Xn>0) < C/n
for some c,C>0. This is a lot trickier. |
|
P'(1) = [sum] k pk = EX1 = 1, so d(P(x)-x)/dx(1) = 0, so P(x) - x has a double root at x=1. I sorta handwaved at this above, but here's the nitty gritty. There are constants a and b such that
x + a(x-1)2 < P(x) < x + b(x-1)2
for x close to 1. Then
x > 1 - 1/(an) => P(x) > 1 - 1/(an) + a(1/an)2 = 1 - (n - 1)/(an2) > 1 - 1/(a(n+1))
and
x < 1 - 1/(2bn) => P(x) < 1 - 1/(2bn) + b(1/(2bn))2 = 1 - (2n - 1)/(4bn2) <= 1 - /(2b(n+1)).
We can choose a and b so that 1 - 1/a < P(Xn>0) < 1 - 1/(2b), and the result follows.
Note that for multiplicity k > 2, the same argument works - we can choose a and b so that
x + a(x-1)k < P(x) < x + b(x-1)k
and
x > 1 - c/n1/(k-1) => P(x) > 1 - c/n1/(k-1) + a ck/nk/(k-1) > 1 - c/(n+1)1/(k-1)
for suitably chosen a and c, and similarly for b and C.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: The bacterium
« Reply #36 on: Apr 5th, 2005, 3:53pm » |
Quote Modify
|
on Mar 31st, 2005, 12:48am, Deedlit wrote:
It solves it, doesn't it? The bacteria always die if and only if EX <= 0, or in your terminology, when EX1 <= 1. |
|
To be precise,
Xn+1 = Y1n+1+...+YX_nn+1,
where the Yin are independent with the distribution of X1. Sorry, but I still don't see how it follows.
Quote:
P'(1) = [sum] k pk = EX1 = 1, so d(P(x)-x)/dx(1) = 0, so P(x) - x has a double root at x=1. |
|
I'm not sure how much of this is obvious. Does P(x) necessarily have a power series at x=1, valid for x<=1? Or is the condition P''(1) < [infty] enough for the bounds you give?
(P, P', and P'' (by the assumptions [mu]=1, [sigma]<[infty]) certainly converge for x<=1 (Abel's convergence theorem). But if we take, say, pk=b/k4, k>0, where b Zeta(3)=1, and p0+b Zeta(4)=1, then P isn't defined for x>1.)
|
| « Last Edit: Apr 5th, 2005, 3:54pm by Eigenray » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: The bacterium
« Reply #37 on: Apr 6th, 2005, 5:20pm » |
Quote Modify
|
on Apr 5th, 2005, 3:53pm, Eigenray wrote:
To be precise,
Xn+1 = Y1n+1+...+YX_nn+1,
where the Yin are independent with the distribution of X1. Sorry, but I still don't see how it follows.
|
|
The sequence I used was
Xn = [sum]i=1n Yi.
The difference between the two is that your sequence skips ahead Xn terms each step, in terms of my sequence. But that doesn't affect whether it hits zero - from Xn, it takes Xn steps to reach zero anyway. So what I said applies to either version.
Quote:
I'm not sure how much of this is obvious. Does P(x) necessarily have a power series at x=1, valid for x<=1? Or is the condition P''(1) < [infty] enough for the bounds you give?
(P, P', and P'' (by the assumptions [mu]=1, [sigma]<[infty]) certainly converge for x<=1 (Abel's convergence theorem). But if we take, say, pk=b/k4, k>0, where b Zeta(3)=1, and p0+b Zeta(4)=1, then P isn't defined for x>1.) |
|
For some reason, I was thinking of P as a polynomial.  But yes, if P''(X) approaches a positive number at 1, then P(X) will be sandwiched between two quadratics tangent to y=x at 1. (P''(1) must be positive, since EX = 1 and p0 > 0, so we need some pk > 0 with k > 1 to balance it out.)
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: The bacterium
« Reply #38 on: Apr 6th, 2005, 8:09pm » |
Quote Modify
|
on Apr 6th, 2005, 5:20pm, Deedlit wrote:| The difference between the two is that your sequence skips ahead Xn terms each step, in terms of my sequence. |
|
I think it's more than that. Xn+1 is the sum of Xn i.i.d vars with mean [mu]. It's not obtained from Xn by adding on i.i.d vars with mean [mu]-1.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: The bacterium
« Reply #39 on: Apr 6th, 2005, 9:26pm » |
Quote Modify
|
on Apr 6th, 2005, 8:09pm, Eigenray wrote:
I think it's more than that. Xn+1 is the sum of Xn i.i.d vars with mean [mu]. It's not obtained from Xn by adding on i.i.d vars with mean [mu]-1. |
|
The result is the same, though. Adding Xn i.i.d. variables with mean [mu]-1 to Xn gets you the same result as summing Xn i.i.d. variables with mean [mu].
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print