On path entropy functions for rooted trees

✍ Scribed by A. Meir; J.W. Moon

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 323 KB
• Volume: 138
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(94)00214-4

✦ Synopsis

Ifu is a terminal node of a rooted tree T. with n terminal nodes, let h(u) = ~f (d(v)) where the sum is over all interior nodes v in the path from the root of T. to u, d(v) is the out-degree of v, and 1" is a non-negative cost function. The path entropy function h(T.) = ~h(u), where the sum is over the n terminal nodes of T., is a measure of the complexity of the hierarchical classification scheme represented by T.. We show, under suitable assumptions, that the expected value of h(T.) over all trees 7". in certain families of weighted trees is asymptotic to Kn 3/2 where the constant K depends on the family and the cost function f * The preparation of this paper was assisted by grants from the Natural Sciences and Engineering Research Council of Canada. * Corresponding author.