Optimizing the Penalty in an Urn Problem: A Scientific Approach

[RvMiert]

Consider an urn with r red balls and b blue balls. In every turn, one ball is drawn.

When a red ball is drawn, it is put back in the urn together with some extra R red balls.

When a blue ball is drawn, it is left outside the urn.

The questions are:
1. What is the expectation value of the number of blue balls outside the urn, B(n), after n turns?
2. What is the expected number of turns needed to get all the blue balls out of the urn?
3. What minimal value must the penalty have, the number R, to get this number of expected turns to infinity?

 

[viraltux]

Consider an urn with r red balls and b blue balls. In every turn, one ball is drawn.

When a red ball is drawn, it is put back in the urn together with some extra R red balls.

When a blue ball is drawn, it is left outside the urn.

The questions are:
1. What is the expectation value of the number of blue balls outside the urn, B(n), after n turns?
2. What is the expected number of turns needed to get all the blue balls out of the urn?
3. What minimal value must the penalty have, the number R, to get this number of expected turns to infinity?

Hi RvMiert,

I've got the answer for 1. and the equations for 2. and 3. but the kind of equation that it's not easy to find an explicit expression for the solution, so I'm thinking that maybe there is a simpler way to do it. Could you tell us about the background of this problem? Did you find it in a book where the solution is supposed to be a simple expression?

 

[RvMiert]

Hi viraltux,

Well, sometimes when I get bored during lectures, I make up my own questions to see if I can answer them. And this one was quite hard. :P I asked some of my old teachers if they can give me some hints, but they couldn't give me an explicit expression either. For question 1 a recursive expression was found, but then you would need -all- of the previous B(n-k)'s to express the expectation value of B(n). And all of the teachers said that they were quite sure that there has to be an explicit expression, so my search continues. :P

 

[viraltux]

Hi viraltux,

Well, sometimes when I get bored during lectures, I make up my own questions to see if I can answer them. And this one was quite hard. :P I asked some of my old teachers if they can give me some hints, but they couldn't give me an explicit expression either. For question 1 a recursive expression was found, but then you would need -all- of the previous B(n-k)'s to express the expectation value of B(n). And all of the teachers said that they were quite sure that there has to be an explicit expression, so my search continues. :P

Oh you little #@&%! Thanks for the warning! hahaha :rofl:

Since it looked like a book problem I was all the time thinking I was missing something because the first thing I got was the recursive expression too... But anyway, I kept on it and now I think I got the a explicit one in form of a summatory. Since I need 1. to answer questions 2. and 3. I could not get from this summatory an explicit n and R respectively but just the equations to get them, but anyway, now that you explain where the problem comes from with all your professors trying to solve your crazy (but interesting) problem I guess my solution is more than OK now! :tongue:

1. OK, a hint for solving 1. Just consider how the probabilities to get a blue ball behave in n steps in:

$$\frac{b-i}{r+j R + b - i}$$

where $i+j=n$. Then add them up to get the expected value in n steps.

Once we have $E(Bn)$ we can solve 2. and 3. by simply solving these equations numerically:

2. $min \ n |\ E(Bn)\geq b$
3. $min \ R | \forall n \ E(Bn)>b$

 

[alan2]

This is a complicated variation of Polya's urn. I think you have a publishable paper if you solve it. The real problem is that you have no symmetry between the two colors of balls. It is the symmetry which normally allows problems of this type to be solved.

 

[RvMiert]

Well, I did have some progression before I went to my teachers.



The expectation value of the first turn is easy,
\begin{equation} \mathbb{E}\left[ {{B_1}} \right] = \frac{b}{{r + b}} \end{equation}.

