# From Trees to Barcodes and Back Again: Theoretical and Statistical Perspectives
## 4 Stability of the TNS
### Bottleneck Stability  
Henceforth, we call the endpoints of the bars of the barcode \(B\)_targets_, as the TNS algorithm either creates a new branch or terminates a branch when the distance from the root approaches a birth or death point, respectively. By definition of the TNS algorithm (cf. Section 2.4), when approaching a target, there is an exponential probability to bifurcate (create a new branch) or terminate, depending on \(\lambda\). It follows that, for any bar \((b_{i},d_{i})\) of a given barcode \(B\), the distance between \(b_{i}\) and \(b^{\prime}_{i}\) (the bifurcation distance and the target bifurcation distance of the \(i\)th branch) and the distance between \(d_{i}\) and \(d^{\prime}_{i}\) (the termination distance and the target termination distance of the \(i\)th branch) should follow an exponential distribution of parameter \(\lambda\),  
\[|b_{i}-b^{\prime}_{i}|\sim\text{Exp}(\lambda)\text{ and }|d_{i}-d^{\prime}_{i}| \sim\text{Exp}(\lambda).\]  
The notion of similarity between barcodes that we consider here is the standard _bottleneck distance_. Given two strict barcodes \(B\) and \(B^{\prime}\) with \(n+1\) bars, the bottleneck distance between them is  
\[d(B,B^{\prime})=\inf_{\gamma\in\mathfrak{S}_{n}}\sup_{i}|b_{i}-b^{\prime}_{ \gamma(i)}|+|d_{i}-d^{\prime}_{\gamma(i)}|.\]  
**Lemma 4**. : _Let \(B\) be a strict barcode with \(n\) bars, and let \(B^{\prime}=\text{TMD}\circ\text{TNS}(B)\). If \(B\sim B^{\prime}\), then_  
\[\mathbb{P}\big{(}d(B,B^{\prime})>\varepsilon\big{)}\leq 1-(1-\exp(-\lambda \varepsilon)(\lambda\varepsilon+1))^{n}. \tag{1}\]Proof. : Considering the case where \(\gamma\) is the identity, we see that  
\[d(B,B^{\prime})\leq\sup_{i}|b_{i}-b^{\prime}_{i}|+|d_{i}-d^{\prime}_{i}|.\]  
If \(B\sim B^{\prime}\), the differences between the new and original values of the births and deaths all follow an exponential distribution,  
\[|b_{i}-b^{\prime}_{i}|\sim\text{Exp}(\lambda)\text{ and }|d_{i}-d^{\prime}_{i}| \sim\text{Exp}(\lambda).\]  
The cumulative probability distribution function of \(|b_{i}-b^{\prime}_{i}|+|d_{i}-d^{\prime}_{i}|\) is thus given by an Erlang\((2,\lambda)\) distribution  
\[\mathbb{P}\big{(}|b_{i}-b^{\prime}_{i}|+|d_{i}-d^{\prime}_{i}|\leq\varepsilon \big{)}=1-(1+\lambda\varepsilon)\exp(-\lambda\varepsilon).\]  
Because we consider the supremum over \(i\) of the sum \(|b_{i}-b^{\prime}_{i}|+|d_{i}-d^{\prime}_{i}|\), and all of the \(|b_{i}-b^{\prime}_{i}|+|d_{i}-d^{\prime}_{i}|\) are _i.i.d_, it follows from the theory of order statistics that  
\[\mathbb{P}\big{(}d(B,B^{\prime})\leq\varepsilon\big{)}\mathbb{P}(\sup_{i}|b_{ i}-b^{\prime}_{i}|+|d_{i}-d^{\prime}_{i}|\leq\varepsilon)=(1-\exp(-\lambda \varepsilon)(\lambda\varepsilon+1))^{n}. \tag{2}\]  
Considering the probability of the complement leads to the result in Equation (1). Lemma 4 implies that the TNS is stable with respect to the bottleneck distance, in a manner dependent on the parameter \(\lambda\). To illustrate this dependence, we plot the function of Equation (1) for different values of \(\lambda\) in Figure 10. The curve obtained for \(\lambda=1\) (blue in Figure 10) makes it clear that setting \(\lambda=1\) ensures that the TNS gives rise to a diverse family of new trees that are nonetheless topologically not significantly far from the original ones, which is the desired goal from a biological perspective. Making an appropriate choice of the parameter \(\lambda\) is thus essential. If \(B\sim B^{\prime}\), the bound by \(\gamma=I\) in the formula for the bottleneck distance is computed between pairs of points that follow the same exponential law, as the order of bars is preserved. If \(B\
eq B^{\prime}\), for example when a switch of bars occurs, then we cannot assume that the distances between matched  
Figure 10: Upper bound on the probability that the bottleneck distance between \(B\) and \(\text{TNS}\circ\text{TMD}(B)\) is larger than \(\varepsilon\) (Equation (1)) for various values of \(\lambda\) and for \(n=10\). pairs of points in the computed bottleneck distance follow the same law.