Short Side Branches

• higher in the tree the number of branches we encounter that are the same depth as the longest one falls rapidly
• I.e. the higher coefficients p' are not only bounded (they are non-negative but sum to 1.0) but the higher order ones vanish.
• In fact in large random binary trees the chance that the other subtree is empty tends to a constant value of approximately 0.5 [Sedgewick and Flajolet, 1996, page 241]

  I.e.  $p'_{0\ldots 0}$ tends to 0.5 as we get further from the leaf,

  i.e. as i increases, so M_i is dominated by the first few terms.

• Hence while $M_i \not=M_1$, $M_{i+1} \approx M_i$ and so the current value along the longest path will become Markovian.
• Therefore the probability distribution of the output of large random trees does not depend upon their size.
• From the eigenvalues and eigenvectors of $M_\infty$ we can calculate the probability distribution of the output of large random trees and how big the threshold size is.

  Note that unlike linear programs, these may depend upon the programs inputs.