7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Just to make sure I understood the question correctly: you ask if the same bound $O(\log |V|)$ holds in the general case, right? $\endgroup$ – fedja Sep 4 '17 at 17:48
  • $\begingroup$ Not necessarily that particular bound, but I would conjecture the slightly looser bound O(log|kn|) where k is the number of leaves and n the depth of the deepest leaf. $\endgroup$ – Michael Jarret Sep 4 '17 at 17:50
  • $\begingroup$ Looks like I'm missing something: take the "star" tree with all other $n$ vertices connected directly to the root and having the same value $k(v)=a$. Then $k(r)=na$, so $a^2(n^2+n)=1$ and the probability to stay at the root is $n^2a^2=\frac n{n+1}$, so you are, most likely, not getting anywhere before time $n$. What am I missing? $\endgroup$ – fedja Sep 4 '17 at 20:30
  • $\begingroup$ Problem is that I screwed up my statement and I'll correct the post in a second. Assume the probability of staying at the root is 0, but the probability of moving to any child of the root is uniformity distributed across children. $\endgroup$ – Michael Jarret Sep 4 '17 at 20:32
  • $\begingroup$ OK. But, then let me ask what is $k_v$. Is it a completely new function having nothing to do with $k_r$? $\endgroup$ – fedja Sep 4 '17 at 20:38
4
$\begingroup$

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)

enter image description here

$\endgroup$
  • $\begingroup$ I don't think that I fully follow this. We're only looking for the probability that we find some leaf, not a particular leaf. Does this still hold in that case? It seems like, in the example you're describing (if I'm actually understanding it) we would find some leaf in expected number of steps log(m) since this is approximately the same problem as the path. It is a few examples like this that motivated the conjecture. $\endgroup$ – Michael Jarret Sep 4 '17 at 23:16
  • $\begingroup$ I can no longer edit my own comment, but there might be a notational issue above. Did you mean m leaves at every m-th vertex or m leaves at ever n-th vertex? If the latter, I should have said that it seems like the result scales like log(n), not log(m). Regardless, I may just not be understanding your argument. Thanks for the help. $\endgroup$ – Michael Jarret Sep 4 '17 at 23:30
  • $\begingroup$ @MichaelJarret I added a graph example to avoid any notation misunderstanding. What else is unclear? $\endgroup$ – fedja Sep 5 '17 at 1:11
  • $\begingroup$ thanks for the graphic, that was very helpful in clarifying your example. I still don't understand why this example would require more than $\sim log(m)$ steps, however. It seems that when one arrives at any bush, one samples a leaf with very high probability. I assume there's something about your adjustment of the probability function, but I didn't quite follow that part. $\endgroup$ – Michael Jarret Sep 5 '17 at 3:00
  • $\begingroup$ Indeed, if you arrive at a bush, then you end up in the leaf with high probability. The whole point is that it is very unlikely to do so because at each step you have at least $m$ vertices on the path to choose from out of which only $2$ are bush roots and the probability to go directly to a leaf of the second bush is negligible. Since you seem to be a visual person like myself, I added the picture of $k_w$ as well. The double translation (picture -> text -> picture) can, indeed, be too much :-) $\endgroup$ – fedja Sep 5 '17 at 13:50

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.