Bound on queries to a tree with unusual probabilities

Question

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:

1. Sample a random vertex $v$ with probability $\kappa_r(v)^2$
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:

1. Create a new statistic that scales like what I anticipate the expected number of steps to scale like
2. Attempt to prove that for any distribution of vertices, the problem with evenly distributed branch points becomes harder (using some set of moves)
3. 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.

Answer 1

Alas, under the conditions you imposed, your conjecture is way too optimistic. Consider a path of length $mn$ and plant a bush with $m$ leaves at every $m$-th vertex on that path (so $|V|=2nm$). Now, if $w$ is not in a bush, we can define $k_w$ proportional to $1$ on the path until we meet the second bush after $w$ (the leaves of the first bush are assigned the value $0$), then, at the second bush we split $k$ equally between leaves, so we get $m$ leaves with $k\sim \frac{1}{m}$ and assign $0$ to the rest of the path. The result is that during each step we have only at most $2/m$ chance to land in a bush and we never move beyond the second bush. So, if $n\le m/4$, the probability to just move along the path without landing in any bush and covering not more than $2m$ vertices each time during the first $n$ steps is at least $1/2$. However, in such regime, we cannot finish in fewer than $n/2$ steps. Thus, the best upper bound you can hope for in general is something like $\sqrt{|V|}$.

Graph for $m=6,n=4$:

The function $k_w$ (not normalized, the root $w$ is shown in green)