# Probability Density Estimation through Nonparametric Adaptive Partitioning and Stitching
## 2 Nonparametric Adaptive Partitioning and Stitching
### NAPS Algorithm  
The divide and conquer process using data-driven decisions based on the density variation characteristic, \(\xi\), to create a binary tree structure is called the optimal branching tree (OBT). Here, the pseudo code of NAPS is provided with implementation details, broken down into three algorithms, the first is to calculate \(\xi\).  
Algorithm 1 splits a sample \(S\) in half, yielding samples \(S_{0}\) and \(S_{1}\) for the left and right sides. For each half, the statistical measure for density variation is calculated as \(R_{0}\) and \(R_{1}\). This means that the differences, \(\Delta\), are computed for \(S_{0}\) and sorted, and then again for \(S_{1}\) and sorted. For each set, \(\Delta_{min}\) and \(\Delta_{max}\) are calculated as the mean over the first and last \(w\) points of the sorted sets. In this way, \(R_{0}\) and \(R_{1}\) are calculated so that \(\xi\) is returned.  
Figure 5: Stitching process: (**a**) To facilitate a stitch, the estimated complementary CDF based on \(u_{1}\) and the estimated CDF based on \(u_{2}\) used in Equation (5) are shown as red and blue curves, respectively. **(b)** The resulting stitched density (black) as an interpolation between the left and right density estimates of a pair of blocks show as red and blue curves, respectively. This example is atypical as it shows the weighting from the left and right sides both range from 0 to 1. Typically the maximum values for the CDF and complimentary CDF are less than 1 over the mutually shared region of interest.  
Algorithm 2 initializes the sample size dependent threshold and partition set \(p\) for the sample or subsample \(S\), with set size \(|S|=n\). The maximum number of levels allowed in the unbalanced binary tree is set to 40 for completeness, albeit not obtainable. The initial \(\xi_{00}\) is computed, and \(b\), the number of branches, is initialized to 1. The indexing on \(\xi_{ij}\) is based on tree level. If \(\xi_{ij}<\Gamma\), the starting partition set is returned unchanged; otherwise, the block is partitioned into equal halves. The outer loop iterates over the number of levels in the tree, while the inner loop iterates through all branches currently under evaluation per tree level. The average of ratios for the left and right newly generated subsamples is stored in \(\xi_{ij}\) and evaluated against \(\Gamma\). If \(\xi_{ij}>\Gamma\), the new partition is accepted; otherwise, the partition is rejected. After evaluating all branches for a given level, they are checked against \(\Gamma\). If \(\xi_{ij}<\Gamma\)\(\forall\)\(i\in 1,\ldots,m\) and \(j\in 1,\ldots,b\), the subroutine stops making any further levels of the tree and returns the set \(p\). Otherwise, the algorithm updates the number of branches to evaluate and recursively continues.  
The mathematical components of the stitching algorithm were described above. Algorithm 3 provides a pseudo code for the stitching process, and the complete NAPS algorithm is defined by the combination of Algorithms 1-3. Once all blocks are stitched together, there is one final step: normalizing the proposed PDF to 1. Additionally, different methods for estimating the PDF within a block, such as KDE, can be plugged into NAPS.