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

- $\sum_{v \in V} \kappa_r(v)^2 = 1$,
- $\kappa_r(r) = 0$,
- 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
- (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:

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)$

(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,

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

2more comments