[SOLVED] Probability Question
I am having a difficulty on this problem (part a ) and would appreciate if someone can help.
Suppose you’re designing
strategies for selling items on a popular auction Web site. Unlike other
auction sites, this one uses a one-pass auction, in which each bid must be
immediately (and irrevocably) accepted or refused. Specifically,
• First, a seller puts up an item for sale.
• Then buyers appear in sequence.
• When buyer i appears, he or she makes a bid bi > 0.
• The seller must decide immediately whether to accept the bid or not.
If the seller accepts the bid, the item is sold and all future buyers are
turned away. If the seller rejects the bid, buyer i departs and the bid
is withdrawn; and only then does the seller see any future buyers.
Suppose an item is offered for sale, and there are n buyers, each with a
distinct bid. Suppose further that the buyers appear in a 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 chance 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.
(a) 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 are allowed to assume that n is an even number.) Prove
that your strategy achieves this probabilistic guarantee.
