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.

This page is maintained by Thomas Bending,
and was last modified on Thu 28 July 2022.

Comments, criticisms and suggestions are welcome.
Copyright © Thomas Bending
2022