The hotel problem
You are driving down a one-way road and pass a strip of a large number, N, of hotels. These all have different rates, arranged randomly. You want to maximize your chance of choosing the cheapest hotel, but you can’t return to one you’ve passed up. Assume that your only goal is to obtain the cheapest one (the second cheapest is of no more value to you than the most expensive). If your strategy is to proceed past a certain fraction, x, of them and then pick the next one that is cheaper than all the ones you’ve seen so far, what should x be? What, then, is the probability of success? Assume that N is very large, and ignore terms in your answer that are of sub - leading order in N.