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

    Join Date
    Dec 2007
    Rep Power

    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 01:47 AM.

IMN logo majestic logo threadwatch logo seochat tools logo