Dev Shed Lounge
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
User Name:
Password:
Remember me

The Shed is going Social! Join us on FaceBook and Twitter and chime in on the conversation.

Go Back   Dev Shed ForumsOtherDev Shed Lounge

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Rate Thread Display Modes
 
Unread Dev Shed Forums Sponsor:
  #1  
Old July 10th, 2012, 12:54 AM
Jarek Duda Jarek Duda is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Dec 2007
Posts: 44 Jarek Duda User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 Day 2 h 34 m 31 sec
Reputation Power: 6
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.

Reply With Quote
Reply

Viewing: Dev Shed ForumsOtherDev Shed Lounge > Expected number of degree 1 nodes in minimal prefix tree is n*lg(e/2) ...

Developer Shed Advertisers and Affiliates



Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump

Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 


Powered by: vBulletin Version 3.0.5
Copyright ©2000 - 2013, Jelsoft Enterprises Ltd.

© 2003-2013 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap