The Asymptotic Distribution of the k-Robinson-Foulds Dissimilarity Measure on Labeled Trees

Motivated by applications in medical bioinformatics, Khayatian et al. (2024) introduced a family of metrics on Cayley trees [the k-Robinson-Foulds (RF) distance, for $k\hspace{0.17em}=\hspace{0.17em}0,$ . . . $,n-2$] and explored their distribution on pairs of random Cayley trees via simulations. In this article, we investigate this distribution mathematically and derive exact asymptotic descriptions of the distribution of the k-RF metric for the extreme values $k\hspace{0.17em}=\hspace{0.17em}0$ and $k\hspace{0.17em}=\hspace{0.17em}n-2$, as n becomes large. We show that a linear transform of the 0-RF metric converges to a Poisson distribution (with mean 2), whereas a similar transform for the ($n-2$)-RF metric leads to a normal distribution (with mean $\sim \hspace{0.17em}n{e}^{-2}$). These results (together with the case $k\hspace{0.17em}=\hspace{0.17em}1$ which behaves quite differently and $k\hspace{0.17em}=\hspace{0.17em}n-3$) shed light on the earlier simulation results and the predictions made concerning them.