On the Informativeness of Moments in Optimal Stopping

We study a variant of the prophet inequality with limited information, where the decision maker has access only to the first 𝑘 moments of each random variable, rather than their full distributions. In this work, we show that even with full moment knowledge (i.e., 𝑘 = ∞), the best possible competitive ratio is Θ(1/log 𝑛), 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 𝑘 moments coincide, and for which the expected maximum of 𝑛 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/log 𝑛) of the expected maximum. Our result implies that to obtain improved prophet inequalities, further assumptions beyond moment knowledge are needed. To showcase this direction, we establish improved bounds under additional distributional assumptions such as MHR and bounded coefficient of variation.