{"id":"arxiv/2609.26017","url":"https://arxiv.org/abs/2609.26017","tags":["math.OC","cs.DS"],"score":0,"title":"Sample-Based Prophet Inequalities for Random Walks","domain":"math.OC","source":"arxiv","authors":["Pieter Kleer","Johan van Leeuwaarden","Daan Noordenbos"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-22","reactions":{}}