Maxima and near-maxima of a Gaussian random assignment field

Gilles Mordant and Johan Segers
Additional contact information
Gilles Mordant: Université catholique de Louvain, LIDAM/ISBA, Belgium
Johan Segers: Université catholique de Louvain, LIDAM/ISBA, Belgium

No 2021008, LIDAM Discussion Papers ISBA from Université catholique de Louvain, Institute of Statistics, Biostatistics and Actuarial Sciences (ISBA)

Abstract: The assumption that the elements of the cost matrix in the classical assignment problem are drawn independently from a standard Gaussian distribution motivates the study of a particular Gaussian field indexed by the symmetric permutation group. The correlation structure of the field is determined by the Hamming distance between two permutations. The expectation of the maximum of the field is shown to go to infinity in the same way as if all variables of the field were independent. However, the variance of the maximum is shown to converge to zero at a rate which is slower than under independence, as the variance cannot be smaller than the one of the cost of the average assignment. Still, the convergence to zero of the variance means that the maximum possesses a property known as superconcentration. Finally, the dimension of the set of near-optimal assignments is shown to converge to zero.

Keywords: Extremal field; Gaussian random field; near maximal set; random assignment; superconcentration (search for similar items in EconPapers)
Pages: 9
Date: 2021-01-01
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://dial.uclouvain.be/pr/boreal/fr/object/bore ... tastream/PDF_01/view (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:aiz:louvad:2021008

Access Statistics for this paper

More papers in LIDAM Discussion Papers ISBA from Université catholique de Louvain, Institute of Statistics, Biostatistics and Actuarial Sciences (ISBA) Voie du Roman Pays 20, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Nadja Peiffer ().