Skip to main content
1 of 3
Johan Wästlund
  • 5.5k
  • 3
  • 28
  • 35

I discussed this problem with Thomas Bruss in 2009 and solved it modulo some numerical details.

A selector wants to pick online the last of an unknown number of items that arrive at independent times uniformly chosen in $[0,1]$. The number $w_n$ is the probability of success (with $n$ items) for the strategy where the selector accepts the $k$:th item if it arrives after time $1-1/(k+1)$.

It turns out that the difference $w_{n+1}-w_n$ is of order $1/n^2$, and to show that the sequence is increasing, it suffices to estimate $w_n$ with an error of order $O(1/n^3)$.

To get an upper bound with this precision, we note that in order for the selector to succeed, there has to be exactly one item arriving in the interval $[1-1/(n+1), 1]$. Moreover, there can be no item arriving in the interval $[1-1/n, 1-1/(n+1)]$, and at most one in the interval $[1-1/(n-1), 1-1/n]$.

The probability that these conditions are met is $$n\cdot \frac1{n+1}\cdot \left[\left(1-\frac1{n-1}\right)^{n-1} + \frac1n\cdot \left(1-\frac1{n-1}\right)^{n-2}\right].$$

Taylor expansion with respect to $1/n$ shows that this is $$\frac1e - \frac1{2e}\cdot\frac1n + \frac7{24e}\cdot\frac1{n^2}+O\left(\frac1{n^3}\right).$$

If the selector's policy fails despite these conditions being fulfilled, it must be because for some $k\geq 3$ there are $k$ items arriving in the interval $[1-1/(n-k+1), 1-1/(n+1)]$. This is way more likely to happen for $k=3$ than for any higher $k$, and we only need a rough upper bound of order $1/n^3$.

To wrap up, we need explicit bounds on the error terms, combined with some numerical results for small values of $n$. I will update the answer with the messy details.

Johan Wästlund
  • 5.5k
  • 3
  • 28
  • 35