# Probability Density Estimation through Nonparametric Adaptive Partitioning and Stitching
## 2 Nonparametric Adaptive Partitioning and Stitching
### Divide and Conquer
It is interesting to observe that \(R\) exhibits a scaling law property as a function of number of units across a variety the distributions we considered. As expected, the uniform density case (SURD) yields  
Figure 1: Visualizing how to calculate \(R\): The \(\Delta^{(s)}\) values are distributed for a subsample after being sorted from lowest to highest values. For illustration purposes, \(n=16\) are the number of data points, there are 15 \(\Delta^{(s)}\) values, and \(w=5\). Note that only \(w\) spacing values on either extreme (minimum spacing on the left side) or (maximum spacing on the right side) are averaged over as the highlights show. The larger differences in small/large spacing implies greater density variation within a block. the lowest \(R(n)\). We find that the scaling law \(R=An^{\alpha}\) provides a good fit to SURD, with \(A=0.01675\) and \(\alpha=1.1\), determined through least squares error linear regression. Notably, the parameters \(A\) and \(\alpha\) are rooted in fundamental statistical properties, which we demonstrate numerically. In other words, \(A\) and \(\alpha\) are not optimized hyperparameters that could depend on our selection of \"training distributions\", while our approach holds universal appeal, it is important to acknowledge that \(w\) serves as a heuristic hyperparameter embedded in the operational definition of \(R\), requiring optimization. We observe that for any fixed value of \(w\) we tested, \(R\) tends to approach a power law form in the limit \(n\gg w\). However, we aim to keep \(w\) small to enable the application of the divide and conquer procedure on small blocks, facilitating better treatment of singular densities. Fitting a scaling law to SURD for different window sizes, \(w\), shows that \(w=10\) provides robust and consistent results for individual realizations. Increasing \(w\) minimizes fluctuations in \(R\) across individual samples, but smaller \(w\) extends the power law to lower sample sizes and keeps computational cost to a minimum. Our heuristic analysis indicates that a value of \(w=10\) is a suitable lower bound. Increasing \(w\) did not result in a significant improvement in accuracy beyond \(w=10\), while smaller values of \(w\) are viable, we select \(w=10\) as it fulfills all necessary requirements, and decreasing \(w\) does not confer computational benefit. To divide a block into two offspring, each containing subsamples of units from the parent block, there are two mechanisms of partitioning. The primary method partitions a block if \(\zeta>An^{\alpha}\) for a given block under consideration, and the splitting process concludes once \(\zeta\leq An^{\alpha}\) is achieved for all blocks. The secondary mechanism is used to further subdivide large blocks containing \(n>n_{0}\) data points, where \(n_{0}\) is determined primarily by hardware constraints. Importantly, all successive divisions of a parent block that satisfies the condition \(\zeta<An^{\alpha}\) will also satisfy this condition for each of the children blocks having  
Figure 2: Sample size dependence on statistical measure \(R\): For the case that \(w=10\), it is seen that a simple power law describes how \(R\) scales as a function of \(n\). These results are based on averaging over 100 realizations per \(n\) value. As expected, the uniform distribution (shown as a dashed black line) provides the lowest bound for \(R\) among all the distributions tested. smaller subsamples. Therefore, when density variation does not cause a block division, the second mechanism will divide the block if it has more units than the predefined maximum, \(n_{0}\). This secondary partitioning rule ensures that a NMEM-worker will not require large memory needs. A practical cutoff of \(n_{0}=\) 100,000 is employed. NAPS achieves load balancing through block partitioning. To determine if the number of samples, \(n\), within a block should be split in half, a \"what-if\" test is developed.