<p>I am working on a proof that require the result of the following problem:</p>

<p>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. </p>

<p>Then, what it is the average number of nodes this procedure will visit?</p>

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

CC BY-SA 3.0
2014-07-27T04:04:38.527Z
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.
Peter Shor 
CC BY-SA 3.0
2014-07-27T17:42:16.917Z
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.
Indranil B
CC BY-SA 3.0
2014-07-27T19:00:57.763Z
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.
Peter Shor 
<ds.data-structures><tree>
On a property of random rooted trees with $n$ nodes and of height $h$
Indranil B
# On a property of random rooted trees with $n$ nodes and of height $h$

(Asked by: username_0 on 2014-07-27)

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?

**Tags:** ds.data-structures, tree

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  

---

## 0 answers

