Search Results

Documents authored by Fill, James Allen

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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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