An optimal algorithm for stopping on the element closest to the center of an interval

DOI10.1016/J.AAM.2021.102281MaRDI QIDQ2665754zbMATH OpenOpenAlexFDO

Authors Małgorzata Kuchta, Małgorzata Sulkowska, Ewa Kubicka, Grzegorz Kubicki

Publication date 19 November 2021

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.12600

zbMATH Keywords

combinatorial optimizationoptimal stoppingsecretary problem

Mathematics Subject Classification ID

Management decision making, including multiple objectives (90B50) Combinatorial probability (60C05) Stopping times; optimal stopping problems; gambling theory (60G40)

Abstract: Real numbers from the interval [0, 1] are randomly selected with uniform distribution. There are $n$ of them and they are revealed one by one. However, we do not know their values but only their relative ranks. We want to stop on recently revealed number maximizing the probability that that number is closest to $frac12$. We design an optimal stopping algorithm achieving our goal and prove that its probability of success is asymptotically equivalent to $frac1sqrtnsqrtfrac2pi$.

Recommendations

• Optimal stopping of a random sequence with unknown distribution
• Optimal rules for the sequential selection of uniform spacings
• Optimal Stopping for I.I.D. Random Variables Based on the Sequential Information of the Location of Relative Records Only
• scientific article; zbMATH DE number 4147350
• scientific article; zbMATH DE number 4036973

Cites work

• scientific article; zbMATH DE number 3734865 (Why is no real title available?)
• A Problem of Optimal Choice and Assignment
• An efficient algorithm for stopping on a sink in a directed graph
• Dynamic Programming and Decision Theory
• Graph-Theoretic Generalization of the Secretary Problem: The Directed Path Case
• On a universal best choice algorithm for partially ordered sets
• Partial-order analogue of the secretary problem: The binary tree case
• Partially ordered secretaries
• Percolation and best-choice problem for powers of paths
• Probabilities of choosing applicants of arbitrary rank in the secretary problem
• The best choice problem for upward directed graphs
• The best-choice problem for partially ordered objects.
• Who solved the secretary problem

Cited in

(2)

• Secretary problem with hidden information; searching for a high merit candidate
• Conditions for quasi-stationarity of the Bayes rule in selection problems with an unknown number of rankable options

This page was built for publication: An optimal algorithm for stopping on the element closest to the center of an interval

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2665754)