0
$\begingroup$

Suppose we have $N$ root nodes that can branch into $N$ new nodes every level. There is a maximum of 64 levels. However, on any given step, each node has a chance $P$ of terminating. What is the expected value of $S$, the total number of nodes in the tree?

Is the answer simply

$$S = \sum\limits_{n=0}^{63}(1-P)^n *N^n $$

or something like that? This is similar to other questions on here such as Expected number of leaf nodes resulting from branching process or expected value tree structure.

$\endgroup$
0
$\begingroup$

Each level should be expected to contain $C[N(1-P)]$ nodes, where $C$ is the number of nodes on the previous level. This is because every $C$ that survives, which is $C(1-P)$ on average, multiplies to $N$ more nodes. Thus the expected total, $S$ is indeed

$$S = N\sum\limits_{n=0}^{63} \left[N(1-P)\right]^n$$

| cite | improve this answer | |
$\endgroup$

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.