# From Trees to Barcodes and Back Again: Theoretical and Statistical Perspectives
## 4 Stability of the TNS
### Transposition Stability  
As the TNS algorithm is a stochastic process, the image of any strict barcode \(B=\{(b_{i},d_{i}\})\) under the composite \(\mathrm{TMD}\circ\mathrm{TNS}\) essentially always differs at least slightly from \(B\). Here, we determine the probability that the orders of the death times of two specific bars of \(B\) and \(\mathrm{TMD}\circ\mathrm{TNS}(B)=B^{\prime}=\{(b^{\prime}_{i},d^{\prime}_{i})\}\) are different, so that \(B\) and \(\mathrm{TMD}\circ\mathrm{TNS}(B)\) are not combinatorially equivalent, i.e., the associated permutations are different, as long as the birth times are not also transposed (Figure 13). Figure 12: **(A1–A3)** Bottleneck distance as a function of \(\lambda\). We compute the bottleneck distance between an input barcode \(B\) and an output barcode \(B^{\prime}\) for \(\lambda=0.01-2\). **(A1)** From barcode \(B\) (in black), a tree (in red) is generated using the TNS which results in a new barcode \(B^{\prime}=\mathrm{TMD}\circ\mathrm{TNS}(B)\) (in red). **(A2)** The average bottleneck distance (red points) is compared to the expected mean of the probability distribution function found in Lemma 4 (blue curve). **(A3)** The bottleneck distances (red) are compared to the cumulative distribution probability for \(0<\epsilon<200\) and \(0<\lambda<2\) (blue). **(B1–B2)** Bottleneck distance between \(B\) and \(B^{\prime}\) as a function of distances between bars in \(B\). **(B1)** We consider barcodes of the same permutation type for different distances between two bars \((b_{i},d_{i})\) and \((b_{j},d_{j})\) of the initial barcode \(B\) that are consecutive in the order of deaths. **(B2)** For each input barcode with increasing \(d_{i}\), the distance between death times presented in \(x\)-axis, 100 synthesized barcodes are generated and the bottleneck distance between the input and output barcodes is computed (\(y\)-axis), which depends only on the value of \(\lambda\) and not on the distance between the bars. **Lemma 5**. : _Let \(B\) be a strict barcode, and let \((b_{i},d_{i}),(b_{j},d_{j})\) be bars of \(B\) such that \(d_{i}<d_{j}\). Let \((b^{\prime}_{i},d^{\prime}_{i})\) and \((b^{\prime}_{j},d^{\prime}_{j})\) denote the corresponding bars in \(B^{\prime}=\mathrm{TMD}\circ\mathrm{TNS}(B)\). The probability that \(d^{\prime}_{j}<d^{\prime}_{i}\) is_  
\[\mathbb{P}(d^{\prime}_{j}<d^{\prime}_{i})=\frac{1}{2}\exp(-\lambda(d_{j}-d_{i} )).\]  
The TNS thus exhibits a sort of \"transposition stability\": the probability that the death times of two bars will be transposed decreases exponentially with the distance between those death times. Proof. : We compute \(\mathbb{P}(d^{\prime}_{j}<d^{\prime}_{i})=\mathbb{P}(d^{\prime}_{j}<d^{\prime} _{i}\left|d_{i}<d_{j}\right. )\), the probability that \(d^{\prime}_{j}<d^{\prime}_{i}\) given that \(d_{i}<d_{j}\). Observe first that  
\[\mathbb{P}(d^{\prime}_{j}<d^{\prime}_{i})=\mathbb{P}(d_{j}+(d_{i} -d^{\prime}_{i})<d_{i} +(d_{j}-d^{\prime}_{j}))\\ =\mathbb{P}(d_{j}+X_{i}<d_{i}+X_{j})=\mathbb{P}(X_{j}-X_{i}>d_{j }-d_{i}).\]  
Let \(Y=X_{j}-X_{i}\). As \(X_{j}\) and \(X_{i}\) both follow an exponential law, the density function of their difference, \(Y\), is given by \(f_{Y}(t)=\frac{\lambda}{2}\exp(-\lambda t)\) when \(t\geq 0\). Therefore,  
\[\mathbb{P}(d^{\prime}_{j}<d^{\prime}_{i})=\mathbb{P}(X_{j}-X_{i}>d_{j}-d_{i}) =\int_{d_{j}-d_{i}}^{\infty}f_{Y}(t)dt=\frac{1}{2}\exp(-\lambda(d_{j}-d_{i})).\]  
**Remark 1**. : _Since the TNS is based on a stochastic process, multiple transpositions can occur when generating a new tree from a barcode. This makes it challenging to determine the overall probability of changing equivalence classes when computing the composite \(\mathrm{TMD}\circ\mathrm{TNS}\). Note that the TNS might also affect the birth order, but we will not discuss this possible effect in this paper.