Search Results

Documents authored by Fill, James Allen

Document
DOI: 10.4230/LIPIcs.AofA.2026.21
A New Fine-Scale Berry-Esseen-Type Gumbel-Limit Theorem for Multivariate Maxima

Authors: James Allen Fill

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract
For d ≥ 2 and i.i.d. d-dimensional observations 𝐗^(1), 𝐗^(2), … with independent Exponential(1) coordinates, let φ_n denote the minimum 𝓁¹-norm among the maxima of {𝐗^(1), …, 𝐗^(n)}. (A maximum from this set is an observation 𝐗^(k) with 1 ≤ k ≤ n such that 𝐗^(k) ⊀ 𝐗^(i) for all 1 ≤ i ≤ n, where 𝐱 ≺ 𝐲 means that x_j < y_j for 1 ≤ j ≤ d.) Key roles in the study of multivariate Pareto records are played by φ_n and by the more easily handled maximum with the maximum 𝓁¹-norm. Fill et al. proved [Fill et al., 2026, Theorem 1.11(a)] that φ_n = ln n - ln ln ln n - ln(d - 1) + O_p(1/ln ln n), where Z_n = O_p(a_n) means that Z_n / a_n is bounded in probability, and conjectured [Fill et al., 2026, Remarks 1.13 and 3.3] that (ln ln n) (φ_n - [ln n - ln ln ln n - ln(d - 1)]) has a nondegenerate limiting distribution, suggesting that the limiting distribution might be that of - G, where G has a Gumbel distribution with location - ln[(d - 1)!]/(d - 1) and scale 1/(d - 1). In the present extended abstract we outline a proof of a Berry-Esseen-type theorem for this convergence in distribution, thereby establishing a very sharp result for φ_n.
Cite as

James Allen Fill. A New Fine-Scale Berry-Esseen-Type Gumbel-Limit Theorem for Multivariate Maxima. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 21:1-21:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fill:LIPIcs.AofA.2026.21,
  author =	{Fill, James Allen},
  title =	{{A New Fine-Scale Berry-Esseen-Type Gumbel-Limit Theorem for Multivariate Maxima}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{21:1--21:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.21},
  URN =		{urn:nbn:de:0030-drops-262924},
  doi =		{10.4230/LIPIcs.AofA.2026.21},
  annote =	{Keywords: Multivariate maxima, Gumbel distributions, Berry-Esseen-type theorem, Poisson approximation, Chen-Stein method, multivariate Pareto records}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.28
Sharpened Localization of the Trailing Point of the Pareto Record Frontier

Authors: James Allen Fill, Daniel Q. Naiman, and Ao Sun

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
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.
Cite as

James Allen Fill, Daniel Q. Naiman, and Ao Sun. Sharpened Localization of the Trailing Point of the Pareto Record Frontier. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 28:1-28:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fill_et_al:LIPIcs.AofA.2024.28,
  author =	{Fill, James Allen and Naiman, Daniel Q. and Sun, Ao},
  title =	{{Sharpened Localization of the Trailing Point of the Pareto Record Frontier}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{28:1--28:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.28},
  URN =		{urn:nbn:de:0030-drops-204631},
  doi =		{10.4230/LIPIcs.AofA.2024.28},
  annote =	{Keywords: 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}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.AofA.2018
LIPIcs, Volume 110, AofA'18, Complete Volume

Authors: James Allen Fill and Mark Daniel Ward

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
LIPIcs, Volume 110, AofA'18, Complete Volume
Cite as

29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Proceedings{fill_et_al:LIPIcs.AofA.2018,
  title =	{{LIPIcs, Volume 110, AofA'18, Complete Volume}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018},
  URN =		{urn:nbn:de:0030-drops-92453},
  doi =		{10.4230/LIPIcs.AofA.2018},
  annote =	{Keywords: Mathematics of computing, Theory of computation, Computing methodologies, Philosophical/theoretical foundations of artificial intelligence}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.AofA.2018.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: James Allen Fill and Mark Daniel Ward

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 0:i-0:xi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fill_et_al:LIPIcs.AofA.2018.0,
  author =	{Fill, James Allen and Ward, Mark Daniel},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{0:i--0:xi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.0},
  URN =		{urn:nbn:de:0030-drops-88930},
  doi =		{10.4230/LIPIcs.AofA.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.21
On the Tails of the Limiting QuickSort Density

Authors: James Allen Fill and Wei-Chun Hung

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
We give upper and lower asymptotic bounds for the left tail and for the right tail of the continuous limiting QuickSort density f that are nearly matching in each tail. The bounds strengthen results from a paper of Svante Janson (2015) concerning the corresponding distribution function F. Furthermore, we obtain similar upper bounds on absolute values of derivatives of f of each order.
Cite as

James Allen Fill and Wei-Chun Hung. On the Tails of the Limiting QuickSort Density. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 21:1-21:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fill_et_al:LIPIcs.AofA.2018.21,
  author =	{Fill, James Allen and Hung, Wei-Chun},
  title =	{{On the Tails of the Limiting QuickSort Density}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{21:1--21:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.21},
  URN =		{urn:nbn:de:0030-drops-89144},
  doi =		{10.4230/LIPIcs.AofA.2018.21},
  annote =	{Keywords: Quicksort, density tails, asymptotic bounds, Landau-Kolmogorov inequality}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact