4
$\begingroup$

I have two bags: one filled with red marbles, and one filled with blue marbles. I would like to fill a bin with only $k$ red marbles and no blue marbles. However, I can only sample (with replacement) from the bag of red marbles with probability $p$ and from the bag of blue marbles with probability $(1-p)$. Thus, the expected fraction of red marbles in the bin after $N$ additions is $pN$.

However, at any point, I can stop and select marbles from the bin (strictly with uniform probability, regardless of their color) to toss out.

What is an optimal strategy for minimizing the number of marbles rejected / removed from the bin until I reach the state where the bin is filled with only $k$ red marbles (after the aforementioned random walk like process)? What probability distribution should I expect for the number of total number of marble additions and removals from the bin provided some $k$ and $p$?

Update - How might it matter if one chooses to enter the pruning phase when spotting a single blue marble vs. some number of blue marbles $k$? Intuitively, I would expect it wouldn't, but is this provable?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

One strategy is to start removing marbles whenever you have drawn a blue marble. Let $a(p,n)$ be the expected number of removals under this strategy before reaching a collection of $n$ red marbles.

$$a(p,n) = \frac{1}{p} a(p,n-1) + \frac{1-p}{p} \bigg(\frac{n+1}{2} - \frac{1}{n} \sum_{k=0}^{n-1} a(p,k) \bigg)$$

I don't see a closed form. The asymptotic value for $a(1/2,n)$ appears to be $2^{n+2}/n$.

By the way, I think the above strategy is optimal, but I haven't proved this yet. I looked at some other strategies such as only removing marbles when you reach $n$. That takes a random walk on the cube, and in small cases it averages more removals.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I can't understand the recursion or how could it be that it grows by more then a factor of $2$ (for $p=\frac12$) but the asymptotic is less then $2^n$. $\endgroup$
    – Ori Gurel-Gurevich
    Commented May 1, 2013 at 23:44
  • $\begingroup$ @Ori Gurel-Gurevich: $a(p,n)−a(p,n−1)=(1−p)b(p,n)$ where $b(p,n)$ is the average number of removals to go from $n−1$ red, $1$ blue to $n$ red. It takes an average of $(n+1)/2$ removals to get rid of the blue marble, and that leaves you with $b(p,n)=\frac{1}{n}\sum_{k=0}^{n−1}(a(p,n)−a(p,k))$ removals to go. I'm not sure what you mean about the asymptotics being less than $2^n$. The simple strategy of removing everything when you encounter a blue marble takes about $2^{n+1}$ removals. $2^{n+2}/n=2^n \times 4/n$ which is asymptotically less. Where it is greater, $2^{n+2}/n$ isn't yet close. $\endgroup$
    – Douglas Zare
    Commented May 2, 2013 at 2:30
  • $\begingroup$ OK, in that case, the sum in your equation should have a minus sign. This also answers my other comment - I thought that $a(1/2,n)>2 a(1/2,n-1)$ which contradicts an asymptotic of less then $C 2^n$. $\endgroup$
    – Ori Gurel-Gurevich
    Commented May 2, 2013 at 4:56
  • $\begingroup$ Is this then correct? $a(p,n) = \frac{1}{p} a(p,n-1) + \frac{1-p}{p} \bigg(\frac{n+1}{2} - \frac{1}{n} \sum_{k=0}^{n-1} a(p,k) \bigg)$? $\endgroup$
    – VGore
    Commented May 2, 2013 at 5:34
  • $\begingroup$ Oops, yes, I had left out that minus sign. Thanks. $\endgroup$
    – Douglas Zare
    Commented May 2, 2013 at 7:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .