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:

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

  2. (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.

  • $\begingroup$ Interesting... It looks like the conditions $(1)-(5)$ actually determine $k_r$ uniquely, don't they? Moreover they may become incompatible for certain trees (consider the tree with just two path branches, one of length 2 and another of length 1: L0-V-R-L1. Are you sure that nothing is screwed up now? $\endgroup$
    – fedja
    Sep 6, 2017 at 22:21
  • $\begingroup$ @fedja I should have included $b\neq r$ in the sums of condition (5), which should avoid your mentioned problem. Thanks for pointing this out. $\endgroup$ Sep 6, 2017 at 22:29
  • $\begingroup$ Erm... That completely destroys the phrase "By (5), this is independent of our choice of $l0\in L(r)$." so something is still fishy as written... $\endgroup$
    – fedja
    Sep 6, 2017 at 22:40
  • $\begingroup$ @fedja you are correct as always. I will correct it. $\endgroup$ Sep 6, 2017 at 22:42
  • $\begingroup$ Alas, you still declare equality of all sums for $b=r$ in $(6)$. Are you sure you want to keep $(4)$? The problem gets much neater without it with just $(1,2,3,5)$: the weight is determined uniquely and just conditioned upon the remaining sub-tree every time, and several other features get way more attractive. From purely aesthetic point of view, $(4)$ is a total disaster. Of course, if it holds in the model, nothing can be done about it, but does it? $\endgroup$
    – fedja
    Sep 7, 2017 at 0:36

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.