Prophet inequality improves stopping decisions from sample random walks
Sample-Based Prophet Inequalities for Random Walks
Data Structures and Algorithms
Summary
This paper studies how to make the best decision about when to stop watching a random process that changes in steps, without knowing the process’s details beforehand. The main goal is to stop near the highest point that the process will reach. The authors develop mathematical guarantees on how close the stopping rule’s expected reward is to the true maximum, based on how many sample paths of the process are available. Their results connect classic probability tools with new techniques to give exact performance limits depending on the number of samples.
What this means in practice
- •For financial traders: Design algorithms to decide the best time to sell assets based on past price path samples to approach maximum expected returns.
- •For network engineers: Improve packet scheduling by estimating optimal stopping points in signal quality modeled as sample-based random walks to enhance data transmission.
A theory result. No direct application yet.
Authors
Pieter Kleer, Johan van Leeuwaarden, Daan Noordenbos
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\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.