mercredi 1 avril 2020

Optimal Stopping - Probabilistic Analysis 25%

The following problem is an optimal stopping problem, which I've seen before. Secretary problem, odds algorithm, etc. However, it is being presented as a probabilistic problem with a smaller success rate target (25%) then I have seen--usually have heard explanations related to the cumulative odds and working backwards to find the optimal stopping point. https://en.wikipedia.org/wiki/Odds_algorithm

Here's the problem:

Suppose an item is offered for sale, and there are n buyers, each with a distinct bid. Suppose further that the buyers appear in random order, and that the seller knows the number n of buyers. We’d like to design a strategy whereby the seller has a reasonable change of accepting the highest of the n bids. By a strategy, we mean a rule by which the seller decides whether to accept each presented bid, based only on the value of n and the sequence of bids seen so far. For example, the seller could always accept the first bid presented. This results in the seller accepting the highest of the n bids with probability only 1/n, since it requires the highest bid to be the first one presented. Give a strategy under which the seller accepts the highest of the n bids with probability at least 1/4, regardless of the value of n. (For simplicity, you may assume that n is an even number.) Prove that your strategy achieve this probabilistic guarantee.

Anyone have a conceptual way of thinking this probabilistically? I have been trying to think of it from the perspective of percentiles, similar to why picking a random pivot for quicksort (good being within 25th-75th percentile) leads on average almost optimal performance, but no insight/aha moments on my end for this problem.




Aucun commentaire:

Enregistrer un commentaire