On the Co-Structure of \(k\) Paths In a Random Binary Tree

Consider the paths \(\pi_t(i_1), \ldots, \pi_t(i_k)\) from the root to the leaves \(i_1, \ldots, i_k\) in a random binary tree \(t\) with \(n\) internal nodes, where all such trees are assumed equally likely and the leaves are enumerated from left to right. We investigate, for fixed \(i_1, \ldots, i_k\) and \(n\), the average size of \(\pi_t(i_1)\cup \ldots \cup \pi_t(i_k)\) resp. of \(\pi_t(i_1)\cap \ldots \cap \pi_t(i_k)\) (the latter corresponding to the average depth of the smallest subtree containing \(i_1, \ldots, i_k\)). By a rotation argument, both problems are reduced to the case \(k=1\), for which a solution is known. Furthermore, formulas for the probability distributions of the depth of leaf \(i\), the distance between leaf \(i\) and \(j\) and the length of \(\pi_t(i) \cap \pi_t(j)\) are derived.