Metraipolis › archive › dc_33dc3a692bb5
Sample-Based Prophet Inequalities for Random Walks — arXiv:2609.26017
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.26017
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T15:53:21.210Z
- SHA-256 of the archived text
4ce7601bb706b7a5c1f839b1984979451ccfc9da6a12ceb1c8bc5df06fad2704- Stable URL of this page
https://metraipolis.com/documento/dc_33dc3a692bb5
How to cite
Sample-Based Prophet Inequalities for Random Walks — arXiv:2609.26017 — arXiv (en), https://arxiv.org/abs/2609.26017 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_33dc3a692bb5 (Metraipolis archive dc_33dc3a692bb5, sha256 4ce7601bb706b7a5c1f839b1984979451ccfc9da6a12ceb1c8bc5df06fad2704)
BibTeX
@misc{dc33dc3a692bb5,
title = {Sample-Based Prophet Inequalities for Random Walks — arXiv:2609.26017},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.26017},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_33dc3a692bb5; sha256 4ce7601bb706b7a5c1f839b1984979451ccfc9da6a12ceb1c8bc5df06fad2704},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.26017. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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\to\infty$, 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\ge1$ 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\ge 2K^2$, implying convergence to the infinite-horizon constant as $n\to\infty$. 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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-23 in math.OC).
Categorie arXiv: Optimization and Control (math.OC) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.26017 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T15:12:09.740Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-23?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).