Information Entropy

Jim Mahoney
April 2005

Preface

Consider a stream of symbols such as (a c b a a d a a d c...).  How much information is contained in such a stream?  One way to approach this question is by imagining that we're receiving these symbols one at a time, and trying to guess which symbol will come next based on those alreaady sent.  If, for example, we notice that every time a "q" is sent that the next character is always a "u", then sending that "u" doesn't really tell us anything that we don't already expect.

Claude Shannon defined a notion of "information entropy" that gives a rigorous version of this approach in his classic paper " A mathematical theory of communication".  The purpose here is to summarize and explore some of his ideas.

Many discussions of this topic assume that a Markov process generates the sequence of symbols; that is, a set of conditional probabilities is given from which the stream is created.  Here we'll also do the reverse, extracting the conditional probabilities and appproximations to the entropy from a given finite sequence of symbols.

Definitions

First, here are notations for the alphabet of symbols and sequences of these symbols.

	M					number of distinct symbols in our alphabet
	{(Subscript[x, i])}		{a,b,c,...}		a finite set of symbols, 1 ≤ i ≤ M
	x, y, z					variables representing symbols from {(Subscript[x, i])}
	N					number of symbols in a sequence (Subscript[S, N])
	(Subscript[S, N])		 a b a ... c a		a sequence of N symbols from alphabet {(Subscript[x, i])} 
	S		 a a b c a...		limit N->∞ of (Subscript[S, N]) ; Shannon's "stream"

Second, notations for counting symbols, pairs, triples, and n-tuples, and the associated probabilities.  

If the stream is defined by a Markov process, then the probabilities that define that process are the fundamental building blocks, not the symbol counts.  In that case, we think of instances of (Subscript[S, N]) as generated by the probabilities.  On the other hand, if we are given (Subscript[S, N]), we can estimate probabilities and conditional probabilities by counting the various k-tuples. 

