Desurvire E. Classical and Quantum Information Theory: An Introduction for the Telecom Scientist
Подождите немного. Документ загружается.
Boltzmann’s entropy 567
= log N
1 +
1
2N
− 1 +
log
(
2π
)
2N
−
m
i=1
N
i
N
log N
i
−
N
i
N
+
log N
i
2N
+
log
(
2π
)
N
%
≈ log N − 1 −
m
i=1
N
i
N
log N
i
+
m
i=1
N
i
N
−
m
i=1
log N
i
2N
=−
m
i=1
N
i
N
log
N
i
N
−
m
i=1
log N
i
2N
≈−
m
i=1
N
i
N
log
N
i
N
≡−
m
i=1
p
i
log p
i
. (A10)
Appendix B (Chapter 4) Shannon’s
entropy
1
Consider a source with N elements of occurrence probability p
i
(i = 1 ...N ). We look
for an information measure H, which should meet three conditions:
(1) H = H ( p
1
, p
2
,..., p
N
) is a continuous function of the probability set p
i
;
(2) If all probabilities were equal (namely p
i
= 1/N ), the function H should increase
monotonously with N ;
(3) If any occurrence breaks down into two successive possibilities, the original H
should break down into a weighed sum of the corresponding individual values of H.
Step 1
We first define A(N ) = H (
1
N
,
1
N
,...,
1
N
), which is the value taken by H when prob-
abilities are equal. Consider now A(2) = H (
1
2
,
1
2
), which is the mean information of
two equiprobable events. After condition (3), if the second event represents two equal
possibilities, the new information measure is given by the weighted sum
H
1
2
,
1
4
,
1
4
= H
1
2
,
1
2
+
1
2
H
1
2
,
1
2
= A(2) +
1
2
A(2).
(B1)
The first term in t he left-hand side represents the information contribution of the two
events, and the second term represents the extra information contained in the second
event (which occurs half of the time). If the first event also represents two equal possi-
bilities, we have
H
1
4
,
1
4
,
1
4
,
1
4
= H
1
2
,
1
4
,
1
4
+
1
2
H
1
2
,
1
2
= A(2) +
1
2
A(2) +
1
2
A(2)
↔ A(4) = 2A(2)
↔ A(2
2
) = 2A(2),
(B2)
1
This is a more detailed description of Shannon’s demonstration. See C. E. Shannon, A mathematical theory
of communication. Bell Syst. Tech. J., 27 (1948), 79–423, 623–56. This paper can be downloaded from
http://cm.bell-labs.com/cm/ms/what/shannonday/paper.html.
Shannon’s entropy 569
where we used the result in Eq. (B1). We can indefinitely repeat this operation of breaking
down each of the single events into two other possibilities, and finally obtain the general
rule:
A(2
m
) = mA(2). (B3)
Consider next A(S) = H(
1
S
,
1
S
,...,
1
S
), representing the information contained in S
equiprobable events. It is clear from the previous demonstration that we also have the
property:
A(S
m
) = mA(S), (B4)
meaning that the gain of information obtained by splitting the S initial events m times is
precisely m.
Since the result in Eq. (B4) applies for any integer S, we also have, for any integer
T = S and n = m,
A(T
n
) = nA(T ). (B5)
Step 2
With a given choice of n (sufficiently large), it is possible to find m for which we have
the double inequality
S
m
≤ T
n
< S
m+1
. (B6)
To convince ourselves of the validity of this result, we take the logarithm of both
inequalities to obtain the following condition on the existence of m (given n, S, T ):
u − 1 < m ≤ u, (B7)
with u = n log T / log S.Ifn is large enough, we have u > 0, regardless of the values of
S and T . According to Eq. (B7); the only two possibilities for m are
(i) u is an integer: m = u,
(ii) u is not an integer: m = E(u),
where E(x) means the integer part of real x (e.g., E (2.75) = 2). The first case is
straightforward. The second case is demonstrated by first setting u = E(u) + x and
u − 1 = E(u − 1) + x where x is a real number satisfying 0 < x < 1. Substituting these
two definitions in Eq. (B7) yields 0 <
x < m − E(u − 1) ≤ 1 + x. Since m − E(u − 1)
is nonzero, we have m > E(u − 1). Since m − E(u − 1) is an integer; we also have
m − E(u − 1) ≤ 1. The only integer solution is m = E(u), since E (u) − E(u − 1) = 1.
The general solution of Eq. (B6) is, thus, m = E (u) = E(n log T/ log S).
570 Appendix B
Having shown that the property in Eq. (B6) is always valid for n sufficiently large, we
perform the following operations:
m log S ≤ n log T < (m + 1) log S
m
n
≤
log T
log S
<
m
n
+
1
n
.
(B7)
Since n can be chosen arbitrarily large, the last result means that
0 ≤
log T
log S
−
m
n
<ε, (B8)
with ε being made arbitrarily small (ε = 1/n → 0).
We now use the property that the function A(N ) is monotonically increasing, as per
requirement (2). With Eq. (B9), this property gives
A(S
m
) ≤ A(T
n
) < A(S
m+1
)(B9)
and with Eq. (B5):
mA(S) ≤ nA(T ) < (m + 1)A(S)
↔
m
n
≤
A(T )
A(S)
<
m
n
+
1
n
↔ 0 ≤
A(T )
A(S)
−
m
n
<ε,
(B10)
ε being made arbitrarily small. Combining Eqs. (B8) and (B10), we get
⎧
⎪
⎪
⎨
⎪
⎪
⎩
0 ≤
log T
log S
−
m
n
<ε
0 ≤
A(T )
A(S)
−
m
n
<ε.
(B11)
This result shows that, as n becomes large (ε → 0), the distance between the function
m/n and the two quantities log T / log S and A(T )/A(S) vanishes. The only possibility
of verifying this property is that we have:
log T
log S
≡
A(T )
A(S)
, (B12)
or
A(T ) = K log T, (B13)
where K is an arbitrary constant, which must be positive to satisfy condition (2).
We can also derive this result more formally using the previously established relation
m = E(u) = E(n log T/ log S), which gives:
⎧
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎩
(i) 0 ≤
log T
log S
−
1
n
E
n
log T
log S
<ε
(ii) 0 ≤
A(T )
A(S)
−
1
n
E
n
log T
log S
<ε,
(B14)
Shannon’s entropy 571
There exist two possible cases:
r
u is an integer: then E(u) = u = n log T/ log S, and the first inequality in Eq. (B12)
intrinsically holds regardless of the size of n. The second inequality converts to
A(T )
A(S)
−
log T
log S
<ε, (B15)
which, in the limit of large n, leads to the conclusion expressed in Eqs. (B12) and
(B13);
r
u is not integer: then E(u) = u + x = n log T / log S + x, where 0 < x < 1. In this
case, the first inequality intrinsically holds regardless of the size of n, and the second
inequality converts to
A(T )
A(S)
−
log T
log S
<ε(1 + x) < 2ε (B16)
which leads to the same conclusion.
2
Step 3
Assume that the source now contains N equiprobable possibilities. Its information mea-
sure is, therefore, H(1/N, 1/N,...,1/N ) = A(N ) = K log N . We can arbitrarily group
these possibilities into m subgroups having n
i
elements each, and whose associated prob-
abilities are p
i
= n
i
/N . According to condition (3), if we define a first partition of two
subgroups of length n
1
and n
2
= N − n
1
, with probabilities p
1
= n
1
/N and p
2
= n
2
/N ,
respectively, we have
A(N ) = H
(
p
1
, p
2
)
+ p
1
A(n
1
) + p
2
A(n
2
). (B17)
In the right-hand development of Eq. (B17), the first term corresponds to the information
provided by this partition and the second two terms corresponds to the information
contained in the two subgroups (weighted by their respective occurrence probabilities
p
1
, p
2
). Note that if any subgroup has only one element (e.g., n
1
= 1), the corresponding
information vanishes, since A(1) = 0.
We can then continue this partitioning by splitting the second subgroup into two new
subgroups with n
2
and n
3
elements (n
2
+ n
3
= N − n
1
) and respective probabilities
p
2
= n
2
/N , p
3
= n
3
/N , yielding the information decomposition:
A(N ) = H
(
p
1
, p
2
, p
3
)
+ p
1
A(n
1
) + p
2
A(n
2
) + p
3
A(n
3
). (B18)
2
It is interesting to note that the Appendix in C. E. Shannon, A mathematical theory of communication.
Bell Syst. Tech. J., 27 (1948), 79–423, 623–56 proceeds differently: Eqs. (B8) and (B11) are written in
the alternative forms |log T / log S − m/n| <εand | A(T )/A(S) − m/n| <ε, respectively. From there, it is
directly concluded that | A(T )/A(S) − log T / log S| < 2ε, which is far from o bvious (as the reader might
easily check). As a matter of fact, this last inequality summarizes at once the results in Eqs. (B15) and (B16)
without providing any of the details. This apparent omission could be explained by the author’s concer n to
save room in a very mathematically intensive paper or, as another possibility, to challenge the reader with
the proof.
572 Appendix B
Iteration of the above partitioning into m subgroups under the condition
m
i=1
n
i
= N
finally yields:
A(N ) = H
(
p
1
, p
2
,..., p
m
)
+
m
i=1
p
i
A(n
i
). (B19)
A general definition of the function H ( p
1
, p
2
,..., p
m
) is, thus, obtained from Eq.
(B19):
H
(
p
1
, p
2
,..., p
m
)
= A(N ) −
m
i=1
p
i
A(n
i
)
= K log N − K
m
i=1
p
i
log n
i
=−K
log
1
N
+
m
i=1
p
i
log n
i
=−K
m
i=1
p
i
log
n
i
N
≡−K
m
i=1
p
i
log p
i
.
(B20)
For an m-symbol source, the only function that satisfies the requirements (1) to (3) is,
therefore:
H =−K
m
i=1
p
i
log p
i
. (B21)
Appendix C (Chapter 4) Maximum
entropy of discrete sources
In this appendix, I show first that for a discrete source of k independent events, X =
{x
1
, x
2
,...,x
k
}, the source entropy is maximized when all events are equiprobable,
corresponding to the uniform distribution. Second, I derive the discrete distribution for
which entropy is maximized when there is a constraint on the mean N =x. With this
constraint, I show that in the case where the events take integer values (x
1
= 0, x
2
=
1,...with k →∞) the entropy is maximized for the discrete exponential distribution of
mean N (Bose–Einstein or thermal distribution). In the case of a discrete source of finite
size, X ={x
1
, x
2
,...,x
k
}, where the events take nonnegative real values, I show that the
distribution maximizing entropy is the Maxwell–Boltzmann distribution. I then analyze
the effect of other additional constraints in the determination of maximum entropy and
of the corresponding distributions.
Uniform distribution solution
By definition, the entropy of the source X ={x, x
2
,...,x
k
} is:
H(X ) =−
k
i=1
p(x
i
)logp(x
i
), (C1)
or, with simplified notation:
H(X ) =−
i
p
i
log p
i
. (C2)
For convenience, I shall use natural logarithms; this does not affect the generality of the
following demonstrations.
Using the method of Lagrange multipliers, we first define the function with parameter
λ as:
f = H (X) + λ
i
p
i
, (C3)
while assuming the constraint:
s
0
= 1 −
i
p
i
= 0. (C4)
574 Appendix C
This constraint ensures that the sum of all probabilities p
i
is equal to unity. The task is
to minimize f with respect to p
i
, namely, to find the solution of:
d f
d
p
j
=
d
f
d
p
j
&
H(X ) +λ
i
p
i
'
= 0, (C5)
which yields:
d
f
d
p
j
=
d
d
p
j
3
−
i
p
i
log p
i
+ λ
i
p
i
4
=
d
f
d
p
j
(−p
j
log p
j
) + λ
=−log p
j
− 1 +λ
= 0,
(C6)
which yields the solution p
j
= exp(λ − 1). Since λ is a constant, the distribution is
uniform. Substituting this result into the constraint s
0
defined in Eq. (C4)gives
s
0
= 1 −
i
p
i
= 1 −
k
i=1
= exp(λ − 1)1 −k exp(λ − 1)
= 0,
(C7)
which yields the solution exp(λ − 1) = 1/k (or λ = 1 −log k), which finally gives
p
i
= 1/k. The conclusion is that the PDF that maximizes the entropy of any discrete
source of k independent events, X ={x
1
, x
2
,...,x
k
}, is the uniform distribution defined
by p(x
i
) = 1/k.
Discrete-exponential (Bose–Einstein) distribution solution
We consider next a second problem, which can be formulated as follows: what is the
discrete distribution of given mean N that maximizes entropy? We note that if a mean
N is specified, the source events must correspond to a discrete set of real values, i.e.,
x
1
= m
1
, x
2
= m
2
,...,x
k
= m
k
with m
i
= m
j
for i = j. Whether the values m
i
are
real or integer, or equally spaced or ordered (i.e., m
i+1
> m
i
) is not important in the
derivation of the general solution to this maximization problem.
The solution comes again from the Lagrange-multipliers method, this time with the
following function to be minimized:
f = H (X) + λ
i
p
i
+ µ
i
x
i
p
i
, (C8)
and with the additional constraint:
s
1
= N −
i
x
i
p
i
= 0, (C9)
Maximum entropy of discrete sources 575
which ensures that the PDF mean is x=N . The minimum of f is found by solving:
d
f
d
p
j
=
d
d
p
j
&
H(X ) +λ
i
p
i
+ µ
i
x
i
p
i
+
'
= 0,
(C10)
or
d
f
d
p
j
=
&
−
i
p
i
log p
i
+ λ
i
p
i
+ µ
i
x
i
p
i
+
'
=−log p
j
− 1 +λ + µx
j
= 0,
(C11)
which yields
d
f
d
p
j
=
&
−
i
p
i
log p
i
+ λ
i
p
i
+ µ
i
x
i
p
i
+
'
=−log p
j
− 1 + λ + µx
j
= 0,
(C12)
and the PDF solution
p
j
= exp(λ − 1 +µm
j
)
= exp(λ − 1)[exp µ]
m
j
≡ PQ
m
j
,
(C13)
with P = exp(λ − 1) and Q = exp µ. To define P, Q, one must then find the two
unknown parameters λ, µ by substituting the result in Eq. (C13) into the two constraints
in Eqs. (C4) and (C9):
s
0
= 1 −
i
p
i
= 1 − P
i
Q
m
i
= 0, (C14)
s
1
= N − P
i
m
i
Q
m
i
= 0, (C15)
which, considering that Q > 0, yields
P =
1
i
Q
m
i
, (C16)
i
(m
i
− N )Q
m
i
= 0. (C17)
Given an arbitrary set of real or integer values m
1
, m
2
,...,m
k
, the solution for Q in
must be computed numerically, since Eq. (C17)isatranscendental equation of the form
a
1
Q
m
1
+ a
2
Q
m
12
+···+a
k
Q
m
1k
= 0, (C18)
where a
i
= m
i
− N . Here, I will not discuss the conditions for which a real solution
Q > 0 may exist in the general case. The only conclusion we can reach is that if such a
576 Appendix C
solution Q exists, the PDF defined in Eq. (C13) takes the form:
p
i
=
Q
m
j
i
Q
m
j
. (C19)
I show next that this PDF matches the discrete exponential distribution (see Chapter 1),
provided we assume that:
(a) m
1
, m
2
,...,m
k
are ordered integers with m
1
= 0, m
2
= 1,...,m
i
= i − 1;
(b) k is infinite;
(c) µ<0 (for which Q < 1, the condition for the denominator in Eq. (C19)tobefinite).
With these assumptions, the solution is Q = N/(N + 1) and P = 1/(N + 1), which
gives
p
i
=
1
N + 1
N
N + 1
i
, (C20)
which is known as the Bose–Einstein (BE) distribution (see Chapter 1).
1
It is shown in
particular that in the limit of large means (N 1), we have H ≈ log N . Incidentally,
this is the same entropy as that of a uniform distribution of N discrete events (N an
integer). The BE distribution corresponds to the photon statistics of incoherent light,
such as those emitted from thermal sources (e.g., candle, light bulb, Sun, stars). It is also
characteristic of spontaneous emission in optical amplifiers.
2
Maxwell–Boltzmann distribution solution
I consider next another case of interest for the solution in Eq. (C19), where:
1
With these assumptions, all summations in the definitions carry from i = 0 to infinity. We then use the
property of the geometrical series
∞
i=0
Q
i
=
1
1−Q
to get the result p
i
= (1 − Q)Q
i
from Eq. (C19). To
solve for Q, we calculate the mean as defined by N =
ip
i
, which develops into:
N = (1 − Q)
∞
i=0
iQ
i
= (1 − Q)Q
∞
i=0
iQ
i−1
= (1 − Q)Q
d
dQ
3
∞
i=0
Q
i
4
= (1 − Q)Q
d
dQ
1
1 − Q
= (1 − Q)Q
1
(1 − Q)
2
=
Q
1 − Q
,
which yields Q =
N
N +1
,thenP =
1
N +1
and proves Eq. (C20). The entropy of the BE distribution is defined
by: H =−
PQ
i
log(PQ
i
). Elementary calculation and substitution of the definitions of P and Q yields
H = (N + 1) log(N + 1) − N log N , which can also be written H = log N (1 +
1
N
)
N +1
. In the limit of
large N (or 1/N = ε → 0), we have H ≈ log{N [1 + (N + 1)ε]}≈log N.
2
E. Desurvire, Erbium-Doped Fiber Amplifiers, Principles and Applications (New York: John Wiley & Sons,
1994), Ch. 3, p. 154. E. Desurvire, How close to maximum entropy is amplified coherent light? Opt. Fiber
Technol., 6 (2000), 357.