Consider a very simple online auction system that works as follows. There are n bidding agents; agent i has a bid bi, which is a positive natural number. We will assume that all bids bi are distinct from one another. The bidding agents appear in an order chosen uniformly at random, each proposes its bid bi in turn, and at all times the system maintains a variable b∗ equal to the highest bid seen so far. (Initially b∗ is set to 0.)
What is the expected number of times that b∗ is updated when this process is executed, as a function of the parameters in the problem?
Example. Suppose b1 = 20, b2 = 25, and b3 = 10, and the bidders arrive in the order 1, 3, 2. Then b∗ is updated for 1 and 2, but not for 3.