Optimal Stopping for the Uniform Distribution

Alexander Gnedin · 2026

Read Optimal Stopping for the Uniform Distribution by Alexander Gnedin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-04371.txt.

Introduction

Alexander Gnedin solves a clean gambling problem in a 2026 arXiv paper: numbers arrive one at a time, drawn independently from a discrete uniform distribution. a player who must stop once, with no recall, wants the best final result. When the number of draws and the size of the range grow together, the discrete problem is known to have a tractable limit form built on a planar Poisson process.

Working in that limit, Gnedin finds the solution for the uniform case and identifies the optimal stopping rule. Through a change of time variable, the rule matches a known asymptotic solution to Lindley's classic problem of minimizing the expected rank of the chosen value. The result ties two old stopping problems together and gives the uniform problem the same kind of complete answer its continuous cousins enjoy.

Catalog record

CREATORAlexander Gnedin
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-04371

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Optimal Stopping for the Uniform Distribution Alexander Gnedin Abstract Many discrete-time optimal stopping problems are known to have more tractable limit forms based on a planar Poisson process. Using this tool we find a solution to the optimal stopping problem for i.i.d. sequence of n n discrete uniform random variables, in the asymptotic regime where n n and the range of distribution are of the same order. The optimal stopping rule in the Poisson problem is identified, by means of a time change, with known asymptotic solution to Lindley’s problem of minimising the expected rank. 1 Introduction The following problem introduced by Moser [ 24 ] belongs to classics of the discrete-time optimal stopping. A number is drawn at random from the uniform distribution on [0,1] . We may either keep the number, or reject it and draw again. We can then either keep the second number drawn or reject it, and draw again, and so on until being willing to accept the last observed number. Suppose we have at most n opportunities of which exactly one must be used to eventually accept a number. Let V_{n} be the smallest possible expected value of the accepted draw. What is V_{n} and what is a stopping rule that achieves this value? Contrary to the established tradition we formulated the problem as a minimisation task, to cast the principal large- n asymptotics in the most transparent way as \lim_{n\to\infty}nV_{n}=2, (1) and to facilitate linking with the scaling limits in the sequel. Extensions of Moser’s problem to sampling from other continuous distributions (possibly changing from trial to trial) have been widely studied, see [ 19 ] for recent developments and bibliography. The related vast area of prophet inequalities is focused on comparison of the optimal stopping value with expectation of the most favourable draw value that would be accessible under a complete foresight of random sequence [ 18 ] . Historically, the first problem of optimal stopping was proposed by Cayley [ 6 ] for sampling without replacement from an urn of lottery tickets, and solved explicitly by backward induction for payoffs \{1,2,3,4\} and n=1,2,3,4 draws. Ferguson in his textbook [ 9 ] regards Moser’s problem as approximation to Cayley’s model for sampling from \{1,2,\ldots,N\} when N is large. However, if both N and n are large the approximation can only be justified when N is of the order higher than n , to ensure that each particular value appears among n draws with negligible probability. If N and n are of comparable magnitude one should be careful to distinguish between sampling with and without replacement. Sampling without replacement is always more favourable [ 3 ] but gives rise to a much more complex stopping problem apparently unsolved up to date (for n<N of the same order). In this paper we first revise Moser’s problem with the accent on its limit form based on the planar Poisson process, adding some insights to the existing literature [ 12 , 20 , 29 ] . Then we move into the unexplored territory to consider the optimal stopping for sampling with replacement from the discrete uniform distribution as n/N\to T,0<T<\infty . This asymptotic regime is known as the central domain of parameters in the classic balls-in-boxes allocation scheme [ 21 ] . We find the limit stopping value function and the optimal strategy, in particular show that for n=N the constant analogous to ( 1 ) is about 2.513 . Finally we find out, quite unexpectedly, that the optimal strategy transforms, via a simple time change, into known asymptotic solution to Lindley’s problem of minimising the expected rank [ 7 , 9 , 22 , 26 ] . The analytical aspects of the exact solution and two-sided bounds enrich the bunch of examples of stopping boundaries for Poisson processes found in [ 29 ] . Though we introduce all necessary tools, skipping some routine details will be inevitable to keep the exposition concise. See [ 28 ] for the general background on point processes and extreme values, and [ 9 , 27 ] for basics of the optimal stopping theory. 2 Moser’s problem and its limit form 2.1 Moser’s problem in a nutshell Suppose the successive draw values are independent random variables U_{1},U_{2},\ldots with [0,1] -uniform distribution. We define the stopping value for the problem with (at most) n trials as the ‘minimal expected loss’ V_{n}:=\inf_{\sigma\leq n}{\mathbb{E}}\,U_{\sigma}, (2) where the infinum is taken over all stopping times \sigma adapted to the sequence and taking values in \{1,\ldots,n\} . In this generality, at each step the observer may use the information contained in all draws available so far. By the independence assumption, however, in the event that stopping has not occurred before step j<n , only U_{j} and the number of remaining trials n-j do matter for deciding between accepting the j th draw hence terminating, or continuing with the next draw. The optimality principle dictates to resolve the stopping-continuation dilemma at each step by comparing the immediate loss of stopping with the best expected outcome by continuation (given the observed data). For the problem ( 2 ) this implies the Wald-Bellman optimality equation V_{n}={\mathbb{E}}\min(U_{1},V_{n-1}) , which can be re-arranged as V_{n}-V_{n-1}=-{\mathbb{E}}\,(V_{n-1}-U_{1})_{+} and upon integration becomes V_{n}-V_{n-1}=-\frac{1}{2}\,V_{n-1}^{2},~~~~ (3) with the initial value V_{0}:=\infty . Relative to the temporal succession of draws, the difference equation ( 3 ) is a backward recursion for the continuation value V_{n} , which assesses the best outcome for an online decision maker when n steps remain to go. Accordingly, the optimal stopping time is of the threshold form \sigma_{n}:=\min\{1\leq j\leq n:U_{j}\leq V_{n-j}\}. (4) It is a peculiar feature of the uniform distribution that the same number V_{n-j} carries the twofold role of a critical threshold for draw U_{j} to be accepted and the optimal continuation outcome when n-j trials are still available. The limit ( 1 ) follows from the more informative bounds on the stopping value, which ajusted to the minimisation problem ( 2 ) are \frac{2}{n+H_{n}+2}\leq V_{n}<\frac{2}{n+H_{n}+1}, where H_{n}:=\sum_{k=1}^{n}1/k is the harmonic number. See [ 9 , 24 ] for this and a more precise asymptotic approximation. The stopping value can be compared with the best possible value of a prophet n\,{\mathbb{E}}\min(U_{1},\ldots,U_{n})=1. The following asymptotic moments of the optimal stopping time were obtained in [ 8 , 23 ] by involved combinatorial calculations based on ( 4 ): \frac{1}{n}\,{\mathbb{E}}\,\sigma_{n}\to\frac{1}{3},~~~\frac{1}{n^{2}}\,{\rm Var}(\sigma_{n})\to\frac{1}{18}~~~~~({\rm as}~~n\to\infty). (5) Matching the moments with ( 5 ), one might expect that the distribution of \sigma_{n}/n is close to beta (1,2) -distribution on [0,1] . Confirming the guess and deriving the limit law for the accepted draw U_{\sigma_{n}} are most naturally done in the continuous-time scenario to follow. 2.2 The planar Poisson framework The adjustment of Moser’s problem to sampling from the uniform distribution on [0,T] or any other interval is obvious. Nevertheless introducing a scaling parameter will be beneficial to reveal a trade-off between the range of draws and horizon of the stopping problem. The random scatter of points on the plane \left\{\big((T/n)j,\,(n/T)U_{j}\big),~j\in{\mathbb{N}}\right\} (6) for large n can be approximated by a Poisson point process \Pi with unit rate in the positive quadrant {\mathbb{R}}_{+}^{2} . Simply put, the number of points ( 6 ) falling in a bounded

Read the complete text