MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is an extension of a previous question of mine (nicely answered by Douglas Zare): Filling a bin with one type of element when uniformly selecting from a set of two (with bias)

Say I fill a multiset by flipping a biased coin and putting the element $A$ in the set if I see heads, and $B$ if I see tails. However, as soon as there are $k$ copies of element $B$ in the multiset, I sequentially select elements with uniform probability (regardless of whether they are $A$ or $B$) and prune them until no more copies of $B$ exist. I then return to flipping my coin and filling the multiset in the aforementioned manner. I halt the process when there exists exactly $N$ copies $A$ in the multiset and no copies of $B$.

If we reach $N$ copies of $A$ in the multiset, and we have $>0$ copies of $B$, we automatically begin the pruning process.

My question here is: does the value of $k$ matter when $k \leq N$? If the value does matter, what value minimizes the number of coin flips required to reach the halt state with exactly $N$ copies of the element $A$ in the multiset and no copies of element $B$?

share|cite|improve this question
What do you do if you reach $N$ elements where the count of $B$s is between $1$ and $k-1$? Also, note that if $k \gt 1$ then this procedure is inconsistent, since the operation you perform on a state such as $\lbrace A, B \rbrace$ depends on how you got there. This could only be optimal among all strategies if there is no difference between choosing to flip or prune from that state. That the strategies with $k \gt 1$ are inconsistent does not mean they are worse than $k=1$. – Douglas Zare May 2 '13 at 11:04
@Douglas Zare I have specified that when we reach the state of having $N$ copies of $A$ in the multiset (not $N$ total elements in the multiset) we automatically begin the pruning process as if we had a threshold number $k$ copies of $B$. – VGore May 2 '13 at 11:53
@Douglas Zare I think I understand what you mean. For $k > 1$ the action we perform on the multiset does not strictly depend on the state of the multiset but rather on the set of previous states. I agree, and this is part of why I've found this problem difficult to analyze. – VGore May 2 '13 at 11:56
The difference between higher values of $k$ and $k=1$ can be broken up into individual choices to continue drawing when you have already drawn one or more $B$. If all of these move farther from the finish line on average assuming all subsequent decisions were made according to $k=1$, then they can't be shortcuts. The distance according to $k=1$ can be computed $d_n(p,x,y) = \frac{x+y+1}{y+1} + \sum_{k=0}^x d_n(p,k,0) {x+y-k-1 \choose y-1}/{x+y \choose y}$ for $y \gt 0$, where $d_n(p,x,0) = a(p,n) - a(p,x)$ and $a(p,n)$ is the expected number of removals following $k=1$ to get to $n\times A$. – Douglas Zare May 3 '13 at 2:20
@DouglasZare If we have some scenario 1: $X$ elements of type $A$ and $Y$ elements of type $B$, and scenario 2: $2X$ elements of type $A$ and $Y+1$ elements of type $B$, shouldn't the mean number of elements of type $A$ we need to prune PER elements of type $B$ remain fixed? – VGore May 3 '13 at 3:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.