### Thread: Expected number of degree 1 nodes in minimal prefix tree is n*lg(e/2) ...

1. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2007
Posts
51
Rep Power
10

#### Expected number of degree 1 nodes in minimal prefix tree is n*lg(e/2) ...

While working on minimal prefix trees (minimal distinguishing) constructed on n completely random bit sequences, there appeared a few looking fundamental, but quite nontrivial relations and I couldn't find them in literature, like:

- we know that they have n-1 degree 2 nodes, but the expected number of degree 1 nodes also grows linearly: n*lg(e/2) ~ 0.442695n
- the average depth of leaves is larger than lg(n) for perfect binary tree by about 1/2+gamma*lg(e) ~ 1.332746177 (expected)
- expected probability that a completely random sequence will get to a leaf is about ln(2) ~ 072134
- Shannon entropy of such infinite family of random trees is finite and grows linearly: like about (1/2+(1+gamma)lg(2))n ~ 2.77544n

The funny is that there are very small oscillations around these values - of sin(2pi lg(n)) type.
Here are derived formulas in a few very different ways and only one of each leaded to a series which can be approximated by integral: http://arxiv.org/abs/1206.4555

How to calculate these oscillations - e.g. for D_n=sum_{d=0}^infty 1-(1-2^{-d})^n ?
Especially the first relation seems quite fundamental - maybe someone has seen a paper about something like that before?
Maybe there are some simple intuitions about them?
Last edited by Jarek Duda; July 10th, 2012 at 02:47 AM.