wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> The bacterium
        
(Message started by: Wah on Jan 21st, 2003, 9:27pm)
Title: The bacterium
Post by Wah on Jan 21st, 2003, 9:27pm
A bacterium splits into two identical ones with probability p, otherwise it dies.  What is the probability that, beginning with this one bacterium, the colony lasts forever? ;D
Title: Re: The bacterium
Post by towr on Jan 21st, 2003, 11:53pm
interesting puzzle..

I have no idea on how to solve it..
Title: Re: The bacterium
Post by william wu on Jan 22nd, 2003, 1:15am
My almost complete solution below -- i invite someone else to finish it -- using the newly implemented hide tags:

[hide]
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.
[/hide]
Title: Re: The bacterium
Post by Wah on Jan 22nd, 2003, 5:55am
that was definitely a clever answer. :o
Title: Re: The bacterium
Post by towr on Jan 22nd, 2003, 8:54am
quite a clever solution.. I wish I thought of it :p


on 01/22/03 at 01:15:39, william wu wrote:
How do you know which value for s is valid? I'll let someone else finish this up.

well, if you take p = 0.2, then s would be 4 in the latter case, and s has to be between 0 and 1, so only the other option is left..

On the other hand if p=1, then the colony obviously will survive.. so the former doesn't work out really..

[note]the hide tags don't work when quoted[/note]
Title: Re: The bacterium
Post by BNC on Jan 22nd, 2003, 9:41am
To follow up on towr an WW:

If p<0.5, s=1 and the bacteria colony is doomed.
If p>0.5, s=1/p-1, and the colony has a fair shot.

p=0.5 yield the same result for both solutions, and is the border case.
Title: Re: The bacterium
Post by william wu on Jan 22nd, 2003, 10:01am
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?
Title: Re: The bacterium
Post by BNC on Jan 22nd, 2003, 10:39am
These type of problems are solved using Markov chains. This riddle, nice and hard as it is, is but a simple case. Real-life scenarios (birth-probability, death-probability, migration probability, over-crowding) are much more difficult.
Title: Re: The bacterium
Post by Wah on Jan 23rd, 2003, 4:13am
i am convinced about the above solution
but one of my friend cam up with the folowing and i can't see the flaw in it



here it goes:
"Chance of 1 bacteria splitting = p

Chance of 1 bacteria dieing = 1 - p

If p occurs, number of bacteria "n" = n + 1

If 1 - p occurs, number of bacteria "n" = n - 1

At any given point in time, the colony will have n bacteria in it. The chance of ALL bacteria splitting is p to the power n. The chance of ALL bacteria dieing is (1-p) to the power n. All other results will result in a change in the value of n, because as long as at least ONE bacteria splits, the colony will exist for the next stage of splitting.

Therefore, in order for the bacteria colony to exist, at least ONE bacteria must split at each stage of multiplication, because if it doesn't, then that means that all bacteria have died.

The probability of AT LEAST ONE bacteria splitting is equal to 1 - the probability of all bacteria dieing, which is:

1 - ( ( 1 - p ) to the power n )

In order for a colony to exist forever, then this event needs to occur EVERY SINGLE TIME. n is variable based on what the value of n was last time.

so the probability of the colony existing after 3 multiplications is:

(1-((1-p)^n1)) * (1-((1-p)^n2)) * (1-((1-p)^n3))

In order for the colony to exist forever, then this needs to go on for infinity: (1-((1-p)^n1)) * (1-((1-p)^n2)) *. . . * (1-((1-p)^ninfinity))

Because n is always a positive whole number >1 , it means that each one of these expressions will ALWAYS be LESS than one.

So what your saying is you have an INFINITE number of numbers less than one which you are multiplying together.

Which is 1/infinity.

So the probability of a colony existing FOREVER is 1/infinity.

