# Stochastic Safety Radius on UPGMA
## 5 Computational Experiments  
In this computational experiment, we use the ape [17] and the phangorn packages [18; 19]. R packages for phylogenetic tree data structures, generating random trees, and UPGMA. First, in order to compare Theorem 10 and the space of ultrametrics, namely Theorem 5 computationally with \(n=3\) so that we can visualize the results. We generated 1000 random points \(\delta=(\delta_{12},\delta_{13},\delta_{23})\) where \(\delta_{ij}=d_{ij}+\epsilon\) for \(i,j,k\in\{1,2,3\}\) and \(\epsilon\sim N(0,\sigma)\). We vary \(\sigma=0.01,0.1,0.5,1.0\). The results show in Figure 5. Black points are ultrametrics \(d=(d_{12},d_{13},d_{23})\) and red points are \(\delta=(\delta_{12},\delta_{13},\delta_{23})\). Figure 4: Two cases for equidistant trees without labels. We estimate the probability for UPGMA to return the true tree topology using Algorithm 2 for \(n=4,\ldots,10\) and for \(\sigma=0.1,0.5,1,2,5\), and then we compare these estimated probabilities with lower bounds which we obtained in Theorem 10. These results are shown in Tables 1 and 2. These results show that lower bounds computed in Theorem 10 might not be tight. In all cases, the lower bound computed by Theorem 10 is an order of magnitude less than the estimated probability for UPGMA to return the true tree topology with a random sample. This suggests that although the presence of a lower bound defines a boundary for the likelihood of the having the true tree topology, it also presents a challenge in the magnitude of gap. \begin{table}
\begin{tabular}{c c c c c} \hline \(\sigma\)/ \(n\) & 4 & 5 & 6 & 7 \\ \hline
0.1 & 0.902 (0.334) & 0.802 (0.447) & 0.682 (0.381) & 0.545 (0.260) \\
0.5 & 0.650 (0.160) & 0.420 (0.055) & 0.246 (0.035) & 0.144 (0.014) \\
1 & 0.446 (0.060) & 0.214 (0.006) & 0.093 (0.001) & 0.049 (<0.0001) \\
2 & 0.261 (0.015) & 0.080 (0.001) & 0.027 (<0.0001) & 0.007 (<0.0001) \\
5 & 0.129 (0.004) & 0.031 (<0.0001) & 0.007 (<0.0001) & 0.001 (<0.0001) \\ \hline \(\sigma\)/ \(n\) & 8 & 9 & 10 & \\ \hline
0.1 & 0.477 (0.226) & 0.357 (0.137) & 0.320 (0.118) & \\
0.5 & 0.084 (0.001) & 0.046 (<0.0001) & 0.019 (<0.0001) & \\
1 & 0.021 (<0.0001) & 0.009 (<0.0001) & 0.003 (<0.0001) & \\
2 & 0.002 (<0.0001) & 0.001 (<0.0001) & \textless{0.001 (<0.0001)} & \\
5 & \textless{0.001 (<0.0001)} & \textless{0.001 (<0.0001)} & \textless{0.001 (<0.0001)} & \\ \hline \end{tabular}
\end{table} 
Table 1: Comparison between empirical probabilities with lower bounds computed by Theorem 10. The notation \(a(b)\) in each cell represents two parts: \(a\) represents the estimated probability for UPGMA to return the true tree topology with a random sample of sample size 1000 and \((b)\) represents a lower bound computed by Theorem 10. We repeated this process 100 time and take an average for computing estimated probabilities. For example, we consider the cell for \(\sigma=0.1\) and \(n=4\). In this cell, 0.902 is an estimated probability computed by Algorithm 2 and 0.334 is a lower bound from Theorem 10 with \(n=4\) and \(\sigma=0.1\). Figure 5: Red points are randomly generated \(\delta=(\delta_{12},\delta_{13},\delta_{23})\) and black points are ultrametrics which are equivalent to equidistant trees. The top left figure is for \(\sigma=0.01\). The top right figure is for \(\sigma=0.1\). The bottom left figure is for \(\sigma=0.5\). The bottom right figure is for \(\sigma=1\). ```
Input: The number of leaves \(n\), standard deviation \(\sigma>0\). Output: Estimated probability for UPGMA to return the true tree topology. for\(i=0,\ldots,100\),do  Generate a random tree \(T\) with \(n\) leaves \(X=\{1,\ldots,n\}\) using a multispecies coalescent model [4] via the function coal from the ape package. Set \(p_{i}=0\). for\(k=0,\ldots,1000\),do  Generate a random distance matrix with \[\delta_{ij}=d_{ij}+\epsilon_{ij},\] where \(d_{ij}\) is the total branch length from a leaf \(i\) to a leaf \(j\) in \(T\) and \(\epsilon_{ij}\sim N(0,\sigma)\) for all \(i,j\in X\).