Bagel monster eats bagels

Question

Say I have 3 big bagels and 7 tiny bagels in a bag. Every minute, Bagel Monster randomly picks a bagel from the bag. If it's a tiny bagel, it's eaten; if it's a big bagel, it's cut into 2 pieces, where one half is eaten and the other half is put back into the bag as a tiny bagel. After how many minutes is it expected for the bag to have only tiny bagels left?

Answer 1

Let $n$ be the number of tiny bagels, $m$ - the number of big bagels at some time.

Let also $E_{n,m}$ - expected time to result (to moment, when $n=0$).

So $$E_{0,m} = 0,\quad m=0,1,2,...10$$

Also from state $E_{n,m}$ we can move to $E_{n,m-1}$ with probability $\dfrac{m}{m+n}$ or to $E_{n-1,m+1}$ with probability $\dfrac{n}{m+n}$, so $$E_{n,m} = \dfrac{m}{m+n}\left(E_{n,m-1} + 1 \right) + \dfrac{n}{m+n}\left(E_{n-1,m+1} + 1 \right)= \dfrac{m}{m+n}E_{n,m-1} + \dfrac{n}{m+n}E_{n-1,m+1} + 1$$

Using this conditions we can find $E_{1,m}$ for $ m=0,1,2,...10$:

$$E_{1,0} = \dfrac{0}{1}E_{1,-1} + \dfrac{1}{1}E_{0,1}+1 = 1$$

$$E_{1,m} = \dfrac{m}{m+1}E_{1,m-1} + \dfrac{1}{m+1}E_{0,m+1} + 1 = \dfrac{m}{m+1}E_{1,m-1} + 1$$

We can use formula for $E_{1,m-1}$:

$$E_{1,m} = \dfrac{m}{m+1}\left(\dfrac{m-1}{m}E_{1,m-2} + \dfrac{1}{m}E_{0,m} + 1\right) + 1 = \dfrac{m-1}{m+1}E_{1,m-2} + 1 + \dfrac{m}{m+1}$$

If we continue this process as result we have:

$$E_{1,m} = \dfrac{1}{m+1}E_{1,0} + \dfrac{1}{m+1}\sum_{i=2}^{m+1}i = \dfrac{1}{m+1}\sum_{i=1}^{m+1} = \dfrac{m+2}{2} = 1 + \dfrac{m}{2}$$

Now we can find $E_{2,m}$ for $ m=0,1,2,...9$ the same as with $E_{1,m}$:

$$E_{2,0} = \dfrac{0}{2}E_{2,-1} + \dfrac{2}{2}E_{1,1}+1 = 0 + \dfrac{1+2}{2} +1 = \dfrac{5}{2}$$

$$E_{2,m} = \dfrac{m}{m+2}E_{2,m-1} + \dfrac{2}{m+2}E_{1,m+1}+1 = $$ $$= \dfrac{m}{m+2}E_{2,m-1} + \dfrac{2}{m+2}\dfrac{m+3}{2} + 1 = \dfrac{m}{m+2}E_{2,m-1} + \dfrac{1}{m+2} + 2$$

As result:

$$E_{2,m} = \dfrac{5}{2} + \dfrac{2}{3}m = \dfrac{15 + 4m}{6}$$

Finally we can find $E_{3,m}$ for $ m=0,1,2,...8$ the same as with $E_{2,m}$:

$$E_{3,0} = \dfrac{0}{3}E_{3,-1} + \dfrac{3}{3}E_{2,1}+1 = 0 + \dfrac{15 + 4}{6} +1 = \dfrac{25}{6}$$

$$E_{3,m} = \dfrac{25}{6} + \dfrac{3}{4}m = \dfrac{50 + 9m}{12}$$

The answer of our problem is $E_{3,7}$:

$$E_{3,10} = \dfrac{50 + 9\cdot7}{12}=\dfrac{113}{12}$$

Answer 2

This is not meant to be an answer
This is just a piece of code which calculates this expected value, don't take it as an answer! Take it as a tool to help yourself if you want to work on this problem.

The code:

#include <cstdio>
#include <cstdlib>
int main(int args,char **argv){
    #define LOL {printf("LOL\n");return 1;}
    if(args!=3)LOL
    int B=atoi(argv[1]);
    int S=atoi(argv[2]);
    if((B<0)|(S<0)|((B==0)&(S==0))|(B>100)|(S>100))LOL
    float _f[(B+S+1)*(B+1)];
    #define f(x,y) _f[(x)*(B+S+1)+y]
    for(int i=0;i<=B+S;++i)f(0,i)=0;
    for(int j=1;j<=B;++j){
        f(j,0)=1+f(j-1,1);
        for(int i=1;i+j<=B+S;++i)
            f(j,i)=1+(f(j,i-1)*i+f(j-1,i+1)*j)/(float)(i+j);
    }
    printf("%f\n",f(B,S));
    return 0;
}

The output for 3 7 is $\frac{113}{12}$.