On the Informativeness of Moments in Optimal Stopping
José Correa, Andrés Cristi, Vasilis Livanos, Victor Verdugo, Jiechen Zhang
Abstract
We study a variant of the prophet inequality with limited information, where the decision maker has access only to the first k moments of each random variable, rather than their full distributions. In this work, we show that even with full moment knowledge (i.e., k=∞), the best possible competitive ratio is Θ(1/ logn), and that this can already be achieved with only knowledge of the first moment. While the lower bound is simple and is attained by a standard exponential bucketing algorithm, the upper bound requires a subtle construction. This involves using Vandermonde matrices first to construct a parametrized family of distributions for which the first k moments coincide, and for which the expected maximum of n such copies varies widely across different parameter choices. Using Prokhorov’s theorem, we establish the existence of limit distributions, which we show have all their moments equal. Finally, we describe a construction where an adversary can select equally looking instances combining these distributions, making it impossible for the decision maker to obtain a factor better than O(1/ logn) of the expected maximum.
Ask Lune
Know where this paper stands in minutes, not an afternoon.
Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.
Related papers
- Prophet Inequalities Require Only a Constant Number of SamplesAndrés Cristi, Bruno ZiliottoSTOC 2024 · 6 citations
- Prophet Inequalities: Competing with the Top ℓ Items is EasyMathieu Molina, Nicolas Gast, Patrick Loiseau, Vianney PerchetSODA 2025
- Prophet Inequality from Samples: Is the More the Merrier?Tomer EzraSODA 2026 · 1 citation
- Learning Online Algorithms with Distributional AdviceIlias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian et al.ICML 2021 · 44 citations
- Minimization is Harder in the Prophet WorldVasilis Livanos, Ruta MehtaSODA 2024 · 2 citations
