2019/09/12 by Sören Christensen, Christensen, Sören, Simon Fischer +1 · 1 citation
Computer Science · Economics, Econometrics and Finance · Decision Sciences · #Optimization and Search Problems #Stochastic processes and financial applications #Auction Theory and Applications
paper · pdf · doi:10.48550/arxiv.1909.05762
The Chow-Robbins game is a classical still partly unsolved stopping problem introduced by Chow and Robbins in 1965. You repeatedly toss a fair coin. After each toss, you decide if you take the fraction of heads up to now as a payoff, otherwise you continue. As a more general stopping problem this reads V(n,x) = supτE [ (x + Sτ)/(n+τ)] where S is a random walk. We give a tight upper bound for V when S has subgassian increments. We do this by usinf the analogous time continuous problem with a standard Brownian motion as the driving process. From this we derive an easy proof for the existence of optimal stopping times in the discrete case. For the Chow-Robbins game we as well give a tight lower bound and use these to calculate, on the integers, the complete continuation and the stopping set of the problem for n≤ 105.