English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Suppose a customer is faced with a sequence of fluctuating prices, such asfor airfare or a product sold by a large online retailer. Given distributionalinformation about what price they might face each day, how should they choosewhen to purchase in order to maximize the likelihood of getting the best pricein retrospect? This is related to the classical secretary problem, but withvalues drawn from known distributions. In their pioneering work, Gilbert andMosteller [\textit{J. Amer. Statist. Assoc. 1966}] showed that when the valuesare drawn i.i.d., there is a thresholding algorithm that selects the best valuewith probability approximately $0.5801$. However, the more general problem withnon-identical distributions has remained unsolved.  In this paper we provide an algorithm for the case of non-identicaldistributions that selects the maximum element with probability $1/e$, and weshow that this is tight. We further show that if the observations arrive in arandom order, this barrier of $1/e$ can be broken using a static thresholdalgorithm, and we show that our success probability is the best possible forany single-threshold algorithm under random observation order. Moreover, weprove that one can achieve a strictly better success probability using moregeneral multi-threshold algorithms, unlike the non-random-order case. Along theway, we show that the best achievable success probability for the random-ordercase matches that of the i.i.d.\ case, which is approximately $0.5801$, under a"no-superstars" condition that no single distribution is very likely ex ante togenerate the maximum value. We also extend our results to the problem ofselecting one of the $k$ best values.

Prophets, Secretaries, and Maximizing the Probability of Choosing the Best