And also it is not hard to find that
\begin{equation} \mathbb{P}\left[ {\left. {{B_n} = {B_{n - 1}} + 1} \right|{B_{n - 1}}} \right] = \frac{{b - {B_{n - 1}}}}{{r + b + R \cdot \left( {n - {B_{n - 1}}} \right) - {B_{n - 1}}}} \end{equation},
\begin{equation} \mathbb{P}\left[ {\left. {{B_n} = {B_{n - 1}}} \right|{B_{n - 1}}} \right] = \frac{{r + R \cdot \left( {n - {B_{n - 1}}} \right)}}{{r + b + R \cdot \left( {n - {B_{n - 1}}} \right) - {B_{n - 1}}}} \end{equation}.

So
\begin{gathered}
\mathbb{E}\left[ {\left. {{B_n}} \right|{B_{n - 1}} = k} \right] = k\mathbb{P}\left( {\left. {{B_n} = {B_{n - 1}}} \right|{B_{n - 1}} = k} \right) + \left( {k + 1} \right)\mathbb{P}\left( {\left. {{B_n} = {B_{n - 1}} + 1} \right|{B_{n - 1}} = k} \right) \\
= k + \frac{{b - k}}{{r + b + R \cdot \left( {n - k} \right) - k}}\\
\end{gathered}.

And then
\begin{equation} \mathbb{E}\left[ {\left. {{B_n}} \right|{B_{n - 1}},...,{B_1}} \right] = \sum\nolimits_{k = 0}^{n - 1} {\frac{{b - {B_k}}}{{r + b + R \cdot \left( {n - {B_k}} \right) - {B_k}}}} \end{equation}

But then what...? :P

 

[viraltux]

Well, I did have some progression before I went to my teachers.

\begin{equation} \mathbb{E}\left[ {\left. {{B_n}} \right|{B_{n - 1}},...,{B_1}} \right] = \sum\nolimits_{k = 0}^{n - 1} {\frac{{b - {B_k}}}{{r + b + R \cdot \left( {n - {B_k}} \right) - {B_k}}}} \end{equation}

But then what...? :P

Well, I got a different recursive expression based on the number of red and blue balls from the previous step, but anyway, that didn't help either for the explicit expression.

What I did is to build a probability tree for the red and blue balls, so for a particular level k I found this relationship:

$$P(Bk)=\sum_{\forall i,j |\ i+j=k} {k \choose i} \frac{b-i}{r+j R + b - i}$$

And therefore:

$$E(Bn)= \sum_{k=0}^{n-1} \sum_{\forall i,j |\ i+j=k} {k \choose i} \frac{b-i}{r+j R + b - i}$$

Now, I didn't check this thoroughly because I thought your question was a book style problem and I had the feeling I might be going overboard with this solution, that's when I asked you about the background of the problem, but at the very least I hope this helps :tongue:

 

[RvMiert]

What I did is to build a probability tree for the red and blue balls, so for a particular level k I found this relationship:

$$P(Bk)=\sum_{\forall i,j |\ i+j=k} {k \choose i} \frac{b-i}{r+j R + b - i}$$

I don't get it. What exactly is P(Bk)? The probability that B_n = k? And how can it be a sum of scaled probabilities? Because, all ready in the second turn, you would get a product of probabilities.

Say that p_b is the probability to draw a blue ball, p_bb to draw blue when blue is drawn in the first turn, p_br to draw red when blue is drawn in the first turn, etc. Then P(B_2=k) will at least consists of some combinations of p_b*p_bb, p_b*p_br, etc. So I don't see how it can be expressed just as a sum.

 

[viraltux]

I don't get it. What exactly is P(Bk)? The probability that B_n = k? And how can it be a sum of scaled probabilities? Because, all ready in the second turn, you would get a product of probabilities.

Say that p_b is the probability to draw a blue ball, p_bb to draw blue when blue is drawn in the first turn, p_br to draw red when blue is drawn in the first turn, etc. Then P(B_2=k) will at least consists of some combinations of p_b*p_bb, p_b*p_br, etc. So I don't see how it can be expressed just as a sum.

Yeah, you're right, I am missing the products. What I did is

in the first draw the probability to get a blue ball is $\frac{b}{r + b}$

