IBM Ponder This #091 · November 2005

Puzzle for November 2005.

This month's puzzle concerns random binary trees. Let p be a fixed parameter between 0 and 1. Starting with the complete infinite binary tree retain each edge randomly and independently with probability p. Our random binary tree is the portion connected to the root. So for example the binary tree consisting of the root alone will be selected with probability (1-p)**2 (ie when neither edge out of the root is retained).

Some of these random binary trees will contain an infinite number of vertices. Throw these out. Then we ask what is the expected number of vertices as a function of p of a random binary tree selected in this way. This is a problem for which it is possible to obtain the right answer in a non-rigorous way. We will not attempt to check the derivation of submitted solutions but you should think about what would be required to prove your answer rigorously.

Hints to the puzzle added on November 17**th 2005:
A lot of wrong answers so perhaps a hint is in order. It may be helpful to compute the fraction of random binary trees which are infinite and therefore thrown out. And remember you are computing the expected size over the remaining trees after throwing out the infinite trees (or to put it another way the expected size given that the tree is finite).

---

The first 100 people who answer correctly will be listed. The answer will be posted a week after the 100th is received, or at the end of the month.

Solution

Best opened after a real attempt

To be added.