Probability of a complicated problem I have no maths background, but I am looking for an answer for the following problem for work-related purposes.


*

*We have a certain set of actors $A$ and their number is always $n(A)>0$.  

*We have a certain set of enemies $E$ and their number is always $n(E)>0$.  

*Each actor and each enemy may have a flag DO_NOT_PAIR. The probability whether they have a flag or not is not specified. We do know in each case how many actors $A$ or enemies $E$  have the flag.  

*Each actor $A$ randomly chooses its target from a set of enemies $E$.  

*Each enemy $E$ randomly choses its target from a set of actors $A$.  

*For each actor $A$ and for each enemy $E$ we check whether its target has a flag DO_NOT_PAIR. If anyone paired up with a target with a flag, we jump back to step 4 and repeat the algorithm. If no one is paired up with a target with a flag, we finish the algorithm.


The question is:
In certain situations it will be mathematically impossible to pair everyone correctly (for example when all actors or all enemies have a flag). How many jumps from step 6 we must perform in order to ensure that we checked at least $p\%$ of all possible pairings (or if that's not possible to figure out: that we have $c\%$ certainty that we checked $p\%$ of all possible pairings?).
I hope I phrased the problem clearly. English is not my first language and I have at best sub-par knowledge on maths terminology. 
Thanks in advance.
 A: It’s not clear to me why you perform this seemingly wasteful algorithm at all, instead of directly choosing targets only among the potential targets that don’t have the DO_NOT_PAIR flag, but in case you need to:
There are $n(A)$ independent choices with $n(E)$ options each and $n(E)$ independent choices with $n(E)$ options, for a total of $n(A)^{n(E)}n(E)^{n(A)}$ different pairings. (This will typically be a very large number.)
You can’t guarantee that you’ve seen a certain proportion of different pairings after some number of trials because you might always get the same pairing.
The probability distribution of the number of different pairings seen after $n$ trials is that of the coupon collector’s problem. This is given at Probability distribution in the coupon collector's problem. It’s a complicated sum with lots of summands and lots of cancellation for the large numbers that you may be dealing with, so you may want to approximate it, but to provide a useful approximation we’d have to know which regime you’ll be using it in.
