lacunary - Mathnotes

Definition: Entropy Rate \@{entropy-rate}

Consider a discrete source with i finite number of states, where in state i there is probability pi(j) of producing symbol j. Then, each state i will have an entropy Hi, and the entropy rate of the source will be defined as the average of these Hi weighted by the probability of the occurrence of each state (Pi):

H=∑iPiHi=−∑i,jPipi(j)log⁡pi(j).

In other words, H=E[Hi] - the expected value of the per state entropy.

This is the entropy of the source per symbol of text.

If the source (a @markoff-process) produces symbols at a definite time rate there is also an entropy per second:

H′=∑ifiHi,

where fi is the average @frequency of state i. We can also say

H′=mH,

where m is the average number of symbols produced per seconds, i.e. fi=mPi

H an H′ measure the amount of information generated by the source per symbol and per second, respectively. For log2, they represent bits per symbol and bits per second.

Referenced by (1 direct)

Direct references:

Simplifying, when successive symbols are independent, H=−∑pilog⁡(pi), where pi is the probability of symbol i. Consider a long message S of N symbols. It will contain, with high probability, about piN occurrences of x1, p2N of x2, etc. Therefore the probability of S is approximately

p=p1p1Np2p2N⋯pnpnN=∏ipipiN,

so

log⁡p≈N∑i[pilog⁡pi]log⁡p≈−NHH≈log⁡1/pN.

so entropy is approximately the log of the reciprocal probability of a long sequence divided by the number of symbols in the sequence. The theorem below states this more formally.

Theorem: Weak Asymptotic Equipartition Property \@{theorem-2}

Start with a source alphabet with n symbols a1,…,an, emitted i.i.d. with probabilities p1,…,pn (so pi=Pr(ai)). Its entropy is, by definition,

H=−∑i=1npilog⁡pi.

A message is a sequence S=(x1,…,xN) of length N, each xj∈{a1,…,an}. By independence,

pS=∏j=1NPr(xj)

is the probability of the sequence S being emitted.

Let ϵ,δ>0. Then, there exists N0 such that for all N≥N0, the length-N sequences split into two classes:

  1. The typical set, Aδ(N)={S:|1Nlog⁡1pS−H|≤δ}.
  1. The atypical set, Aδ(N)―, with total probability Pr(Aδ(N)―)<ϵ.

Equivalently, Pr(Aδ(N))→1 as N→∞, i.e. 1Nlog⁡1pS→H in probability.

Proof \@{proof-of-theorem-2}

First some preliminaries. We have two indices to keep straight here:

  • n - our alphabet size; we use i∈{1,…,n} to index distinct symbols ai, each with its own probability pi.
  • N - sequence length; we use j∈{1,…,N} to index positions in a sequence, each holding some symbol xj.

If we let ci=#{j:xj=ai} be the count of symbol ai in S, so ∑i=1nci=N, then we can restate pS as

pS=∏i=1npici.

ci is the only random thing in pS - it doesn't consider position of symbols, just the total count of each symbol (random) and the probability of that symbol being emitted on any given turn (fixed).

Taking advantage of our symbols being emitted i.i.d., we can convert our expression about the surprisal of the sequence to an equivalent expression about the surprisal of individual symbols being emitted:

1Nlog⁡1pS=1Nlog⁡1∏i=1npici=−1Nlog⁡∏i=1npici=−1N∑i=1nlog⁡pici=−∑i=1nciNlog⁡pi.

This final term is very similar to H=−∑i=1npilog⁡pi; we just need to show that ciN→pi as N→∞. The expected value of ci for N draws is the expected count of ai in N draws, and is

E(ci)=Npi.

So, by the @weak-law-of-large-numbers, ciN→pi as N→∞. That is, 1Nlog⁡1pS=−∑i=1nciNlog⁡pi @converges-in-probability to H as N→∞. This means that for any δ>0,

Pr(|1Nlog⁡1pS−H|>δ)→N→∞0.

That is, that for every ϵ>0, there exists N0 such that for all N≥N0,

Pr(|1Nlog⁡1pS−H|>δ)<ϵ.

That is to say, that the total probability of getting a sequence where the surprisal rate 1Nlog⁡1pS is more than δ from H is less than ϵ for all N larger than some N0, which is what we wanted to show.

◻
Intuition \@{theorem-2-intuition}

This is just saying that the empirical frequencies in sequences of symbols generated by this source, (c1N,…,cnN) approach the true probabilities for the source distribution, p1,…,pn as N→∞. In other words, the sequences most likely to be produced by the source (typical sequences) are all about equally likely to occur, with probability

pS≐2−HN.

Theorem: Strong Asymptotic Equipartition Property (Shannon--McMillan--Breiman) \@{theorem-5}

Start with a source of n states a1,…,an, emitted by a @stationary ergodic Markov chain with transition probabilities pik=Pr(Xt+1=ak∣Xt=ai),∑k=1npik=1, and Stationary Distribution of an Ergodic Chain P=(P1,…,Pn). Its entropy rate is, by definition, H=−∑i=1n∑k=1nPipiklog⁡pik. A message is a sequence S=(x1,…,xN) of length N, each xt∈{a1,…,an}. Such a message is a path through the network with probability pS=Px1∏t=1N−1pxtxt+1. Let ϵ,δ>0. Then there exists N0 such that for all N≥N0 the length-N sequences split into two classes:

  1. The typical set, Aδ(N)={S:|1Nlog⁡1pS−H|≤δ}.
  2. The atypical set, Aδ(N)―, with total probability Pr(Aδ(N)―)<ϵ.

Moreover the convergence holds @almost surely: Pr(limN→∞1Nlog⁡1pS=H)=1, so with probability 1 a drawn sequence is typical for all sufficiently large N

Proof \@{proof-of-theorem-5}

--- the left eigenvector solving P=PT for the transition matrix T=(pik) (eigenvalue 1, normalized so ∑iPi=1).

◻
Theorem: Noiseless channel transmitting discrete symbols \@{theorem-7}

Given a communication channel which has a capacity of C bits per second, accepting signals from a source of entropy (or information) of H bits per symbols, it is possible, given a properly devised coding procedure, for the transmitter to transmit symbols over the channel at an average rate which is nearly C/H but which, no matter how clever the coding, can never exceed C/H.

Note \@{note-8}

The unit of C is bits (information) per second, and the unit of H is bits (information) per symbol, so we have

bitssecond×symbolsbit=symbolssecond,

so the unit of C/H is symbols per second.

The best transmitter is one which codes the message in such a way that maximizes the signal entropy and makes it equal to the capacity of the channel, which allows reaching the maximum rate C/H for the transmission of symbols.