Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation

Shyam Narayanan, Václav Rozhoň, Jakub Tětek +1

Suppose we have a memory storing $0$s and $1$s and we want to estimate the frequency of $1$s by sampling. We want to do this I/O-efficiently, exploiting that each read gives a bloc…