- We exhaustively compare every item in set $A$ to the items in set $B$, where $A\cap B=\emptyset$, to look for matches.
- We repeat this across iterations, where at every iteration, $|A|=n\gt 0$. At iteration $0$, $|B|=0$, and for subsequent iterations any items from set $A$ without a match are moved to set $B$. Hence, at iteration $1$, $|B|=n$.
- If $a_j\in A$ matches at least one item $b_j\in B$, a match has been successfully found.
- However, $B$ is finite and no item in $B$ can be matched twice in the same iteration.
- There is a fixed probability $\mu$ of any two items matching.
My question is, at iteration $i$, how many elements do we expect to be in set $B$?
I’ve tried writing the maths out in full and constructing a series function. I’ve tried deriving it from scratch using binomial coefficients. I’ve tried using Hypergeometric Distributions.
No luck, even for the expected number of unmatched items in a single iteration. The probability of $a_j$ not finding a match depends on all previous comparisons, $\{a_0,...,a_{j-1}\}$, i.e. $P(a_j)=(1-\mu)^{|B|-\sum_{k=0}^{j-1} P(a_k)}$, which is obviously recursive and I can't find a closed-form solution.
Any help with this please?