Which, in my book, is ZERO. "
Title: Re: The bacterium
Post by Icarus on Jan 23rd, 2003, 6:57pm
If you could show that the multiplicands in your product are bounded away from 1, then you can claim rightly that the limit is zero. But in fact if the exponents climb, the multiplicands converge to 1, which allows the product to converge to a limit greater than zero.

Here is an example of an infinite product of numbers less than one that converges to a non-zero result:
http://tcw2.ppsw.rug.nl/~towr/PHP/formula.php?formula=%5Cprod_%7Bn%3D0%7D%5E%7B%5Cinfty%7D+2%5E%7B-2%5E%7B-n%7D%7D+%3D+%7B1+%5Cover+4%7D

(Thanks, towr, for this great formula generator!)

If you can't see the formula, here it is using the new math symbolry:

[prod]n=0[supinfty] 2-2[supminus][supn] = 1/4
Title: Re: The bacterium
Post by william wu on Jan 31st, 2003, 2:27pm
Right ... if you have a term like (1-((1-p)^n)) and the n is very large, then that term will be close to 1. And 0.9999 ... = 1. (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1027804564)

Besides, you would expect the answer to vary between 0 and 1; your friend is suggesting that the colony is either guaranteed immortality (when p = 1) or guaranteed extinction (when p < 1)!
Title: Re: The bacterium
Post by Chronos on Feb 3rd, 2003, 5:34pm
But in any event, you certainly can't guarantee immortality unless p=1.  If p is less than 1 by any amount, then there's a nonzero chance of the "colony" dying off rightat the outset, before any reproduction has  occured.
Title: Re: The bacterium
Post by NickH on Feb 9th, 2003, 8:38pm
Here's another approach.

Let Pn be the probability that n bacteria will eventually become extinct.  By independence, Pn = P1n.

The probability of the colony becoming extinct after the first split is (P0 + P2)/2.  But this is just P1.

Setting P1 = p, we have p = (1 + p2)/2, from which p = 1.

So the colony survives indefinitely with probability 0.

Of course, we should get the same answer if we allow each bacterium three (equally likely) choices: die, do nothing, or split in two.  And indeed we then have p = (1 + p + p2)/3, which again yields p = 1.

Suppose now we allow the bacterium a different three choices: die, split in two, or split in three.  Then p = (1 + p2 + p3)/3, from which p = 1 or p = sqrt(2) - 1.  I believe the latter is the correct answer, but how can we justify excluding p = 1?
Title: Re: The bacterium
Post by James Fingas on Feb 10th, 2003, 11:42am
NickH,

I don't agree.


Quote:
The probability of the colony becoming extinct after the first split is (P0 + P2)/2.  But this is just P1.


From what I understand, you are say: "with probability 0.5, the colony dies the first step, and with probability 0.5, it turns into a colony of size 2, with probability of dying of surviving P2"

The problem with this is that it doesn't always die with probability 0.5 in the first step. The original problem statement calls the probability of it dying on the first step (1-p), but that won't work with your assignment of p, so let's call this probability q. Then:

Therefore, P1 = (1-q)P2 + qP0 = p2(1-q) + q

In other words, we can find q in terms of p, but we can't directly find p by this method. But, when you consider that all we wanted to do was to find p in terms of q, then you have solved the problem in a very simple way! (although it is the same solution that William posted)

I don't agree that the probability of the colony surviving is always 0. Take a look at the "simple game" thread; I think you'll notice a lot of similarities to this problem.

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1028570694
Title: Re: The bacterium
Post by NickH on Feb 10th, 2003, 3:33pm
James,

You're right, of course.  I misread the question and ended up answering a different (though interesting) one!  Scratch the above post.