The second round the probability to get a blue ball is

if red in the first round: $\frac{b}{r +R + b}$
if blue in the first round: $\frac{b-1}{r + b-1}$

And so on... Before I just copied the formula too fast from my scribbles, sorry for that, the right one is:

$$E(B_n)=\sum_{\forall i,j |\ i+j=n-1} {n-1 \choose i} \frac{b-i}{r+j R + b - i}$$

Which is the expected value of blue balls in the n_th draw. So for instance, for n=1 you get

$$E(B_1)=\sum_{\forall i,j |\ i+j=0} {0 \choose 0} \frac{b-0}{r+0 R + b - 0} = \frac{b }{r + b }$$

for n=2

$$E(B_2)=\sum_{\forall i,j |\ i+j=1} {1 \choose i} \frac{b-i}{r+j R + b - i} = \frac{b}{r+R+b}+ \frac{b -1}{r + b-1 }$$

And so on... but missing the products so... yep. This summatory is just the sum of the probability tree level probabilities.

Nonetheless, I am certain this problem has a summatory solution since I remember a theorem which says that for any recursive algorithm there is an iterative (and therefore summatory) counterpart. I also remember the technique to transform recursion into iteration was a bit convoluted but it is there. So though the summatory I've got misses something you can always resort to the recursion into iteration technique to get an explicit expression.

 

[RvMiert]

for n=2

$$E(B_2)=\sum_{\forall i,j |\ i+j=1} {1 \choose i} \frac{b-i}{r+j R + b - i} = \frac{b}{r+R+b}+ \frac{b -1}{r + b-1 }$$

Still, I´m sorry :P, I don't see how this can be right. If I completely wright it out, I get
$${\Bbb P}_\text{b}={\Bbb P}\left( {n = 1,{\text{ blue ball}}} \right) = \frac{b}{{r + b}}$$
$${\Bbb P}_\text{r}={\Bbb P}\left( {n = 1,{\text{ red ball}}} \right) = \frac{r}{{r + b}}$$

$${\Bbb P}_\text{bb}={\Bbb P}\left( {\left. {n = 2,{\text{ blue ball}}} \right|n = 1,{\text{blue ball}}} \right) = \frac{{b - 1}}{{r + b - 1}}$$
$${\Bbb P}_\text{br}={\Bbb P}\left( {\left. {n = 2,{\text{ red ball}}} \right|n = 1,{\text{blue ball}}} \right) = \frac{r}{{r + b - 1}}$$
$${\Bbb P}_\text{rb}={\Bbb P}\left( {\left. {n = 2,{\text{ blue ball}}} \right|n = 1,{\text{red ball}}} \right) = \frac{b}{{r + R + b}}$$
$${\Bbb P}_\text{rr}={\Bbb P}\left( {\left. {n = 2,{\text{ red ball}}} \right|n = 1,{\text{red ball}}} \right) = \frac{{r + R}}{{r + R + b}}$$

So the expectation value of blue balls outside the urn, after 2 turns is given by
${\Bbb E}\left[ {{B_2}} \right] = 2{{\Bbb P}_{\text{b}}}{{\Bbb P}_{{\text{bb}}}} + 1{{\Bbb P}_{\text{b}}}{{\Bbb P}_{{\text{br}}}} + 1{{\Bbb P}_{\text{r}}}{{\Bbb P}_{{\text{rb}}}} + 0{{\Bbb P}_{\text{r}}}{{\Bbb P}_{{\text{rr}}}} = \frac{{2b\left( {b - 1} \right) + br}}{{\left( {r + b} \right)\left( {r + b - 1} \right)}} + \frac{{br}}{{\left( {r + b} \right)\left( {r + b + R} \right)}}$

 

[viraltux]

Is not right, is missing the products :tongue:

 

[RvMiert]

Is not right, is missing the products :tongue:

Ow haha, you've said it already ^^ Read it too fast.