Consider a tree $\mathcal{T}(r) = (V,E)$ rooted at $r \in V$. Let $\kappa_r: V \longrightarrow [0,1]$ such that $\sum_{v \in V} \kappa_r(v)^2 = 1$. Furthermore, for any given vertex $v \neq r$, $\kappa_r(v) = \sum_{c\leftarrow v}\kappa_r(c)$ where $c\leftarrow v$ means that $c$ is a child of $v$. Also, assume that $\kappa_r(r)=0$ and that $\kappa_r(c) = \kappa_r(c')$ for $c,c' \leftarrow r$. We want to determine a bound on the expected number of queries required to traverse from $r$ to some leaf $l$ as follows:

- Sample a random vertex $v$ with probability $\kappa_r(v)^2$
- Update the root to the outcome of (1), and repeat the procedure on the subtree $\mathcal{T}(v)$, with probabilities assigned by the updated function $\kappa_{v}$.

In the event that the walk is on a path, this clearly scales like $\log(|V|)$ since the probability of sampling anywhere is distributed uniformly. (This is trivial to prove by simply solving the recurrence that results from the probabilities in terms of expected change in depth.) In the event that the tree has more than one leaf, however, the problem IS a bit of a challenge. (Maybe not for someone on here, I hope.) The probabilities become top-heavy due to the square amplitude probabilities, but I'd still anticipate the worst case scaling to occur when a tree with $k$ leaves has $O(\log(k))$ branch points on the path to each leaf or, in other words, when the tree has as many branch points as possible.

I have some ideas on how to prove this, but nothing has worked out yet. Thoughts were:

- Create a new statistic that scales like what I anticipate the expected number of steps to scale like
- Attempt to prove that for any distribution of vertices, the problem with evenly distributed branch points becomes harder (using some set of moves)
- Try to explicitly use something like a Jensen inequality. This works out for star-type (sub)trees, but I still get stuck once I go back an ancestor or so.

Any thoughts, references, suggestions appreciated.

UPDATE: Because of the answer below, I have followed up with a more nuanced question Bound on queries to a tree with unusual probabilties -- follow-up.

1more comment