Date: Mar 24, 2013 8:57 PM Author: ross.finlayson@gmail.com Subject: Re: Matheology § 224 On Mar 24, 4:48 pm, "Ross A. Finlayson" <ross.finlay...@gmail.com>

wrote:

> On Mar 24, 4:16 pm, Virgil <vir...@ligriv.com> wrote:

>

>

>

>

>

>

>

>

>

> > In article

> > <ab63154d-ab7e-4a03-be1b-17ac93226...@hd10g2000pbc.googlegroups.com>,

> > "Ross A. Finlayson" <ross.finlay...@gmail.com> wrote:

>

> > > On Mar 24, 2:51 pm, fom <fomJ...@nyms.net> wrote:

> > > > On 3/24/2013 4:34 PM, WM wrote:

>

> > > > > On 24 Mrz., 21:29, Virgil <vir...@ligriv.com> wrote:

> > > > >> In article

> > > > >> <729f073f-8948-4eb9-991a-2bd249ac5...@c6g2000yqh.googlegroups.com>,

>

> > > > >> A binary tree that contains one path of each positive natural number

> > > > >> length will necessarily also contain exactly one path of infinite length.

>

> > > > > Like the sequence

> > > > > 0.1

> > > > > 0.11

> > > > > 0.111

> > > > > ...

> > > > > that necessarily also contains its limit?

>

> > > A binary tree that contains one path, of all zero-branches, of each

> > > finite length, will necessarily contain a path of 0-branches of

> > > infinite length.

>

> > Better is

>

> > root

> > | \

> > 0 1

> > | \

> > 0 1

> > | \

> > 0 1

> > | \

> > 0 1

> > | \

> > 0 1

> > | \

> > 0 1

> > | \

> > 0 1

> > | \

>

> > And so on

>

> > --

>

> A binary tree, of all 0's or 1's (0- or 1- branches) with paths of

> each finite length, has a path of infinite length: that is a subtree

> of the intersection[*], of the finite paths. A tree with paths of

> each length n having 0's except the last 1 shows a binary tree with an

> infinite path: that is a subtree of the union of the finite paths.

> As a space-complexity problem it's simpler to maintain the

> intersection[*] than the union.

>

> * [ To be sure, to well-define intersection (i.e. to keep it true), it

> is as the union where the existence of a disjoint leaves the result

> undefined. Basically this of the difference among unary and

> infinitary, and binary and n-ary.]

>

> Basically in entropy coding and Huffman coding there are codes with

> the prefix property that codes of arbitrary width can be put into a

> sequence and demarcated courtesy the prefix property. Then, an idea

> is that with paths as codes with the prefix property and distinct

> length, there would be in the tree a path of each finite length, but

> that paths of greater length would have a different prefix than each

> preceding path.

>

> https://en.wikipedia.org/wiki/Prefix_codehttps://en.wikipedia.org/wiki/Huffman_coding

>

> Then, where Huffman coding is to find the largest alphabet with the

> prefix property with the least average length of the path, here the

> idea for dense bounded tree coding is to find an alphabet with the

> prefix property with one code for each length: with the maximum suffix

> of the path that is disjoint the other code's paths, that each pair is

> mutually disjoint.

>

> Basically this is about codes with the prefix property (that there

> would be a branch from lesser length codes, and the next), the

> palindrome property, or otherwise with the prefix property, and that

> the suffix was not following the suffix of another code initial

> segment, in reverse as it were. Basically it is that the reverse of

> the code of length n as path, would have the prefix property, to the

> initial segment of length n of any code of greater length.

>

> Then, saying that there would always be an infinite path in the union

> of paths of each finite length of the binary tree is that there is no

> "dense bounded" coding as here. Basically that is a question of what

> are the most paths and most lengths (and as to complexity and entropy)

> there can be with the least amount of infinite paths.

>

> Here, again, the intersection[*] of the 0-paths is infinite, the union

> of the 0*1-paths has a subtree that is infinite, a distinct

> difference: the least number of finite paths, with an infinite path.

>

> There is a difference among representations, of unary, infinitary,

> binary, and n-ary (in spaces), structural difference with

> concomitantly various results, as of their variety.

>

This as well get directly to questions on sampling the real numbers

via Bernoulli trials. Flip a coin, it begins a sample, flip another,

it begins another, and refines the first, and so on.

The idea here is to maximize the unique part of the path, sharing the

least among their union. Obviously with 2 paths and maximum variation

each of the first level of the tree is exhausted, with 2 levels there

are 4 possible paths each having their own, with n levels (of the

balanced tree) there are 2'n distinct paths of length n, that share

with (2^n-m)-1 other paths their initial segments length m. The

balanced tree has the most variation, the single path the least. Then

the question of there being a "dense bounded" coding (of natural n>0

to path of length n) is as to there being enough paths through the b-

ary balanced tree, with above that b = 2, that each path is mutually

disjoint. There is an obvious case for b = l that there exist paths

up to length l that would not share initial segments and their

intersection[*] would be empty thus finite, and their union would be

finite. Then, in n-ary, up to n-many paths of distinct lengths up to

l, could be mutually disjoint. For length n+1, at least two paths

share an initial segment of length 1, for n + k<n, the sum of the

length of the shared initial segment goes to n, or here there is a

filling in terms of maximizing variety.

So, there are b^l or b^p (l defined to be p for precision) many paths

in the b-ary balanced tree of depth p. For one path of each length,

the ratio of paths in the path-length-replete tree to the balanced

tree is p / b^p. As the base of the tree increases, there are many

more paths to be distinct for more of their branches, that it takes

b^p branches to saturate each level of depth of the tree, thus to

length b^p.

In the asymptotic: b^p >> p. A tree with only a path for each

length , grows sparse in the union of the paths, where not so

contrived, eg branching at random.

Basically then for a tree to have no dense coding, for a n-lengthed

coding of n E N, with a maximally dispersed coding, will have that a

code of length p, will be the initial segment, of a code of length

b^p.

p -> b^p -> b^(b^p) -> b^(b^(b^p) -> ...

Hmm, that doesn't very simply lend itself to notation as tetration,

the sequence of lengths of paths that would form an infinite path in

the b-ary tree with maximally dispersed paths where no "dense bounded"

coding exists.

L_least(a)_b = {

a = 1: p

a > 1: b^ (... a-1 many times ... ) ^p (right-associative)

}

(Though, it is _tractable_ in tetration.)

As b the base or girth of the tree increases, the number of initial

segments necessarily shared by an infinite path goes to zero.

(Intuitively that the one path would have them all, i.e., share none.)

So, why does no "dense bounded" coding exist, thus that the union of

paths of each length p has an infinite subtree?

Regards,

Ross Finlayson