@Douglas Zare I'm not suggesting that there should be shortcuts. I'm just trying to understand why "waiting to prune all the $B$ elements" at some higher threshold number of $B$ elements, $k$, would make any difference?

@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?

@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.

@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$.

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)$?