I am a young PhD student in statistics. Recently, papers (Ambrosio, Stra and Trevisan; Talagrand; Ledoux to cite but a few) tackled the problem of finding the expected cost in an optimal matching, which is a first-order global understanding of what is going on.

I am wondering if anything is known (I found no paper about this) about the following problem.

Consider an i.i.d. sample $\{X_i\}_{i=1}^n$ where each $X_i$ is a random variable whose distribution is the uniform over $[0,1]^2$. For simplicity we assume $n=k^2, \ k\in \mathbb{N}$. Also set $G$, the grid defined as $G:= \{0,\frac{1}{k-1},\frac{2}{k-1},\cdots,\frac{k-1}{k-1}\} \times \{0,\frac{1}{k-1},\frac{2}{k-1},\cdots,\frac{k-1}{k-1}\} $. Each point of the grid is identified by an (unimportant) index in $\{1,2,...,n\}$. The optimal matching $\pi \in S_n$ ($S_n$ being the set of permutations) is such that $$ \sum_{i=1}^n d(X_i ,G_{\pi(i)})^2=\inf_{\pi^*\in S_n} \sum_{i=1}^n d(X_i ,G_{\pi^*(i)})². $$ The question of interest is to find the p.d.f of ${X_i}$ knowing that it was matched with $G_{\pi(i)}$ and $\pi$ is optimal in the sense defined above.

Simulations suggest that a normal r.v. should asymptotically appear for points in the middle; what happens at the boundary is unclear.

Some thoughts suggests that a combinatorial approach may yield results but it becomes very rapidly intractable. (I managed computing the exact distribution for small n) Trying to maximise entropy given the information we have seems too sloppy. Central limit theorem is obviously not applicable and Stein's method (à la Chatterjee, for instance) looks of little help.

I would be very hapy to discuss the problem and the approach.

Thank you in advance.

Have a great day,


Edit: Here are two elements whose proof I am sure of:

  • The pdfs will be polynomials admitting symmetries.
  • For n=4, the distribution is $-4 x^3 y + 6 x^2 y - 4 x y^3 + 6 x y²$. (To obtain the three other ones, it suffices to replace $x$ by $(1-x)$ or $y$ by $(1-y)$ in the polynomial above)
  • 2
    $\begingroup$ can you specify the question a bit further with a mathematically explicit statement for the benefit of the reader $\endgroup$ – kodlu Jan 30 '19 at 22:34
  • $\begingroup$ Sorry for the lack of clarity, I hope it is clearer now $\endgroup$ – Gilles Mordant Jan 31 '19 at 8:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.