Nick
Title: Re: The bacterium
Post by Eigenray on Nov 3rd, 2003, 5:43am
To prove convergence, let pn be the probability that the bacteria have died out by n generations.  We're interested in the limit of pn as n goes to infinity.  Note that pn is increasing, and bounded above, so it must converge.  Also, the probability of k bacteria all dying out after n generations is simply pnk.  Therefore:
p1 = 1-p
pn+1 = 1-p + p pn2.
Since pn converges, it must converge to a fixed point of the map f(x) = 1 - p + px2.
This map has two fixed points, 1 and (1-p)/p.
For 0<x<1, we have x < f(x) = 1-p(1-x^2) < 1, so that the limit of the pn can't exceed 1.
When p <= 1/2, (1-p)/p >= 1, so they converge to 1.
If p > 1/2, and p1 <= x < (p-1)/p, then x < f(x) < 1-p+p[(p-1)/p]2 = (1-p)/p < 1, so they must converge to (1-p)/p.

Therefore the colony survives with probability 0 when p <= 1/2, and with probability 2-1/p when p > 1/2.
Title: Re: The bacterium
Post by Icarus on Nov 3rd, 2003, 6:04pm
A nice clean-up of William's solution. I don't know that convergence of pn really needed to be proven, since some simple considerations make it obvious, but as a mathematician, I have to approve!

(you better correct the typo in the last line, or else I'll have to do it).


Looking back through this thread has reminded me of a curiosity I noticed some time back involving my refutation of Wah's friend's argument. If you call up the formula examples page (http://tcw2.ppsw.rug.nl/~towr/PHP/FORMULA/formulaexamples.php) of towr's formula generator, you will see that while all other formulas in it rate less than 400 requests, the one I created above has over 5400. If this were some profound piece of mathematics I could understand it, but it's just a throw-out formula I cooked up to demonstrate a falacy that is also refuted by any decent low-level analysis textbook.

Towr - do you have any idea why this formula was so popular, or is this the result of some error in the page's statistics?
Title: Re: The bacterium
Post by towr on Nov 4th, 2003, 12:20am

on 11/03/03 at 18:04:17, Icarus wrote:
Towr - do you have any idea why this formula was so popular, or is this the result of some error in the page's statistics?
I don't know, perhaps someone else on the web uses it on a page. It can't be from this thread since it's not nearly been read that many times.. Though it might occasionaly show up on a search-result page..
I don't think it's an error, but I could check and look in some of my backup-files if I can find anything..

[edit]Oh my goodness.. I think someone used it as an avatar  ::)
At a highschool forum no less.. But I don't know who since he seems to have changed it.. (Which is why I think it was an avatar, since on most forums that completely disappears from all posts once it is changed in the profile)

After crossreferencing two threads (found in my backups), and this forum, I've come to the conclusion it was KicksGenius (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=;action=viewprofile;username=KicksGenius)[/edit]
Title: Re: The bacterium
Post by Icarus on Nov 4th, 2003, 9:54am
That explains it! Alex is more than welcome to use it as far as I am concerned. I was just curious why it had so many hits.

And I suppose it could be considered far more profound from the point of view of a 15-year old, for whom the mathematics behind it is still something to be grasped, than it is for a 41-year old who dredged it up out of mathematics mastered before the 15-year old was born.
Title: Re: The bacterium
Post by towr on Nov 4th, 2003, 11:07am

on 11/04/03 at 09:54:39, Icarus wrote:
That explains it! Alex is more than welcome to use it as far as I am concerned. I was just curious why it had so many hits.
He allready stopped using it months ago, but it's an interesting avatar-choice. Most people wouldn't think to use a formula (well maybe E=mc^2)
Title: Re: The bacterium
Post by THUDandBLUNDER on Nov 4th, 2003, 11:35am

Quote:
Here is an example of an infinite product of numbers less than one that converges to a non-zero result:

What does this converge to?
Title: Re: The bacterium
Post by towr on Nov 4th, 2003, 12:11pm
::[hide]lim n->inf - 2/(3·(n + 1)) + 2/(3·n) + 2/3 = 2/3[/hide]::
Title: Re: The bacterium
Post by Icarus on Nov 4th, 2003, 4:54pm
I must admit that my product-finding skills are rusty. The one I chose above was picked specifically to be obvious in its convergence and limit.

Proving convergence is easy (with that handy-dandy convergence theorem again: A product of {1 + un} converges iff the sum of {un} converges). In this case, uk = -2/(k3 + 1), which converges with the series {1/k3}. Since the latter series is well-known to converge, so does the product.

But so far I haven't found the method that allowed towr to produce the answer so easily.
Title: Re: The bacterium
Post by TimMann on Nov 4th, 2003, 11:10pm

on 01/22/03 at 10:39:11, BNC wrote:
These type of problems are solved using Markov chains.

Hey, a Markov chain problem that I haven't jumped in on yet.

OK, assuming that p<1, this problem is clearly an absorbing Markov chain with only one absorbing state.  That is, there is one state (0 bacteria) from which you cannot get to any other state, but it is possible (no matter how improbable) to get from any of the non-absorbing states to the absorbing state in a finite number of steps.

Therefore the process converges to the absorbing state. With probability 1, the colony eventually dies out.

(Of course the colony lasts forever if p=1, because then you can't get to the absorbing state; in fact in the number of bacteria can never decrease.)

See the reference I gave in this thread (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1066763305).
Title: Re: The bacterium
Post by towr on Nov 5th, 2003, 12:51am

on 11/04/03 at 16:54:25, Icarus wrote:
But so far I haven't found the method that allowed towr to produce the answer so easily.
I had a little help from my computer, though it needed a lot of help from my side  ::)
The main idea is splitting the product (from 2 to n) into two, and each reduces to a simple formula in terms of n, then take the limit for n to [infty]
Title: Re: The bacterium
Post by towr on Nov 5th, 2003, 12:54am

on 11/04/03 at 23:10:42, 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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1066763305).
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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1054069556;start=16).
'infinity' is another absorbing state in a sense..
Title: Re: The bacterium
Post by Eigenray on Nov 5th, 2003, 2:01am

