Shannon discrepancy 2

Another side of the Shannon discrepancy is the space distribution defined by the formula

S=Min(2^N,M/N)


where S is the amount of existing objects of size N under a limit of a M size .

spacedistr2

The formula answer to the question “How many bit string exist of Length N inside a limited system ?” It is interesting to see how the curve grow very fast in the starting zone and how decrease very fast in the right side .

In an unlimited system the curve remain exponential and it is impossible to explore all the space , not only all the space but also a significative part of it , instead with limited system as showed this become absolutely feasible.

The central question is : It is better to use a limited model like this or an unlimited model ?

If you place also a very big limit the exponential side grow so fast that the right behaviour start at small value and the problem lose its exponential characteristics.

It is interesting to see how this behaviour explain very well the compression paradox where theoretically the probability to compress a bit sting is 2^-N  ( exponential low ! it is about impossible ) but empirically we know that compression is absolutely feasible also with simple algorithms . Not only the compression work but with small bit strings it is difficult to make compression ( exponential behaviour ) and with large bit strings the compression ratio increase with the length of the string ! ( the right side behaviour )  and this is impossible if the space of the possibilities is exponential .

For this reason and other empirical evidence I think that the space distribution is not exponential and the above formula fit absolutely better the real distribution  .

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s