5
$\begingroup$

Consider a circle of unit circumference. Suppose that there are r equidistant red points on the circle. We will drop b>r blue points on the circle. The location of each blue point is iid and uniformly distributed on the circle.

We will match red and blue points so that each red point is matched to exactly one blue point, and each blue point is matched to at most one red. Consider one of the following matching processes:

  1. Pick a red point uniformly at random and match it to the closest blue point. Remove the matched points. Iterate until all red points are matched.
  2. Match blue and red points such that the total distance achieved by the matching is minimized.

Let $X_i$ denote the distance between the $i$th red point, and the blue point it is matched to. What are $\mathbb{E}[X_i]$ and $\mathbb{E}[X_i^2]$? How do they scale with $b$ and $r$?

Finally, suppose that as opposed to unit circle, we have unit disc or square. How do these quantities change?

EDIT: If it simplifies analysis, in matching process 1, it is fine to assume that each red point is matched to the blue point that is closest, in the clock-wise direction.

$\endgroup$
7
  • $\begingroup$ It would be nice if you could drop a couple of lines on the context and the origin of this problem. $\endgroup$ Commented Aug 27, 2017 at 19:27
  • $\begingroup$ I was reading about Poisson matching (e.g., see link), and wanted to explore matching problems with unequal/unbalanced number of points. $\endgroup$
    – Ozzy
    Commented Aug 28, 2017 at 6:11
  • 1
    $\begingroup$ The situation $1$ or the one in the edit are simple exercises in probability. E.g. $E[X_i^k] = 1/\binom{b+k}{k}$ in $1$. $\endgroup$
    – js21
    Commented Aug 28, 2017 at 8:29
  • $\begingroup$ @js21, can you elaborate on how you get the latter expression? I think I wasn't clear. Each red point is matched to exactly one blue point (and each blue point is matched to at most one red point). Moreover, in 1, as you match points, you do not replace the red points. In light of this, I don't see how the expression you derived can be obtained. I'll update the question with clarifications. $\endgroup$
    – Ozzy
    Commented Aug 28, 2017 at 14:21
  • $\begingroup$ @Ozzy: Ah, thanks, it is clearer now. It is indeed harder if matched blue points are deleted. $\endgroup$
    – js21
    Commented Aug 28, 2017 at 14:30

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.