Raazesh Sainudiin: Minimum Distance Estimation over Adaptive Histograms from Randomized Priority Queues on Statistical Regular Pavings

We present a consistent histogram estimator driven by a randomized queue prioritised by an appropriate function for a generalized statistically equivalent blocks rule. Such data-dependent adaptive histograms are formalized as statistical regular pavings (SRPs). A regular paving (RP) is a binary tree obtained by selectively bisecting boxes along their first widest side. SRP augments RP by mutably caching the recursively computable sufficient statistics of the data. We formalize the partitioning strategy given by a randomized priority queue as a Markov chain over the space of SRPs. For any priority function, we use the method of minimum distance estimation, proposed by Devroye and Lugosi (2004) to select a minimum distance estimate from the set of adaptive histograms visited by the randomized priority queue. Furthermore, given a collection of priority functions, we can select the best histogram estimate from the respective set of priority queues by first obtaining the minimum distance estimate for each priority function, and then performing minimum distance estimation again over each minimum distance estimate. Finally, we present results for the performance of the SRP histograms selected using minimum distance estimation by an empirical assessment for large sample sizes simulated from several 1D mixtures of the Gaussian and Uniform distribution, and several multivariate distributions that belong to the space of SRP histograms.