‎Path length and Sackin index of random $m$-oriented recursive trees‎

Articles in Press

Document Type : Original paper

Authors

Department of Statistics, Imam Khomeini International University, Qazvin, Iran

Abstract

‎The main purpose of this article is to study of two distance-based quantities‎, ‎internal path length and Sackin index‎, ‎in random $m$-oriented recursive trees‎. ‎Unlike the traditional method‎, ‎the mean and variance of the internal path length are  directl} calculated through a simple recurrence‎. ‎The complexity of the calculations is due to the dependence of the probability of attracting a new node on the outdegree of the node‎. ‎We show that there exists a random variable $I$ such that $\frac{I_n‎ -‎\frac nm \log n}{mn}\to I$ almost surely and in $L^2$‎, ‎as $n\to\infty$‎. ‎Then‎, ‎under two assumptions‎, ‎some results related to the Sackin index of these tree models are given‎. ‎Specifically‎, ‎based on Chebychev’s inequality‎, ‎we show that‎ ‎$\frac{(m+1)S_n}{n\log n}\to 1$‎ ‎in probability‎.

Keywords

Main Subjects

References

1] T.M. Coronado, A. Mir, F. Rossello, and L. Rotger, On Sackin’s original proposal: the variance of the leaves’ depths as a phylogenetic balance index, BMC Bioinformatics 21 (2020), no. 1, 154. https://doi.org/10.1186/s12859-020-3405-1
[2] R.P. Dobrow and R.T. Smythe, Poisson approximations for functionals of random trees, Random Structures and Algorithms 9 (1996), no. 1-2, 79–92.
[3] P. Hall and C.C. Heyde, Martingale Limit Theory and its Application, Academic Press, New York, 1980.
[4] M. Javanian and M.Q. Vahidi-Asl, External path length of random $m$-oriented recursive trees, J. Natural Sci. Math. 50 (2010), no. 1-2, 11–18.
[5] R. Kazemi, On the multiplicative Zagreb indices of bucket recursive trees, Iranian J. Math. Chem. 8 (2017), no. 1, 37–45.
https://doi.org/10.22052/ijmc.2017.15385
[6] R. Kazemi, Total path length and Sackin index of random recursive trees, 14th Iranian Statistics Conference, 2018, pp. 420–425.
[7] R. Kazemi and A. Behtoei, The moments of the Sackin index of random d-ary increasing trees, Mathematicki Vesnik 73 (2021), no. 1, 55–62.
[8] M.C. King and N.A. Rosenberg, A simple derivation of the mean of the Sackin index of tree balance under the uniform model on rooted binary labeled trees, Math. Biosci. 342 (2021), 108688. https://doi.org/10.1016/j.mbs.2021.108688
[9] H.M. Mahmoud, Distances in random plane-oriented recursive trees, J. Comput. Appl. Math. 41 (1992), no. 1-2, 237–245. https://doi.org/10.1016/0377-0427(92)90252-S
[10] A. Mir, F. Rossello, and L. Rotger, A new balance index for phylogenetic trees, Math. Biosci. 241 (2013), no. 1, 125–136.
https://doi.org/10.1016/j.mbs.2012.10.005
[11] B. Pittel, Note on the heights of random recursive trees and random m-ary search trees, Random Structures and Algorithms 5 (1994), no. 2, 337–347. https://doi.org/10.1002/rsa.3240050207
[12] M.J. Sackin, Good and bad phenograms, Systematic Biology 21 (1972), no. 2, 225–226. https://doi.org/10.1093/sysbio/21.2.225
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 08 September 2026

Files

Share

How to cite

Statistics