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?



Filling a bin with one type of element when uniformly selecting from a set of two (with bias)
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. 


