# Stochastic Safety Radius on UPGMA
## 1 Introduction
In the application to a phylogenetic tree reconstruction, we use a distance matrix which contains pairwise distances between all pairs of sequences in the input alignment via a user input evolutionary model [1]. A phylogenetic tree is a weighted tree with labeled external nodes, called _leaves_, and unlabeled internal nodes. These labels represent species or taxa at the present time and each internal node represents a common ancestor for all of the leaves below this internal node. A weight on each branch (or edge) of a phylogenetic tree represents a mutation rate combined with its evolutionary time from an ancestor to its descendent. A phylogenic tree can be rooted or unrooted. For more details, see [1]. **Example 1**. : _Suppose we have a label set for leaves \(X=\{1,2,3\}\) which represents a set of species at the present time. Suppose we have a rooted phylogenetic tree \(T\) shown in Figure 1._  
_Internal nodes on \(T\) do not have labels. The internal node of the ancestor of leaves \(1,2\) represents the most common ancestral species of species \(1,2\) and the root of \(T\) is the most common ancestor of all species \(1,2,3\). Each branch length on a branch represents the mutation rate combined with its evolutionary time. A distance matrix computed from this tree shown in Figure 1 is a \(3\times 3\) matrix such that \(d_{ij}\), the \((i,j)\)th cell of the matrix \(d\) is the total branch length from a leaf \(i\in X\) to a leaf \(j\in X\), that is,_  
Figure 1: Example of a phylogenetic tree \(T\) on the label set of leaves \(X=\{1,2,3\}\). \[d= \begin{array}{|c|cccc|}\hline&1&2&3\\ \hline 1&0&e_{1}+e_{2}&e_{1}+w+e_{3}\\ 2&e_{1}+e_{2}&0&e_{2}+w+e_{3}\\ 3&e_{1}+w+e_{3}&e_{2}+w+e_{3}&0\\ \hline\end{array} \]  
_Since \(d\) is computed from a phylogenetic tree, \(d\) is a tree metric. Not all \(n\times n\) symmetric matrices with diagonal elements equal to \(0\) are not tree metrics._  
Through this paper, we assume that _binary phylogenetic trees_ and the smallest branch length \(w_{\min}\) of an internal edge in a binary phylogenetic tree are strictly positive. In this paper, we focus on _equidistant trees_ which are rooted phylogenetic trees with branch lengths such that the total branch length from its root to each leaf is the same. **Example 2**. : _We consider a rooted phylogenetic tree on the label set of leaves \(X=\{1,2,3\}\) shown in Figure 1 with \(w>0\). If \(w+e_{1}=w+e_{2}=e_{3}\), then \(T\) is an equidistant tree._  
In this paper, our main contribution is that we show a lower bound of the probability of UPGMA to return the true equidistant tree on the set of leaves \(X=\{1,2,\ldots,n\}\) for \(n\geq 3\) from a set of random pairwise distances of all possible pairs of sequences. Then we conduct some computational experiments using a statistical software R to see how tight this lower bound is in practice for \(n=4,\ldots,10\). This paper is organized as follows: Section 2 reminds the reader of the basics of tree metrics and random variables representing pairwise distances of all possible pairs of sequences. Then it adds a notion of stochastic safety radius defined by [PERSON] in [2]. In Section 3, we compute the stochastic safety radius of the _three point condition_ for equidistant trees using a lower bound of the probability of returning the tree topology based on the three point condition. Then in Section 4, we compute a lower bound of the the probability of returning the tree topology from UPGMA and in Section 5, we show some results from our computational experiments with R. In Section 6, we end this paper with some discussion.