Probabilities in Matching to the closest point

37 Views Asked by At

Suppose that, in a unit interval, there are $n$ red dots and $n$ blue dots. Red dots are drawn independently from a CDF $F$ and blue dots are drawn independently from a CDF $G$.

Suppose that we match a pair of a red dot and a blue dot based on distance: match the closest pair and exclude the matched pair from interval, and then match the closest pair among the remaining dots, and so on.

For example, say that two red dots are located at 0 and 0.5, two blue dots are located at 0.6 and 1. In this case, in the first round, (0.5,0.6) is paired and eliminated, and then (0,1) is matched and eliminated in the second round.

My question is "If a red ball is located at $x$, what is the probability of being eliminated in the $k^{th}$ round?"