anh1l1ator's blog

Probability Problem
By anh1l1ator, history, 9 years ago, In English

There exists 4 bacteria in your shoes at time t=0 seconds.

A bacteria replicate into 2 with a probability p and otherwise die every second.
What is the expected number of bacteria's at the end of 70 seconds.

Constraints:
(0<=p<=1)
And you have to report the floor of the answer.

I saw this question on a test which allowed usage of computer but I think it can be done using total maths too.
I thought of doing a dp with state { time , number of bacteria's } which is exponential in nature.
Either way I don't have a solution.
Obviously, if we can solve it for 1 bacteria we can solve it for 4 too but this isn't a significant improvement either .

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Let's say we have 1 bacteria. After 1 second the expected number of bacteria will be p·2 + (1 - p)·0 = 2p. So, in 1 second the expected number is increased 2p times (you must use the linearity of EV to prove it). After 70 seconds it will be (2p)70.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Shouldn't it be multiplied by 4 because there are 4 bacteria initially?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      If you want the answer for 4 bacteria then sure, it must be multiplied by 4, so: 4·(2p)70

      → Reply