on 11/04/03 at 16:54:25, 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: [hide]
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[/hide].

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.
Title: Re: The bacterium
Post by TimMann on Nov 6th, 2003, 12:00am

on 11/05/03 at 00:54:07, 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.
Title: Re: The bacterium
Post by pjay on Dec 25th, 2003, 12:13pm
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).
Title: Re: The bacterium
Post by grimbal on Apr 27th, 2004, 4:20pm
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.
Title: Re: The bacterium
Post by Eigenray on Jan 23rd, 2005, 5:57pm

on 01/22/03 at 10:01:15, 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).
Title: Re: The bacterium
Post by Eigenray on Mar 15th, 2005, 5:29pm
I guess I'll answer the first (easy) part:

on 01/23/05 at 17:57:15, 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 ?
Title: Re: The bacterium
Post by kris on Mar 29th, 2005, 8:36am

on 01/22/03 at 01:15:39, william wu wrote:
My almost complete solution below -- i invite someone else to finish it -- using the newly implemented hide tags:

[hide]
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.
[/hide]



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
Title: Re: The bacterium
Post by Deedlit on Mar 30th, 2005, 12:36am

on 01/23/05 at 17:57:15, 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...
Title: Re: The bacterium
Post by Eigenray on Mar 30th, 2005, 12:50pm

on 03/30/05 at 00:36:24, 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.
Title: Re: The bacterium
Post by Deedlit on Mar 31st, 2005, 12:48am

on 03/30/05 at 12:50:59, 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.
Title: Re: The bacterium
Post by Eigenray on Apr 5th, 2005, 3:53pm

on 03/31/05 at 00:48:40, 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.)
Title: Re: The bacterium
Post by Deedlit on Apr 6th, 2005, 5:20pm

on 04/05/05 at 15:53:25, 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.)
Title: Re: The bacterium
Post by Eigenray on Apr 6th, 2005, 8:09pm

on 04/06/05 at 17:20:24, 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.
Title: Re: The bacterium
Post by Deedlit on Apr 6th, 2005, 9:26pm

on 04/06/05 at 20:09:38, 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].


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board