(Header Value)/(Leaf Value) ratio in L.d.a.s: Paradox?

 headers 5   13  21  29  37  45  53  61  69  77  85  ... 805 ...
 leaves  3   9   15  21  27  33  39  45  51  57  63  ... 603 ...
- l.d.a. headers, 5[8], are sparser than leaf nodes, 0[3] (see above)
- so you'd suppose that the (header value)/(leaf value) for l.d.a.s would average 4/3
- in fact, weighted averages on all l.d.a.s of a given length is 1
- e.g.  sss: 2^6*3/(2^3*3^4) = 8/27 weight 1
-      (ssb): 2^7*3/(2^3*3^4) = 16/27 weight 3
-      (sbb): 2^8*3/(2^3*3^4) = 32/27 weight 3
-       bbb: 2^9*3/(2^3*3^4) = 64/27 weight 1
- whose weighted average is ((8+3*16+3*32+64)/27)/8 = (216/27)/8 = 1.0000.
- it's NOT a paradox --- it's a MISTAKE
- should assess at constant power-of-2 depths, not constant l.d.a. length depths
- computer run to 2^25 results in cumulative header/leaf ratio at 1.3295 (increasing from 1 and approaching the expected 4/3)
- Explanation: the abstract tree is unbalanced: the "b" side reaches higher numbers first, so "s" rich l.d.a.s are overweighted in equi-length l.d.a. calculations

next slide             return to slide index       skip past paradoxes