Random Euclidean Matching for exponentially and polynomially decaying densities

This thesis is devoted to the study of the Random Euclidean Matching problem in the case of exponentially and polynomially decaying densities. Such problem consists in finding the optimal matching between a sequence of independent random variables with common probability distribution μ taking values in a domain Ω ⊆ Rd and their reference measure. Such points are denoted by {Xi}ni=1. Here optimal refers to the cost function determined by the power p of the Euclidean distance. More precisely, the problem is to estimate for very large n the expectation E of the cost function determined by the p-Wasserstein distance between two measures: the first one is the empirical measure on the points Xi and the second one is nμ. Briefly speaking, one has to match each point Xi to a region Ωi ⊆ Ω such that μ(Ωi) = n1 in such a way to minimize the Euclidean distance. There are two reasons why one could be interested in studying such quantity. The first one is that it is the semi-discrete version of a problem in which one has to match a sequence of iid points Xi to another sequence of iid points Yj. But it creates much less technical difficulties since in our case one of the two measures is absolutely continuous with respect to the Lebesgue measure. Furthermore, the problem is interesting in its own right because it is related to the estimation of the averaged Wasserstein distance Wp between n points sampled from the distribution μ (the empirical measure) and the distribution itself. Such problem has been deeply studied in the case of variables distributed on bounded connected domains with uniformly positive probability densities, but the results concerning the case of points distributed according to a probability density supported in Rd were much less. There were partial results and conjectures for the Gaussian density in the case p ≤ d and no conjectures at all for p > d. This thesis investigates that direction: we focus on radial probability densities ρ supported in Rd with an exponential and polynomial tail. The Gaussian density is one of these. Our purpose is to prove asymptotic estimates for the expectation E of the cost function we described above in the case of iid points distributed with a probability measure whose density has an exponential and polynomial tail. The strategy of the proof is to adapt the results in the case of bounded connected domains Ω. In the very first part, we focus on the rigorous definition of the problem and on the state of the art. Then, we recall some basic notions and we prove the result we mostly need. In particular, since the Random Matching problem finally turns out to be an Optimal Transport problem, in the following we focus on the couplings between two measures, the Optimal Transport maps and the Benamou-Brenier formula, which leads back the Wasserstein distance to a PDEs problem. Another part is devoted to the concentration properties of binomial random variables, since, given a sequence of iid random variables, the number of them in a fixed region is finally a binomial random variable. Then, since one of the main difficulties in the strategy we will use is the concept of geometric decomposition of the domain, we will need also some extra tools, which we will focus on later. Indeed the geometric decomposition in our case is performed exploiting the symmetries of the density. In particular, to partition the space in much smaller regions, we use the Exponential Map, that projects the tangent space to a manifold (in our case, the sphere) on the manifold itself, and the Haar measure, i.e., the left and right-invariant measure, on the orthogonal group. Therefore some Chapters are dedicated to this. In the very last Chapter we prove our main result: we find a critical exponent pcric at which the rate of the expectation of the cost function for exponentially and polynomially decaying densities changes abruptly. Such pcric depends on the density itself and on the dimension. As we said before, the way we prove it is inspired by the results in the case of bounded and connected domains, but, in order to adapt the proof to an unbounded domain and to a probability density vanishing for large |x|, we need to exploit the radial symmetry of the density. Indeed all the estimates used in the compact case fail in our setting. Our result is the following: we determine the rate of the cost function for any p and d and, for p ≤ pcrit, we prove some more precise estimates about the limit of the cost function divided by its rate.