2026-07-23T20:02:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20463 2024-07-18T12:12:43Z ddc:004 open_access

Sharpened Localization of the Trailing Point of the Pareto Record Frontier Fill, James Allen Naiman, Daniel Q. Sun, Ao Multivariate records Pareto records generators interior generators minima maxima record-setting region frontier current records boundary-crossing probabilities first moment method second moment method orthants For d ≥ 2 and i.i.d. d-dimensional observations X^{(1)}, X^{(2)}, … with independent Exponential(1) coordinates, we revisit the study by Fill and Naiman (Electron. J. Probab., 25:Paper No. 92, 24 pp., 2020) of the boundary (relative to the closed positive orthant), or "frontier", F_n of the closed Pareto record-setting (RS) region RS_n := {0 ≤ x ∈ R^d: x ⊀ X^(i) for all 1 ≤ i ≤ n} at time n, where 0 ≤ x means that 0 ≤ x_j for 1 ≤ j ≤ d and x ≺ y means that x_j < y_j for 1 ≤ j ≤ d. With x_+ : = ∑_{j = 1}^d x_j = ‖x‖₁, let F_n^- := min{x_+: x ∈ F_n} and F_n^+ : = max{x_+: x ∈ F_n}. Almost surely, there are for each n unique vectors λ_n ∈ F_n and τ_n ∈ F_n such that F_n^+ = (λ_n)_+ and F_n^- = (τ_n)_+; we refer to λ_n and τ_n as the leading and trailing points, respectively, of the frontier. Fill and Naiman provided rather sharp information about the typical and almost sure behavior of F^+, but somewhat crude information about F^-, namely, that for any ε > 0 and c_n → ∞ we have P(F_n^- - ln n ∈ (- (2 + ε) ln ln ln n, c_n)) → 1 (describing typical behavior) and almost surely limsup (F_n^- - ln n)/(ln ln n) ≤ 0 and liminf (F_n^- - ln n)/(ln ln ln n) ∈ [-2, -1]. In this extended abstract we use the theory of generators (minima of F_n) together with the first- and second-moment methods to improve considerably the trailing-point location results to F_n^- - (ln n - ln ln ln n) ⟶P -ln(d - 1) (describing typical behavior) and, for d ≥ 3, almost surely limsup [F_n^- -(ln n - ln ln ln n)] ≤ -ln(d - 2) + ln 2 and liminf [F_n^- -(ln n - ln ln ln n)] ≥ -ln d - ln 2. Schloss Dagstuhl – Leibniz-Zentrum für Informatik James Allen Fill and Daniel Q. Naiman and Ao Sun 2024 Is Part Of LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2024.28 urn:nbn:de:0030-drops-204631 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.28 eng https://creativecommons.org/licenses/by/4.0/legalcode