Principles of Information Science Chapter 3 Measures of information
Principles of Information Science Chapter 3 Measures of Information
3-1 Measures of Random Syntactic Information Shannon Theory of Information Key point 1. nformation is something that can be used to remove uncertainty 2. The amount of information can then be measured by the amount of uncertainty it removed 3. In the cases of communications, only waveform is concerned while meaning and value are ignored 4. Uncertainty and thus information are statistic in nature and statistical mathematics is enough
3-1 Measures of Random Syntactic Information Shannon Theory of Information 2. The amount of information can then be measured by the amount of uncertainty it removed. 1. Information is something that can be used to remove uncertainty. Key point: 3. In the cases of communications, only waveform is concerned while meaning and value are ignored. 4. Uncertainty and thus information are statistic in nature and statistical mathematics is enough
Shannon Theorem of random Entropy The measure of uncertainty, will take the form of N Hs(p )=-k n=1 R log R if the conditions below are satisfied should be a continuous function of p, for all n; n (2)Hs should be a monotonically increasing function ofn when p=1/N for all n 3)Hs should observe the rule of stepped weighting summation
Shannon Theorem of Random Entropy The measure of uncertainty, will take the form of H (p , …, p ) = - k p log p n n=1 N n S 1 N (1) H should be a continuous function of p , for all n; S n if the conditions below are satisfied: (2) H should be a monotonically increasing function of N when p = 1/N for all n; S n (3) H should observe the rule of stepped weighting summation. S
The rule of stepped weighting summation: 1/2 1p.=1/2 1/2 13 2p=1/3 23 2 1/6 1/6 13 3 H(12,13,1/6)=H(12,12)+12H(2/3,1/3)
The rule of stepped weighting summation: 1/2 1/3 1/6 x x x 1 2 3 1/2 1/2 2/3 1/3 x x x 1 2 3 p = 1/2 p = 1/3 p = 1/6 1 2 3 H (1/2, 1/3, 1/6) = H (1/2, 1/2) + 1/2 H (2/3, 1/3) S S S
Proof: (a) In the case of equal probabilities Let Hy(N,…,1N)=A(N) By use condition 3), it is then easy to have A(MN)=Hs(1MN,…,1/N) Hsd1M,…,1M)+;(M)(N,…,1N) Then A(+A(N A(3=2A(N, A(S)=QA(S), A(t=BA(t For any given B, it is always possible to find a proper a such that Q+1
Proof: (a) In the case of equal probabilities S S H (1/N, …, 1/N) = A(N) By use condition (3), it is then easy to have A(MN) = H (1/MN, …, 1/MN) S S M i=1 = A(M) + A(N) Then A(N ) = 2 A(N), A(S ) = A(S), A(t ) = A(t) 2 a a b b Let = H (1/M, …, 1/M) + (1/M) H (1/N, …, 1/N) For any given b, it is always possible to find a proper a such that S t < S a b a+1 (*)
or equivalentI 0g <+ βlogsββ On the other hand, from()we have A(S) A()<A(S+I) aA(s)βA(t)<(+)A(S) or aA(t)<01 βAS)ββ Thus A(S logS/Y A(t) log t When b is large enough, we have A(t=k log t
a b log t log S < b a + 1 b or equivalently On the other hand, from (*) we have A(S ) A(t ) < A(S ) a a b a+1 or A(s) bA(t) < (a+1)A(S) (**) b a A(t) A(S) < a b + 1 b (***) Thus A(t) A(S) - log t log S < 1 b When b is large enough, we have A(t) = k log t
(b)In the case of unequal and rational probabilities Let where n, - positive integer for all i then the unequal distribution entropy Hs(P1,.,PN) becomes the case of equal probabilities: n H(
(b) In the case of unequal and rational probabilities Let ni ni i=1 N i then the unequal distribution entropy H (p , …, p ) becomes the case of equal probabilities: i i = n , n1 H ( … , …, ... , … , ... ) n n i N p = where n -- positive integer for all i. S 1 N
On one hand we have H5(…)=A(1/)=klog(1/ On the other hand )=H1(p,…wp)+;H/n,…1) Hsp,…,只)+1pan) HPp1,…,R)+k=P;g Hence Hsq,…=kuog(1 i-l i p log n I -k, p log n log p (c)If p are irrational, the equation also valid, see(1)
On one hand we have H ( … ) = A(1/ ) = k log (1/ ) On the other hand H ( … ) = H (p , …, p ) + p H (1/n , …, 1/n ) = H (p , …, p ) + A(n ) = H (p , …, p ) + k log n 1 N i i i N i=1 S S S S S 1 N i=1 N p i i=1 N p i S 1 N Hence H (p , …, p ) = k[log(1/ ) - p log n ] = - k p log n = - k p log p i i i=1 N i i i=1 N i=1 N i i i i 1 N (c) If p are irrational, the equation also valid, see (1). S
In the case of ideal observation p1…,R)=B(1,…p-(1,0,…,0) (0log0=0) k pi log pi Let n=2, p=p, the base of logarithm takes the value 2 and H(1n2, 1/2)=I bit, then kl. Therefore we have I(p,,…,R)=H(p, log p(bits
I(p , …, p ) = H (p , …, p ) - H (1, 0, …, 0) = H (p , …, p ) = - k S S S 1 N 1 N 1 N i=1 N p log p i i Let N=2, p = p , the base of logarithm takes the value 2 and H (1/2, 1/2) = 1 bit, then k=1. Therefore we have In the case of ideal observation I(p , …, p ) = H (p , …, p ) = - p log p i i i=1 N 1 N S 1 N (bits) (0 log 0 = 0)
Conclusion For a system with n possible states and their associated probabilities p,,..., p, the average a priori uncertainty about the state of the system is Hs(p,,R The average amount of information a bout the system obtained after observation in ideal case is numerically equal to the uncertainty it removed
Conclusion For a system with N possible states and their associated probabilities p , …, p , the average a priori uncertainty about the state of the system is H (p , …, p ). 1 N S 1 N The average amount of information about the system obtained after observation in ideal case is numerically equal to the uncertainty it removed