# Probability Density Estimation through Nonparametric Adaptive Partitioning and Stitching
## 2 Nonparametric Adaptive Partitioning and Stitching
### Test Distributions
```
1:Input subsample \(s\leftarrow\{x_{m_{1}},\ldots,x_{m_{n}}\}\)
2:Sample indices for subsample \(M\subseteq\{1,\ldots,N\}\)
3:\(M=\{m_{1},\ldots,m_{n-1}\}\)
4:subsample size \(n=|M|\)
5:Look up sample differences
6:\(\Delta=\{\Delta_{k}=x_{m_{k+1}}-x_{m_{k}}\;\forall\;k\in\{1,N-1\}\}\)
7:Sorted subsample differences
8:\(\Delta^{M}\leftarrow\{\Delta_{k}\;\forall\;k\;\in\;i\}\)
9:\(i\leftarrow\) Map subsample indices in set M to indices in set \(\Delta\)
10:\(\Delta_{min}\gets mean\{\Delta_{1}^{M},\ldots,\Delta_{w}^{M}\}\)
11:\(\Delta_{max}\gets mean\{\Delta_{m_{n-1}-w}^{M},\ldots,\Delta_{m_{n-1}}^{M}\}\)
12:\(R\leftarrow\frac{\Delta_{min}}{\Delta_{max}}\)
13:Return \(\xi_{01}\leftarrow\frac{\left(R_{0}+R_{1}\right)}{2}\)
```  
**Algorithm 1**\(\xi\) algorithm ```
1:Input Sorted Sample
2:\(X\leftarrow\{x_{1},\dots,x_{k}\}\ \forall\ k\in\{1,\dots,N\}\)
3:Compute threshold
4:\(\Gamma\gets A\cdot N^{\alpha}\)
5:\(N=|X|\)
6:Compute \(\xi\) for \(X\)
7:\(\xi_{00}\leftarrow\ \xi(X)\)
8: First index is the tree level
9: Second index is the branch number on the tree level
10:Get max tree level \(l_{max}\)
11:Initialize partitions \(p\leftarrow\{1,N\}\)
12:Initialize branch number \(b\gets 1\)
13:if\(\xi_{00}>\Gamma\)then
14:for\(i\in\{1,\dots,l_{max}\}\)do
15:for\(j\in\{1,\dots,b\}\)do
16:\(\xi_{ij}\leftarrow(R_{0}+R_{1})/2\)
17:if\(\xi_{ij}>\Gamma\)then
18: Update \(p\leftarrow\{p,p_{new}\}\)
19:endif
20:endfor
21:if\(\xi_{ij}<\Gamma\ \forall\ j\in\{1,\dots,b\}\)then
22: Break loop
23:endif
24: Update \(b\leftarrow|p|-1\)
25:endfor
26:endif
27:Return \(p\)
```

**Algorithm 2** Optimized branching tree algorithm ```
1:Sort Input Sample
2:\(X\leftarrow\{x_{1},\dots,x_{k}\}\ \forall\ k\in\{1,\dots,N\}\)
3:Compute differences
4:\(\Delta\leftarrow\{\Delta_{k}=x_{k+1}-x_{k}\}\ \forall\ k\in\{1,N-1\}\)
5:Get optimal partitions
6:\(p\gets OBT(X)\)
7:Define second layer of blocks
8:\(p^{\prime}\leftarrow\{\lfloor\frac{p_{i+1}-p_{i}}{2}\rfloor\}\ \forall\ i\in\{1,\dots,p-1\}\)
9:Define block samples for both layers
10:\(B^{(1)}\leftarrow\{B^{(1)}_{i}=\{x_{i},\cdots,x_{i+1}\}\ \forall\ i\in p\}\)
11:\(B^{(2)}\leftarrow\{B^{(2)}_{i}=\{x_{i},\cdots,x_{i+1}\}\ \forall\ i\in p^{\prime}\}\)
12:Define ordered block samples
13:\(B\leftarrow\{B^{(1)}_{1},B^{(2)}_{1},\cdots,B^{(2)}_{|p^{\prime}|-1},B^{(1)} _{|p|-1}\}\)
14:Number of blocks \(\leftarrow|B|=(2|p|-3)\)
15:Define block boundary conditions \(\rightarrow\gamma\)
16:Define NMEM settings \(\rightarrow\omega\)
17:\(\textbf{{parfor}}\ j\in\{1,\cdots,N_{blocks}\}\)
18: Get density estimates per block
19:\((\hat{f}_{j},\hat{f}_{j})\gets NMEM(B_{j},\gamma_{j},\omega)\)
20:end
21:\(\textbf{{for}}\ j\in\{1,\cdots,N_{blocks}-1\}\)do
22: Compute weight averaged densities for block overlap regions
23:\(\hat{f}^{(s)}_{j}\leftarrow\frac{(1-u_{1})^{2}\hat{f}_{j}+(u_{2})^{2}\hat{f}_ {j+1}}{(1-u_{1})^{2}+(u_{2})^{2}}\)
24:endfor
25:Return switched densities for all blocks
26:\(\hat{f}=\hat{f}_{1}\cup\hat{f}^{(s)}_{1}\cup\hat{f}_{2}\cup\cdots\cup\hat{f} _{N_{blocks}-2}\cup\hat{f}^{(s)}_{N_{blocks}-1}\cup\hat{f}_{N_{blocks}-1}\)
```  
**Algorithm 3** Stitching method algorithm