2024/11/11 by Zakaria Derbazi, Derbazi, Zakaria
Computer Science · #15B48 #60G40 #60J10 #Distributed systems and fault tolerance #FOS: Mathematics #Optimization and Search Problems #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2411.07103
openalex publication_date 2024/11/11 · openalex created_date 2024/11/15 · openalex updated_date 2026/07/28
Consider a discrete-time optimal selection problem where one observes a sequence of independent Bernoulli trials and receives a nonnegative reward upon stopping on a success. The aim is to find a single-choice strategy that maximises the expected payoff. These Bernoulli stopping problems are characterised by two key properties: (i) a recurrence relation connecting the reward sequence to the continuation payoff sequence, and (ii) the total positivity of the Markov chain embedded in success epochs of the trials. The recurrence is fundamental in proving the optimality of the myopic strategy under unimodal continuation payoff sequence, while the total positivity ensures that the expectation of a quasi-unimodal function of the chain remains quasi-unimodal with respect to the initial state. In particular, if the number of successes is finite almost surely, the quasi-unimodality of the reward sequence is sufficient for the myopic rule to be optimal. Illustrative examples are given in various last-success settings.