The length of a random leaf coloration on a random tree.
Mike Steel, Angèle M. Hamel · UC Research Repository (University of Canterbury) · 1997
An assignment of colors to objects induces a natural integer weight on each tree that has these objects as leaves. This weight is called "parsimony length" in biostatistics and is the basis of the "maximum parsimony" technique for reconstructing evolutionary trees. Equations for the average value (over all binary trees) of the parsimony length of both xed and random colorations are derived using generating function techniques. This leads to asymptotic results that extend earlier results con ned to just two colors. A potential application to DNA sequence analysis is outlined briefly.