A phase transition for the probability of being a maximum among random vectors with general iid coordinates

DOI10.1016/J.SPL.2023.109847MaRDI QIDQ6115504zbMATH OpenOpenAlexFDO

Authors Royi Jacobovic, Or Zuk

Publication date 12 July 2023

Published in Statistics \& Probability Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2112.15534

zbMATH Keywords

extreme valuesmultivariate maximumParetophase transition

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Extreme value theory; extremal stochastic processes (60G70) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Abstract: Consider $n$ iid real-valued random vectors of size $k$ having iid coordinates with a general distribution function $F$. A vector is a maximum if and only if there is no other vector in the sample which weakly dominates it in all coordinates. Let $p_{k,n}$ be the probability that the first vector is a maximum. The main result of the present paper is that if $kequiv{k}_n$ is growing at a slower (faster) rate than a certain factor of $log(n)$, then $p_{k,n}ightarrow0$ (resp. $p_{k,n}ightarrow1$) as $noinfty$. Furthermore, the factor is fully characterized as a functional of $F$. We also study the effect of $F$ on $p_{k,n}$, showing that while $p_{k,n}$ may be highly affected by the choice of $F$, the phase transition is the same for all distribution functions up to a constant factor.

Recommendations

• On the variance of the number of maxima in random vectors and its applications
• Multiple maxima in multivariate samples
• Limit theorems for random maximum of independent and non-identically distributed random vectors
• On the probability of being maximal
• On the average number of maximal in a set of vectors

Cites work

• A note on the expected time for finding maxima by list algorithms
• A Poisson * Geometric Convolution Law for the Number of Components in Unlabelled Combinatorial Structures
• A provably fast linear-expected-time maxima-finding algorithm
• A random forest guided tour
• Consistency of random forests
• scientific article; zbMATH DE number 1281676 (Why is no real title available?)
• scientific article; zbMATH DE number 2038886 (Why is no real title available?)
• Maxima in hypercubes
• Maxima-finding algorithms for multidimensional samples: A two-phase approach
• On the asymptotic distribution of max and mex
• On the Distribution of the Number of Admissible Points in a Vector Random Sample
• On the distribution of the values of arithmetic functions. The number of prime factors of an integer
• On the variance of the number of maxima in random vectors and its applications
• Random inequality constraint systems with few variables
• Supporting-points processes and some of their applications
• The Number of Outcomes in the Pareto-Optimal Set of Discrete Bargaining Games
• The number of two-dimensional maxima

This page was built for publication: A phase transition for the probability of being a maximum among random vectors with general iid coordinates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6115504)