The online monotone array completion problem

Vishesh Jain, Dylan King, Clayton Mizgerd

Consider the following online filling game. An array of length $n$ is initially empty. At each time step one observes an independent sample from $\mathrm{Unif}[0,1]$ and must eithe…