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 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.