July 10th, 2012, 01:54 AM

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 n1 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(12^{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.