I am working on a proof that require the result of the following problem:

Let, $T$ be a rooted directed tree with height $h (\ge \lceil{log_d{n}}\rceil )$ and having $n$ nodes. Each internal node of $T$ has degree (# of children) at most $d$. $T$ was picked uniformly at random from all possible such trees. We define a decent on $T$ as follows. Start with root, for each of its children we decide with probability $p$ whether to decent the subtree rooted by that child. This decisions are made independently for each of the children of root. Then the process continues recursively.

Then, what it is the average number of nodes this procedure will visit?

Is there any known result for this problem for trees with $d$ > 2?

  • $\begingroup$ You visit a node at depth $k$ with probability $p^{k-1}$. Now, all you need is to figure out how many nodes there are at depth $k$. But note that if $p < 1/d$, the average number of nodes visited is constant. $\endgroup$ Jul 27 '14 at 4:04
  • $\begingroup$ I was worried that since nodes shares paths the probabilities may not be the same. Working with indicator variable to might give me the expected # of nodes at depth $k$. Thanks. $\endgroup$
    – Indranil B
    Jul 27 '14 at 17:42
  • $\begingroup$ The expected number of nodes at depth $k$ in a random tree of degree at most $k$ has probably already been computed somewhere; I'd try to look it up rather than duplicate the computations, since I expect it might not be easy. $\endgroup$ Jul 27 '14 at 19:00

Your Answer

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

Browse other questions tagged or ask your own question.