Section 21.2

How Many to Buy?

Choosing in advance how many draws, bidders or helpers to pay for, trading cost against the expected maximum or the chance of success.

Toolkit

These problems fix a quantity in advance (number of trials, draws, or bidders) by comparing the expected marginal benefit of one more unit against its known cost, stopping at the point where gains stop exceeding cost.

If each additional independent trial succeeds with probability $p$ (or raises overall success probability), and the success probability after $n$ trials is $S(n)$ , buy the $(n+1)$ th unit iff

S(n+1)-S(n) > c,

where $c$ is the marginal cost; optimal $n^*$ is the largest $n$ with marginal gain still exceeding $c$ .

For i.i.d. $U_1,\dots,U_n\sim\mathrm{Unif}(0,1)$ ,

\mathbb{E}[\max(U_1,\dots,U_n)] = \frac{n}{n+1},

with marginal gain from the $n$ th to $(n+1)$ th draw

\frac{n+1}{n+2}-\frac{n}{n+1} = \frac{1}{(n+1)(n+2)},

a decreasing sequence; buy draws while this exceeds the per-draw fee.

General principle: since marginal gains are decreasing (concavity), the greedy stopping rule (stop at first unprofitable increment) gives the global optimum.

Problems