The secretary problem for a random walk
type: Item
instance of: scholarly article
title: The secretary problem for a random walk
zbMATH Open document ID: 0647.60051
DOI: 10.1016/0304-4149(88)90104-4
author: J. N. Sheahan
author: M. Hlynka
published in: Stochastic Processes and their Applications
publication date: 1988-01-01T00:00:00Z
review text: The problem of picking the maximum of a sequence of n numbers was first considered by \textit{J. P. Gilbert} and \textit{F. Mosteller} [J. Am. Stat. Assoc. 61, 35-73 (1966)]. Since then, other work has appeared to extend their results, but all extensions to date have retained the assumption that the n numbers are observations on a sequence of independent random variables. This paper considers the problem of finding the maximum on a generalized one-dimensional random walk. The process considered is \(\{Y_ i\}_{i\geq 0}\), such that \(Y_ i=Y_{i-1}+X_ i\), where the \(X_ i's\) are i.i.d. continuous or discrete random variables, symmetric with respect to 0. Like in the usual secretary problem, the process must stop after n observations, and there is no recall. The objective is to maximize the probability of selecting the best (highest) of the n observations. The authors consider a class of stopping rules \(S_ 0,S_ 1,..\). such that \(S_ 0\equiv 0\), and \(S_ k\) is of the form ``let the first k-1 observations go by, and afterwards stop at the first observation which is better than all previous observations''. The main result of the paper states that the \(S_ k's\) are all optimal. Also, in the case of the ordinary random walk, where \(P(X_ i=1)=P(X_ i=-1)=0.5\), the probability of making the best selection if \(n=2m\) is large is approximately equal to 1/\(\sqrt{\pi m}\).
Mathematics Subject Classification ID: 60G40
Mathematics Subject Classification ID: 60G50
zbMATH DE Number: 4056694
zbMATH Keywords: picking the maximum of a sequence
zbMATH Keywords: secretary problem
zbMATH Keywords: stopping rules
reviewed by: J. Gianini Pettitt
MaRDI profile type: Publication
full work available at URL: 0304-4149(88)90104-4
OpenAlex ID: W1987722503
cites work: Q4114551
cites work: Q5538132
cites work: Q5512461
cites work: The Secretary Problem and Its Extensions: A Review
cites work: A Best-Choice Problem With Linear Travel Cost
cites work: A Generalized Problem of Optimal Selection and Assignment
description: scientific article; zbMATH DE number 4056694