# Maxima and near-maxima of a Gaussian random assignment field

*Gilles Mordant* and
*Johan Segers*

*Statistics & Probability Letters*, 2021, vol. 173, issue C

**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)

**Date:** 2021

**References:** View references in EconPapers View complete reference list from CitEc

**Citations:** Track citations by RSS feed

**Downloads:** (external link)

http://www.sciencedirect.com/science/article/pii/S0167715221000493

Full text for ScienceDirect subscribers only

**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:eee:stapro:v:173:y:2021:i:c:s0167715221000493

**Ordering information:** This journal article can be ordered from

http://www.elsevier.com/wps/find/supportfaq.cws_home/regional

https://shop.elsevie ... _01_ooc_1&version=01

**DOI:** 10.1016/j.spl.2021.109087

Access Statistics for this article

Statistics & Probability Letters is currently edited by *Somnath Datta* and *Hira L. Koul*

More articles in Statistics & Probability Letters from Elsevier

Bibliographic data for series maintained by Catherine Liu ().