Re: Jarek Duda's Asymmetric binary system

I want to give some intuition about ANS and why it's so safe.

From the beginning...
We can say that in a natural number x is stored about lg(x) bits.
You probably would like to add ceiling there, but when thinking about
x in higher numeral systems, we asymptotically loose the ceiling.

In symbol(d) which have probability p is stored -lg(p) bits of
information (eg in 0/1 with probability 0.5 is stored 1 bit).
So if we would like to place this information with information stored
in x, it would take about lg(x)-lg(p) bits of information, so
x should be transformed into about x/p.
See that we have it in usual binary system: to store b=0/1 bit with
information stored in x, we can make x->2x+b (it's about x/0.5) - it's
bijection - we can reverse this transform.

Now generally if x-> about x/p, so (x+1)-> about x/q + 1/q
We can do it by placing somehow uniformly with probability q places
which will correspond to this symbol and analogously with other
symbols - we get the tables from ANS initialization:
bijection (x_d,d)->x such that x_d is about x*p_i

In practice we cannot operate on infinitely large numbers, so after
growing above some limit, we forget for a while (move to output) about
some least important digits and work only on first R+1 most important
digit (it almost doesn't change lg(x)) .
So in x is always stored something between R and R+1 bits.
When encoding symbol with probability q, we would increase number of
bits in x by -lg(p), so we have to put into output floor(lg(x)-lg(p)-
R) bits before.

In version for cryptography we place digits uniformly, but using
random generator.
So the symbol(byte?) we get, and place of state we will go to are
fixed, but in fact in random way, depends on the whole context - state
- DEFINED BY WHOLE HISTORY.
The smallest change and we are in a completely different place and
behave completely different.

We have three types of random behavior here:
1) ASYMMETRY (the strongest): different symbols have different
probability - slightest change changes completely place of the next
state
2) UNIFORM COVER: -lg(p_i) is usually irrational, so even with uniform
probability we jump uniformly on the whole space of states - random
behaviors
3) DIFFUSION - in the simplest initialization x*p_i-x_i has standard
deviation sqrt(p_i*(x-2^R)) - it makes that anyway we somehow randomly
diffuse around some expected state.
.

Relevant Pages

  • Re: Rational numbers, irrational numbers: each dense in real numbers
    ... that it is extremely unlikely to have the sequence ... Such a probability distribution, ... probabilities of all but a finite or countably-infinite ... Any uniform nested-finite-distribution system which is ...
    (sci.math)
  • Re: TOE Via Cantors Transfinite Arithmetic
    ... >> for any uniform, random probability distribution over the integers, ... >> the probability that a sample is an even integer is one half. ... people have an easier time accepting a uniform random distribution over ... the reals than they do of one over the integers. ...
    (sci.math)
  • Re: TOE Via Cantors Transfinite Arithmetic
    ... >> for any uniform, random probability distribution over the integers, ... >> the probability that a sample is an even integer is one half. ... people have an easier time accepting a uniform random distribution over ... the reals than they do of one over the integers. ...
    (sci.logic)
  • Re: Cantorian pseudomathematics
    ... >> I understand the probability a divides n when we have a uniform ... >> But there is no uniform distribution on N, so I don't see what Han ... no way to do that with a countable set of discrete ...
    (sci.math)
  • Re: random value generation
    ... non-uniform distribution. ... uniform distribution from to. ... accurate formula. ...
    (comp.soft-sys.matlab)
Loading