Sample-Based Prophet Inequalities for Random Walks
Abstract
We study prophet inequalities for a random walk reward stopping problem with sample-based information. The goal is to stop as close as possible to the maximum of a random walk with i.i.d. increments, measuring performance by the ratio between the expected reward when stopping and the expected true maximum. We consider a sample-based model in which the increment distribution is unknown and the decision maker has access to K independent sample paths of the reward process. For the infinite-horizon setting, we establish a sharp prophet inequality with constant (K/(K+1))K+1. The guarantee is attained by a randomised stopping rule based on the ladder height decomposition of random walks. As K→∞, this recovers the classical 1/e prophet inequality from the full-information setting. For the finite-horizon setting, where the process terminates after n steps, we first prove a tight no-information prophet inequality with constant 1/Hn, where Hn is the n-th harmonic number. For K≥1 samples, we show that a prophet constant of 1/4 is attainable. Finally, we prove that, with K samples, the prophet constant is at most (K/(K+1))K+1+(6+6HK)/Hn for n≥ 2K2, implying convergence to the infinite-horizon constant as n→∞. Our approach combines random walk theory, including ladder heights and Spitzer's identity, with linear programming duality. Our results contribute to random walk stopping theory and to sample-based prophet inequalities for correlated rewards, an area that remains largely unexplored. To the best of our knowledge, our tight sample-based prophet inequalities are the first whose performance is parameterised exactly, rather than only up to constants, by the number of available samples.
Related
BibTeX
@misc{kleer2026samplebased,
title = {{Sample-Based Prophet Inequalities for Random Walks}},
author = {Pieter Kleer and Johan van Leeuwaarden and Daan Noordenbos},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.26017},
eprint = {2609.26017},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.26017},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sample-Based Prophet Inequalities for Random Walks
AU - Pieter Kleer
AU - Johan van Leeuwaarden
AU - Daan Noordenbos
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2609.26017
UR - https://arxiv.org/abs/2609.26017
AB - We study prophet inequalities for a random walk reward stopping problem with sample-based information. The goal is to stop as close as possible to the maximum of a random walk with i.i.d. increments, measuring performance by the ratio between the expected reward when stopping and the expected true maximum. We consider a sample-based model in which the increment distribution is unknown and the decision maker has access to K independent sample paths of the reward process. For the infinite-horizon setting, we establish a sharp prophet inequality with constant (K/(K+1))^K+1. The guarantee is attained by a randomised stopping rule based on the ladder height decomposition of random walks. As K→∞, this recovers the classical 1/e prophet inequality from the full-information setting. For the finite-horizon setting, where the process terminates after n steps, we first prove a tight no-information prophet inequality with constant 1/H_n, where H_n is the n-th harmonic number. For K≥1 samples, we show that a prophet constant of 1/4 is attainable. Finally, we prove that, with K samples, the prophet constant is at most (K/(K+1))^K+1+(6+6H_K)/H_n for n≥ 2K^2, implying convergence to the infinite-horizon constant as n→∞. Our approach combines random walk theory, including ladder heights and Spitzer's identity, with linear programming duality. Our results contribute to random walk stopping theory and to sample-based prophet inequalities for correlated rewards, an area that remains largely unexplored. To the best of our knowledge, our tight sample-based prophet inequalities are the first whose performance is parameterised exactly, rather than only up to constants, by the number of available samples.
ER -