Simple mathematical models are almost always too simple to model complex phenomena in the real world, and the one I want to discuss in this post is not an exception. However, I believe it is a good first order approximation.

Let me begin with the model first and then talk about its potential real life applications. Suppose you have an unknown probability distribution over the unit interval , and you draw i.i.d. samples . Each draw costs a fixed amount , and your goal is to maximize the expectation of by choosing the best . The solution depends on the unknown distribution of course.

Model Assumptions

Let us talk about the use case of this model. You may want to buy a consumer product from the market, and you'd like to do some inspection before buying one. This is especially relevant for technological gadgets. Inspecting each item costs you time/effort, and you need to stop at some point and buy the best item you inspected so far.

Let's think about the fitness between model assumptions and real life. The model assumes there is no learning during the sampling process. You choose the next item randomly. This may be somewhat violated in real life. One way to increase the model faithfulness is to use a dynamic distribution that shifts to the higher values as one samples. This may cause the optimum to be lower than the case where a fixed distribution is used. The other model assumption is that the items will stay available and you don't fear some of them getting out-of-stock before you complete your exploration. This sounds reasonable for many cases. The inspection cost is assumed to be constant, which is a nice assumption since all items are goods of the same kind. And maybe the most unrealistic assumption is that you can judge an item's value exactly after the inspection process. An item's value is the utility it provides throughout its lifetime minus its price, and predicting the first term of this subtraction is not easy. A more faithful model may use variable inspection cost and noisy draws, where the variance of noise decreases with increasing cost.

One could do a quick informed guess for the lower and upper bounds for the value of the worst and best valued items in the market, respectively. Then the unnormalized cost of inspection can be guessed by thinking about how much money one is willing to give someone to do the inspection job for him, provided that the person does this job perfectly. The cost is then the normalized value, where the utility scale is shifted and scaled so that the lower and upper bounds are 0 and 1, respectively.

Solutions for some distributions

Let be the cdf of . It is well-known that the cdf of is . Thus, we have . Using integration by parts we get .

So the should be chosen to maximize . Since range is , we have for some with positive measure and all and for almost all reasonable cdf , so the integral monotonically decreases with , which means there is a unique extremum of , which is a maximizer. Let us forget about the fact that is an integer and treat the problem as continous optimization. Afterall the maximizer will be one of the two closest integer to that solution. Taking the derivative with respect to , we get that must hold if is the (continous) maximizer value.

The worst-case upper bound for

Now we are looking for a cdf which maximizes in the last equation, the market distribution that leads to the maximum exploration.

Notice that the integrand (and the value of the integral) decreases with increasing . Thus, we should choose that maximizes the integrand, so that decreasing it to the same constant takes a larger value.

Let represents the integrand where . A simple calculus shows that attains its maximum value at . This means the cdf must be the constant value , everywhere except the edges. Plugging the maximum value of the integrand into the equation we get .

This means , and almost everywhere. This is a discrete distribution with two types of items: good and bad, where of all items are bad.

Power distributions

For the family of , the integral equation becomes , which can be easily solved to yield .

Uniform distribution is the special case where , which yields . Compare this to the optimum we got for the worst-case distribution. The dependence on is square-rooted.

Conclusion

So the next time you want to buy something, try to estimate the difference between the maximum and minimum valued items in the market (discard the garbage ones that won't even require any inspection), divide that value to the cost of inspecting one item, and further divide it to the magic number . And never surpass that limit. For example if , you should never inspect more than 4 items.

Keep in mind that this is a worst-case bound, and it is probably very loose. It might be that for most of the reasonable distributions , the optimum is inversely proportional to the square root of the cost .