Bound on queries to a tree with unusual probabilties -- follow-up

Question

This question follows up on Bound on queries to a tree with unusual probabilities, where @fedja was able to disprove my conjecture under only constraints (1-4) below. I restate the relevant facts here for simplicity.

Consider a tree $\mathcal{T}(r)=(V,E)$ rooted at $r \in V$ and of maximal depth $n$. Let $\kappa_r:V\rightarrow[0,1]$ be such that

1. $\sum_{v \in V} \kappa_r(v)^2 = 1$,
2. $\kappa_r(r) = 0$,
3. for $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$, and
4. (no longer included)

Let $P(b,v)$ be the shortest path connecting $b$ to $v$ through $\mathcal{T}(r)$ and $L(v)$ be the set of all leaves in the subtree rooted at $v$. We now add the following constraints:

5. For any two leaves $l_0,l_1 \in L(b)$ with most recent ancestor $b \in V$, $\sum_{x \in P(b,l_0)} \kappa_r(x) = \sum_{x \in P(b,l_1)}\kappa_r(x)$

6. (Probably unnecessary) We know $\eta \in \left[\frac{1}{|L(r)|},n\right]$ such that $\eta \sum_{x \in L(r)}\kappa_r(x) = \sum_{x \in P(r,l_0)}\kappa_r(x)$ where $P(r,l_0)$ is the shortest path from $r$ to $l_0$.

We consider an algorithm that seeks to find a leaf of the tree by the following process,

1. sample a random vertex $v$ with probability $\kappa_r(v)^2$
2. let $v$ be a new root and repeat the process on the subtree $\mathcal{T}(v)$ with probabilities assigned by an updated function $\kappa_v$.

Constraints (1-5) apply to any tree/root, so that a new function $\kappa_v$ must also be consistent with them, however it need not be the same function. My conjecture, previously disproven by @fedja, is that under constraints (1-4) one requires something slightly looser than $\log(|V|)$ samples to find a leaf. At least naively, constraint (5) removes the possibility of @fedja's example, since amplitudes appear somewhat inversely proportional to depth. Constraint (6) adds no real mathematical content, but is of algorithmic interest, so I believe that I would like a bound in terms of $\eta$. I can already prove that the algorithm runs in something less than $O\left(|L(r)|\log(n)\right)$ expected steps, but this estimate still seems loose.

Answer 1

If you pose the problem in the most aesthetically pleasing way, it becomes neat and clean and your conjecture holds. Of course, the reality is not obliged to be aesthetically pleasing, but the chance that it complies with aesthetics is generally higher than the chance that it complies with results of students, so the argument below may be of some value.

The setup is that we have a rooted tree oriented away from the root on whose vertices we define the (unique up to a multiplicative constant) positive function $k$ such that

(A) $k(v)=\sum_{c\leftarrow v}k(c)$

(B) The weight $L(v)$ of any path starting at $v$ and going away from the root to some leaf does not depend on the leaf.

Denote by $T(v)$ the subtree rooted at $v$ and put $T'(v)=T(v)\setminus\{v\}$.

If we are at $v$, the next vertex is chosen from $T'(v)$ according to the probability distribution on $T'(v)$ proportional to $k^2$.

Our first task will be to find the normalizing factor for this probability distribution. I claim that $$ K(v)=\sum_{w\in T(v)}k(w)^2=L(v)k(v)\,. $$ Indeed, it is obviously true for leaves $v$ and, assuming that it is true for every child $c$ of $v$, we get $$ K(v)=k(v)^2+\sum_{c\leftarrow v}K(c)=k(v)^2+\sum_{c\leftarrow v}L(c)k(c) \\ =k(v)^2+\sum_{c\leftarrow v}[L(v)-k(v)]k(c)=L(v)k(v)+k(v)\left[k(v)-\sum_{c\leftarrow v}k(c)\right]=L(v)k(v)\,. $$ We used here the immediate consequence of (B) that $L(c)=L(v)-k(v)$ for every child $c$ of $v$.

Thus, the normalizing constant is $Z(v)=K(v)-k(v)^2=[L(v)-k(v)]k(v)=L(c)k(v)$ for every $c\leftarrow v$ and the probability to land in the subtree $T(c)$ equals $$ P(c)=\frac{K(c)}{Z(v)}=\frac{L(c)k(c)}{L(c)k(v)}=\frac{k(c)}{k(v)}\,. $$ Let now $E(v)$ be the expected time until we reach a leaf starting from $v$. If $v$ is not a leaf, we have the recursion $$ E(v)=1+\sum_{w\in T'(v)}\frac{k(w)^2}{Z(v)}E(w)= 1+\sum_{c\leftarrow v}P(c)\sum_{w\in T(c)}\frac{k(w)^2}{K(c)}E(w) \\ =1+\sum_{c\leftarrow v}P(c)\left[\frac{k(c)^2}{K(c)}E(c)+\sum_{w\in T'(c)}\frac{k(w)^2}{K(c)}E(w)\right] \\ =1+\sum_{c\leftarrow v}P(c)\left[\frac{k(c)^2}{K(c)}E(c)+\frac{Z(c)}{K(c)}(E(c)-1)\right] \\ =1+\sum_{c\leftarrow v}P(c)\left[E(c)-1+\frac{k(c)^2}{K(c)}\right] \\ =\sum_{c\leftarrow v}P(c)\left[E(c)+\frac{k(c)^2}{K(c)}\right]= \sum_{c\leftarrow v}\frac{k(c)}{k(v)}\left[E(c)+\frac{k(c)}{L(c)}\right] $$ Now let $LF(v)$ be the set of leaves in $T(v)$. We claim that $$ E(v)\le \sum_{z\in LF(v)}\frac{k(z)}{k(v)}\log_2\frac{L(v)}{k(z)}\,. $$ If $v$ is a leaf, the inequality holds whether we think that $LF(v)=\{v\}$ or that $LF(v)=\varnothing$ (it is the first convention that we'll accept below).

Now, assume that we already have our inequality for all children of $v$. Then, plugging it into the RHS of the recurrence relation for $E(v)$ and taking into account that $\sum_{z\in LF(c)}k(z)=k(c)$ (because of (A)), we get $$ E(v)\le \sum_{c\leftarrow v}\frac{k(c)}{k(v)}\left[\frac{k(c)}{L(c)}+\sum_{z\in LF(c)}\frac{k(z)}{k(c)}\log_2\frac{L(c)}{k(z)}\right] \\ =\sum_{c\leftarrow v}\frac{k(c)}{k(v)}\sum_{z\in LF(c)}\frac{k(z)}{k(c)}\left[\frac{k(c)}{L(c)}+\log_2\frac{L(c)}{k(z)}\right] $$ and it remains to notice that $$ \log_2 L(c)+\frac{k(c)}{L(c)}\le \log_2[L(c)+k(c)]\le\log_2 L(v) $$ (here we used that $k(c)\le L(c)$ and $k(c)\le k(v)$).

Now it remains to note that $$ \sum_{z\in LF(r)}\frac{k(z)}{k(r)}\log_2\frac{L(r)}{k(z)}= \log_2\frac{L(r)}{k(r)}+\sum_{z\in LF(r)}\frac{k(z)}{k(r)}\log_2\frac{k(r)}{k(z)} $$ and that the first term is at most $\log_2D(r)$ where $D(v)$ is the depth of $T(v)$ while the second term is at most $\log_2|LF(r)|$.