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

DOI10.1016/J.AAM.2021.102281zbMATH Open1481.60084arXiv1904.12600OpenAlexW3210192100MaRDI QIDQ2665754FDOQ2665754

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)

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$.

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

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

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)

Cites Work

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

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)