Tree measures
Q: Consider a random finite rooted binary tree. Any given leaf can be reached by a unique shortest sequence of steps from the root. Suppose we pick a leaf uniformly at random, but then take only the first k of these steps from the root. We might reach the leaf we first thought of (maybe in fewer than k steps), or we might reach a node that's a parent of that leaf. Define:
- the uniqueness probability = the probability that we reach the leaf we first thought of;
- the resolution = the reciprocal of the expected number of leaves that are children of the node we reach.
How do these values vary with k, for a large tree? Do the functions approach each other for large k? Do we need to be more specific about what a "random" tree is?
This puzzle was inspired by a discussion of the resolution of my TORUS tune-indexing system, which includes graphs of these functions for the system's database tree.