# Probability Density Estimation through Nonparametric Adaptive Partitioning and Stitching
## 2 Nonparametric Adaptive Partitioning and Stitching
### Divide and Conquer  
We implement a data-driven divide and conquer approach by applying the binary division rule to a block as:  
\[\text{if }(\ n>n_{0}\ \text{ or }\ \xi>An^{\alpha}\ )\text{: \ divide the block in half \ else: terminate its division} \tag{1}\]  
where \(n\) is the number of units in a block, \(n_{0}\) is the maximum size block allowed, \(\xi\) is a test statistic that quantifies density variation within a block, and \(A\) and \(\alpha\) are parameters determined by considering the scaling of a statistical measure \(R\) applied to SURD. Furthermore, the \(\xi\) test statistic is given by \(\xi=(R_{0}+R_{1})/2\) where the statistical measures \(R_{0}\) and \(R_{1}\) will be defined momentarily, after the general \(R\) statistic is defined. From an initial sorting operation of the input data representing \(N\) units, the \(n\) units in a block are sort ordered such that \(x_{k+1}\geq x_{k}\) for all \(k\). The next step evaluates the differences between all adjacent pairs of data points, denoted by \(\Delta=\{\Delta_{k}=x_{k+1}-x_{k}\;\forall\;k\in\{1,\ldots,n-1\}\}\), where \(n\) represents the block size or the total number of input units. The set of differences is sorted and denoted by \(\Delta^{(s)}=\{\Delta_{i}\;|\;\Delta_{i+1}>\Delta_{i}\;\forall\;i\in\Delta\}\). To quantify the variation in density within a block of interest, which contains \(n\) units (note that \(n\leq N\)), we use the statistical measure \(R\). We define \(R\) for a block as an average over the smallest and largest values of \(\Delta^{(s)}\) over a window size of \(w\). The window size is a hyper-parameter that will be heuristically optimized. The calculation of \(R\) involves straightforward operations starting from Equations (2) and (3) and arriving at Equation (4). \[\Delta_{min} =\frac{1}{w}\sum_{k=1}^{w}\Delta_{k}^{(s)} \tag{2}\] \[\Delta_{max} =\frac{1}{w}\sum_{k=n-w}^{n-1}\Delta_{k}^{(s)}\] (3) \[R =\frac{\Delta_{max}}{\Delta_{min}} \tag{4}\]  
Figure 1 gives an illustration of how the averaging procedure for \(\Delta_{min}\) and \(\Delta_{max}\) is performed over a window size of \(w\) for a subsample of \(n\) data points, and having \(n-1\) sorted spacing values from smallest to largest. Note that in cases where \(2w>n-1\) the two regions shown in Figure 1 will overlap. As the overlap increases this will drive \(R\to 1\). As such, the value of \(w\) actually sets the minimum size block for which \(R\) can be greater than 1 regardless of the way \(\Delta^{(s)}\) is distributed. Specifically, for all block sizes with \(n\leq w+1\), it follows \(R=1\), and this lower limit property will be useful to develop a stop condition in subdividing blocks, as explained below. Based on the operational definition for \(R\) (detailed in Equations (2)-(4), we note that \(1\leq R<\infty\). As the density variation within a block increases, \(R\) can only increase from 1, and a divergent density is indicated when \(R\rightarrow\infty\). Furthermore, after consecutive sampled points are sorted in ascending order, the fluctuations that occur in their spacing causes \(R\) to increase away from 1 as the number of units increases. This latter trend will be true for any given statistical distribution, but we are specifically interested in discriminating density variations within a region that is typical of uniform density or slowly varying density (i.e., near uniform density), versus a region having large density variations. To quantify the distinction between low and high density variation requires developing a sample size dependent threshold. To establish a baseline for the threshold as a function of \(n\), we apply the general statistical measure \(R\) to a uniform distribution, since random data cannot be expected to be more uniformly distributed than SURD. To quantify the trend of how \(R\) increases as the number of units increases, we plot \(\log(R)\) as a function of \(\log(n)\) in Figure 2 for the case \(w=10\).