To avoid edge effects in the counting, we'll assume a "periodic boundry condition", which takes  ..., (Subscript[S, N-1,])(Subscript[S, N]),(Subscript[S, 1,])(Subscript[S, 2]),... as the best approximation to S given (Subscript[S, N]).  In other words, for any finite sequence (Subscript[S, N]), we find N different k-tuples by wrapping around from the end of the string to the beginning.  For example, if (Subscript[S, N])=(a b c a) then the 4 pairs are (a b), (b c), (c a), (a a) ,  the 4 triples are (a b c), (b c a), (c a a), (a a b), and so on.
	
	n(x)					number of occurances of symbol x in (Subscript[S, N])
	p(x)		 =n(x)/N		probability of symbol x in (Subscript[S, N])

	n(x y)					number of occurances of adjacent pairs or 2-tuples ( x y )
	p(x y)		=n(x y)/N		probability of "x y" adjacent pairs (Shannon's p(x,y))
	
	n(x y z)					number of occurances of adjacent triples or 3-tuples (x y z)
	p(x y z)		 =n(x y z)/N		probability of "x y z" adjacent triples

Now for conditional probability notation and concepts for a sequence (x y z).

	p(y|x)		= p(x y)/p(x)		the probability of  y given that the preceding symbol is x  (Shannon's (Subscript[p, x])(y) )
	(Underscript[Σ, y])p(y|x)	= 1			for a given x, the probability of something coming after it is 1
	(Underscript[Σ, x]) p(x)p(y|x)	= (Underscript[Σ, x]) p(x y) = p(y)	the probability of y is the same as p(something y)
	
	p(z|x y)	= p(x y z)/p(x y)	the probability of  z given the preceding pair (x y)

Given all that, we can now define a decreasing sequence of approximations to H.  (Note that Shannon uses a slightly different convention than the one I have below. These days a "0'th order" Markov series (and hence the 0'th order entropy) is taken to be one that does not depend on other symbols, only on the probabilities p(z).  Shannon, on the other hand, calls that the "1st order" entropy, (Subscript[H, 1]).)
									
	(Subscript[H, 0])		= -(Underscript[Σ, z])  p(z)  (Subscript[log, 2]) p(z) 						zeroth order entropy per bit (independent symbol probabilities)
		
	 (Subscript[H, 1]) 		= -(Underscript[Σ, y]){p(y) (Underscript[ Σ, z]){ p(z|y)  (Subscript[log, 2]) p(z|y) } } 			first order entropy per bit (probability depends on one other symbol)
	         		= - (Underscript[Σ, y z]) p(y z) (Subscript[log, 2])[p(y z)/p(y)]
	 
	(Subscript[H, 2])   		= -(Underscript[Σ, x]){p(x)(Underscript[Σ, y]){p(y|x) (Underscript[ Σ, z]){p(z|x y)  (Subscript[log, 2])p(z|x y) }  } }		second order per bit (probability depends on two other symbols)
	         		= - (Underscript[Σ, x y]){ p(x y)  (Underscript[Σ, z]){ p(z|x y)  (Subscript[log, 2]) p(z|x y)  }}
	         		= - (Underscript[Σ, x y z]) p(x y z) (Subscript[log, 2])[ p(x y z)/p(x y)]
	         		
	H		=(Subscript[H, ∞]) = (Underscript[lim , k->∞]) (Subscript[H, k])						true information entropy (i.e. bits of information) per symbol of stream S

If the stream is generated by a Markov process in which the probability of a symbol is determined by the preceding k symbols, then H  = (Subscript[H, k]) exactly.  Thus a zero-order Markov stream has H=(Subscript[H, 0]), a first-order Markov stream with each symbol's probability determined by its predecessor has H=(Subscript[H, 1]), and so on.

The entropy determines how much a symbol sequence can be compressed without loss of information since gives the minimum number of bits required to represent a symbol, on average.  Thus for example if

Examples

1.  {0,1} with probabilities {1/2, 1/2}

If the alphabet is just {0,1}, with independent probabilities
	p(0) = p(1) = (1/2).
Then
	H = (Subscript[H, 1]) =- (1/2)(Subscript[log, 2])((1/2)) - (1/2)(Subscript[log, 2])((1/2))= 1,
since this is a 0'th-order Markov process.  (In other words, the probability of any symbol doesn't depend on any previous symbol.)  This implies that  a random string of 1's and 0's has 1 bit of information per symbol and therefore cannot be compressed without losing information.

One way to think about a Markov process is with a finite state diagram.  For a 0'th order process, the generation of each new symbol follows the same rules and is hence determined by the same state, so the picture looks like this:

2.  {a, b, c, d} with probabilities {1/2, 1/4, 1/8, 1/8}

This example (and its encoding in section 2ii below) is from Shannon's paper.

Again consider a 0th-order Markov process, in which each symbol's probability is independent of what's come before, this time with
	p(a) = 1/2 ,
	p(b) = 1/4 ,
	p(c) = 1/8 ,
	p(d) = 1/8 .
Then
	H = (Subscript[H, 1])=- (1/2)(Subscript[log, 2])((1/2))-(1/4)(Subscript[log, 2])((1/4))-(1/8)(Subscript[log, 2])((1/8))-(1/8)(Subscript[log, 2])((1/8)) = (1/2)+(2/4)+(3/8)+(3/8) = (7/4) = 1.75
Thus a stream of such symbols carries 1.75 bits of information per symbol, as opposed to 2 bits per symbol if the probabilities were all equal.

To think about compressing a stream like this, let's look at several binary encodings of these four symbols.

2 i. { 00=a, 11=b, 01=c, 10=d }

First let's consider a 2 bit encoding {a,b,c,d} -> {00, 11, 01, 10}.  With this encoding the stream of four letters turns into a stream of 1's and 0's which consider to be made up of "words" of two (0, 1) symbols.  For example, (d c b a) would become (10  01  11  00) which consist of four words.

We might guess that since there are twice as many symbols there should be half as much information per symbol, which would imply that the entropy of these 1's and 0's should turn out to be H = 1.75 / 2 =(7/8)= 0.875.  Let's see how it works out.

To find the higher order entropies will need the probabilities of various k-tuples of these 0's and 1's.

The probabilities for (a,b,c,d) and therefore the words are
	symbol		probability	1st (0,1)	2nd (0,1)
	 a		(1/2)		(Subscript[0, 1])		(Subscript[0, 2])
	 b		(1/4)		(Subscript[1, 1])		(Subscript[1, 2])
	 c		(1/8)		(Subscript[0, 1])		(Subscript[1, 2])
	 d		(1/8)		(Subscript[1, 1])		(Subscript[0, 2])
so, averaging over the 1st and 2nd positions within the words, the probabilities for the individual 0's and 1's are
	p(0) = (1/2)p((Subscript[0, 1]))+(1/2)p((Subscript[0, 2])) = (1/2)( (1/2)+0+ (1/8)+0) + (1/2)( (1/2) +0+0+(1/8)) = (5/8) ,
	p(1) = (1/2)p((Subscript[1, 1]))+(1/2)p((Subscript[1, 2])) = (1/2)(  0+(1/4)+0+(1/8)) + (1/2)( 0+(1/4)+ (1/8)+0) =(3/8) 
where subscripts like (Subscript[0, 1])mean a 0 as the 1st symbol in a word.  (Note that with this encoding, the probabilties for the individual 0's and 1's are the same in the beginning and end of words.  In other words, p((Subscript[0, 1]))=p((Subscript[0, 2]))=p(0) and p((Subscript[1, 1]))=p((Subscript[1, 2]))=p(1)).

With these numbers in hand we can calculate the 1st order entropy,
	(Subscript[H, 1])=-(5/8)(Subscript[log, 2])(5/8)-(3/8)(Subscript[log, 2])(3/8)≃0.9544 .

One way to look at the probabilities of of pairs of 0's and 1's is to treat pairs within words differently than those across word boundries - after all, the statistics are different for alternating 0's and 1's in this encoding.

The first symbol in each word doesn't depend on the last symbol of the previous word, so for those first symbols the second order entropy is the same as the first order entropy.  
	(Subscript[H, 2])(first symbol) = (Subscript[H, 1]) ≃ 0.9544

For the second symbol in each word, the conditional probabilities of the 2nd given the 1st are calculated as follows.
	p((Subscript[0, 2])|(Subscript[0, 1])) = p((Subscript[0, 1]) (Subscript[0, 2])) / p((Subscript[0, 1])) = ((1/2))/((5/8))=(4/5)
	p((Subscript[1, 2])|(Subscript[0, 1])) = p((Subscript[0, 1]) (Subscript[1, 2])) / p((Subscript[0, 1])) = ((1/8))/((5/8))=(1/5) 
	p((Subscript[1, 2])|(Subscript[1, 1])) = p((Subscript[1, 1]) (Subscript[1, 2])) / p((Subscript[1, 1])) = ((1/4))/((3/8))=(2/3) 
	p((Subscript[0, 2])|(Subscript[1, 1])) = p((Subscript[1, 1]) (Subscript[0, 2])) / p((Subscript[1, 1])) = ((1/8))/((3/8))=(1/3)
Therefore
	(Subscript[H, 2])(second symbol) =
- p((Subscript[0, 1]))  (p((Subscript[0, 2])|(Subscript[0, 1])) (Subscript[log, 2])p((Subscript[0, 2])|(Subscript[0, 1])) + p((Subscript[1, 2])|(Subscript[0, 1])) (Subscript[log, 2])p((Subscript[1, 2])|(Subscript[0, 1])) )
     - p((Subscript[1, 1])) (p((Subscript[0, 2])|(Subscript[1, 1])) (Subscript[log, 2])p((Subscript[0, 2])|(Subscript[1, 1])) + p((Subscript[1, 1]))p((Subscript[1, 2])|(Subscript[1, 1])) (Subscript[log, 2])p((Subscript[1, 2])|(Subscript[1, 1])))
= - (5/8) ((4/5)(Subscript[log, 2])(4/5) + (1/5)(Subscript[log, 2])(1/5) )- (3/8) ((1/3)(Subscript[log, 2])(1/3) + (2/3)(Subscript[log, 2])(2/3) )
≃ 0.7956

The average of these two is then			(Subscript[H, 2_average]) = ( (Subscript[H, 2])(first symbol in word ) + (Subscript[H, 2])(second symbol in word))/2 
	= (1/2)(-(5/8)(Subscript[log, 2])(5/8)-(3/8)(Subscript[log, 2])(3/8)) + (1/2)(- (5/8) ((4/5)(Subscript[log, 2])(4/5) + (1/5)(Subscript[log, 2])(1/5) )- (3/8)((1/3)(Subscript[log, 2])(1/3) + (2/3)(Subscript[log, 2])(2/3) ))
	= (7/8) bits of information per (0,1) symbol

It isn't quite fair to call this the second order entropy, for we're treating every other bit differently.  Still, it's nice to see that the information per symbol is indeed what we expected when we use all the information available.

To find the rigorous second order entropy following Shannon's definition it would be better to treat each symbol the same, rather than doing a different calculation for the first and second symbols in each word of two symbols.  Then since the joint probabilities of symbols at the end of one word and the beginning of the next are just the products of the independent single symbol probabilities, we have the following joint probabilities across word boundaries.
	 p((Subscript[0, 2]) (Subscript[0, 1]))= p((Subscript[0, 2]))p((Subscript[0, 1]))=(5/8)(5/8)=(25/64)
p((Subscript[1, 2]) (Subscript[1, 1]))= p((Subscript[1, 2]))p((Subscript[1, 1]))=(3/8)(3/8)=(9/64)
 p((Subscript[0, 2]) (Subscript[1, 1]))= p((Subscript[0, 2]))p((Subscript[1, 1]))=(5/8)(3/8)=(15/64)
p((Subscript[1, 2]) (Subscript[0, 1]))= p((Subscript[1, 2]))p((Subscript[0, 1]))=(3/8)(5/8)=(15/64)

Then the pairwise probabilities ignoring word boundaries are the averages of those within and across words, since in choosing a random pair of bits that pair is equally likely to be within one word or straddling a word boundry.
	p(0 0) = (1/2)( p((Subscript[0, 2]) (Subscript[0, 1])) + p((Subscript[0, 1])(Subscript[0, 2])) ) = (1/2)( (25/64)+(1/2)) =(57/128) 
p(1 1) = (1/2)( p((Subscript[1, 2]) (Subscript[1, 1])) + p((Subscript[1, 1])(Subscript[1, 2])) ) = (1/2)( (9/64)+(1/4)) =(25/128)
p(0 1) = (1/2)( p((Subscript[0, 2]) (Subscript[1, 1])) + p((Subscript[0, 1])(Subscript[1, 2])) ) = (1/2)( (15/64)+(1/8)) =(23/128)
p(1 0) = (1/2)( p((Subscript[1, 2]) (Subscript[0, 1])) + p((Subscript[1, 1])(Subscript[0, 2])) ) = (1/2)( (15/64)+(1/8)) =(23/128)

This implies that
	p(0|0) = p(0  0) / p(0) = ((57/128))/((5/8))=(57/80)
p(1|0) = p(0  1) / p(0) = ((23/128))/((5/8))=(23/80)
p(1|1) = p(1 1) / p(1) = ((25/128))/((3/8))=(25/48)
p(0|1) = p(1  0) / p(1) = ((23/128))/((3/8))=(23/48)

which gives 
	(Subscript[H, 2]) = - p(0)  (p(0|0) (Subscript[log, 2])p(0|0) + p(1|0) (Subscript[log, 2])p(1|0) )  -  p(1) (p(0|1) (Subscript[log, 2])p(0|1) + p(1)p(1|1) (Subscript[log, 2])p(1|1))
        = - (5/8) ((57/80)(Subscript[log, 2])(57/80) + (23/80)(Subscript[log, 2])(23/80) )- (3/8) ((23/48)(Subscript[log, 2])(23/48) + (25/48)(Subscript[log, 2])(25/48) )
        ≃ 0.9154

Thus for this stream of 0's and 1's we have a decreasing series of approximate values of the entropy  {(Subscript[H, 0]), (Subscript[H, 1]),(Subscript[H, 2]),...} ≃ {1, 0.9544, 0.9154, ...}, which will asymptotically approach the true entropy H = 0.875.

2 ii. { 0=a, 10=b, 110=c, 111=d }

Now consider a different binary encoding, {a, b, c, d} -> {0, 10, 110, 111}.  This variable length scheme is an example of Huffman coding, and can be visualized by the following tree.

Since the words have different lengths, how can we tell which word a 0 or 1 belongs to when we decode?  The answer is that because the begining of each word is unique, there's only one way to decode the words correctly.  For example, (a a b a c b a) encodes to ( 0 0 1 0 0 1 1 0 1 0 0).  To decode this, we start at the left and look at the first character, which is a 0.  "a" is the only symbol which begins with 0, and so we have the first word, (0).  The next character is another 0, and so again this must be an "a".  Next is a 1.  Since there isn't any word made up of just 1, we append the next symbol to get (10), which we see is "b", and so on.

The number of 0's and 1's it takes to encode a string with N {a,b,c,d} symbols is just the number of 0's and 1's requirerd to code each letter times its expected frequency.  
	(Subscript[N, {0,1}]) =  [ 1((1/2)) +2((1/4)) +3((1/8)) + 3((1/8)) ]   (Subscript[N, {a,b,c,d}])= 1.75   (Subscript[N, {a,b,c,d}])

Moreover, this string of 0's and 1's really does look entirely random; following the probabilities rightwards and down the tree diagram makes that pretty clear:  First, the probability of a "0" or ("10", "110", "111") is 50/50, so the leftmost symbol has a 50/50 chance of being a zero or a one.  If it was a zero, then the next symbol starts the same probabalities all over.  If a one, then we have an even chance between "10" or ("110","111"); again, a 50/50 chance of a zero or one in the next position - and so on.

Calculating the conditional probabilities looking to the left, the preceding digits, is tricker but gives the same result.  The trick is to start by calculating the probability that a given 0 or 1 came from an a, b, c, or d.  These probabilities are
	p(0 from an a) = 1((1/2)) /[ 1((1/2)) +2((1/4)) +3((1/8)) + 3((1/8)) ]  

	p(0 or 1 from b) =2((1/4))  /[ 1((1/2)) +2((1/4)) +3((1/8)) + 3((1/8)) ]
and so on.  I'll leave the rest as an exercise.

2 iii. (Subscript[S, N]) = (  a a b a c a ... ) or (0 1 0 0 1 0 1 ... ) or ...

To see what this looks like numerically, I've written a perl program.

Turns out this isn't too hard to do, though the convergence is a bit tricky - if we pick too high an order for (Subscript[H, N]), then we need some pretty long strings.
Here's the picture of the results; the perl code is in "stream.pl"; pasting it here didn't do a good job keeping the text formatting.

Workspace

H[x_]:=-x Log[2,x];
H1[list_]:=Total[H[list]];

/* entropy for (a,b,c,d) example 2 */

H1[{1/2,1/4,1/8,1/8}]

/* first bit of 2bit word */

H1[{5/8,3/8}]

%//N

/* second bit of 2bit word */

Total[{5/8,3/8}{H1[{4/5,1/5}],H1[{1/3,2/3}]}]

%//N

/* average of bit 1 and bit 2 */

(H1[{5/8,3/8}]+Total[{5/8,3/8}{H1[{4/5,1/5}],H1[{1/3,2/3}]}])/2

Simplify[%]

((Log[2,16384])/(Log[2,65536]))

/* H2 rigorously */

Total[{5/8,3/8} {H1[{57/80,23/80}],H1[{23/48,25/48}]}]

Simplify[%]

%//N

Directory[]

SetDirectory["Desktop"]

p=Import["Shannon.png"];

Show[p]

Show[p,ImageSize->{300,300}]