Optimal stopping in urn models with payoff depending on maximal observed element
An urn contains N balls, labelled 1,...,N. Optimal stopping rules are considered for payoff functions f(k, m) where f(k, m) is the reward when stopping after k draws, and the largest number seen by then is m. f(k, m) is assumed nondecreasing im for each k. We show: (i) For any horizon n [less-than-or-equals, slant] N, under optimal stopping, sampling without replacement yields a larger expected value than sampling with replacement. (ii) A sufficient condition, both when sampling with or without replacement, for the optimal stopping rule to be of the form t =inf{k:Mk [greater-or-equal, slanted]qk} for some constants qk, where Mk is the maximal label [Delta](k, m) = f(k, m + 1) - f(k, m) be nonincreasing in k for each m. Better sufficient conditions are given, and several e such as reward minus cost of sampling, or discounted rewards, are considered. Some limiting results, as N -->[infinity], and prophet inequality considerations are included for the example where the payoff is reward minus cost of sampling.
Year of publication: |
1993
|
---|---|
Authors: | Samuel-Cahn, Ester |
Published in: |
Statistics & Probability Letters. - Elsevier, ISSN 0167-7152. - Vol. 16.1993, 5, p. 361-368
|
Publisher: |
Elsevier |
Keywords: | Sampling without replacement optimal stopping cost of observation discounting prophet inequality |
Saved in:
Saved in favorites
Similar items by person
-
Beat the Mean: Better the Average
Krieger, Abba M., (2007)
-
Maximizing expected value with two stage stopping rules
Assaf, David, (2004)
-
A generalized secretary problem
Krieger, Abba M., (2014)
- More ...