Resampling-free bootstrap inference for quantiles

Bootstrap inference is a powerful tool for obtaining robust inference for quantiles and difference-in-quantiles estimators. The computationally intensive nature of bootstrap inference has made it infeasible in large-scale experiments. In this paper, the theoretical properties of the Poisson bootstrap algorithm and quantile estimators are used to derive alternative resampling-free algorithms for Poisson bootstrap inference that reduce the the computational complexity substantially without additional assumptions. The results unlock bootstrap inference for almost arbitrarily large samples. At Spotify, we can now easily calculate bootstrap confidence intervals for quantiles and difference-in-quantiles in A/B tests with hundreds of millions of observations.