Estimating monotone densities by cellular binary trees
We propose a novel, simple density estimation algorithm for bounded monotone densities with compact support under a cellular restriction. We show that its expected error (L_1 distance) converges at a rate of n^-1/3, that its expected runtime is sublinear and, in doing so, find a connection to the theory of Galton–Watson processes.
READ FULL TEXT