🚀 go-pugleaf

Simon wrote:

> To all
>
> X is a discrete random variable that takes on one of the values x1, x2,
> ..... , xn, with respective probabilities p1, p2, .... ,pn.
>
> The entropy of X is defined as:  H(X) = -Sum{pi*log(pi)} in which log means
> log with base 2 and Sum means summation over all i.
>
> Please, could someone explain to me why H(X) is maximized when all of the pi
> are equal??
> (It is quite easy to prove when n=2)(But what to do when n>2???)
>

differentiation with respect to pi yields Log(pi)+1=0, i=1...n, So you can see
immediately that the pi have to be equal. Sum(pi)=1 leads to the values of pi,
pi=1/n.

Hi Simon,

if H(X) = H(p1,...,pn) is maximal for some p1,...,pn then necessarily
the n+1 partial derivatives of function
F(p1,...,pn,z) := H(p1,...,pn) + z*(p1+...+pn)
vanish w.r.t. all of its arguments p1,...,pn,z.
Altogether this makes n+1 equations for the n+1 unknowns p1,...,pn,z yielding
p1=...=pn=1/n. (This method is known as the method of Lagrangian multipliers
in n dimensional calculus!)

Regards Wolfgang

--
Wolfgang Thumser
Universit��t Bielefeld
Fachbereich Mathematik
email: thumser@mathematik.uni-bielefeld.de

The line should read:

F(p1,...,pn,z) := H(p1,...,pn) + z*(p1+...+pn-1)

Sorry, Wolfgang

--
Wolfgang Thumser
Universit��t Bielefeld
Fachbereich Mathematik
email: thumser@mathematik.uni-bielefeld.de

"Simon" <s.salm@cable.a2000.nl> writes:

>To all

>X is a discrete random variable that takes on one of the values x1, x2,
>..... , xn, with respective probabilities p1, p2, .... ,pn.

>The entropy of X is defined as:  H(X) = -Sum{pi*log(pi)} in which log means
>log with base 2 and Sum means summation over all i.

>Please, could someone explain to me why H(X) is maximized when all of the pi
>are equal??
>(It is quite easy to prove when n=2)(But what to do when n>2???)

Are you familiar with the method of Lagrange multipliers? Roughly
speaking it says that if H(p1,p2,..pn) has a maximum on the (hyper)surface
F(p1,p2,...pn)=0 then at that point the gradients of G and F are linerly
dependent.

Applying this with the entropy H (considered a function of p1,...,pn)
and F(p1,...pn) being p1 + p2 + ... +pn -1, we get
grad H = (log(p1) - 1 ,...,log(pn) - 1) = k*grad F = (k,k,...,k).
at the maximum.

--
Dan Luecking                           Dept. of Mathematical Sciences     
luecking@comp.uark.edu                 University of Arkansas      
http://comp.uark.edu/~luecking/        Fayetteville, AR 72101

+ "Simon" <s.salm@cable.a2000.nl>:

| X is a discrete random variable that takes on one of the values x1, x2,
| ..... , xn, with respective probabilities p1, p2, .... ,pn.
| 
| The entropy of X is defined as: H(X) = -Sum{pi*log(pi)} in which log
| means log with base 2 and Sum means summation over all i.
| 
| Please, could someone explain to me why H(X) is maximized when all
| of the pi are equal??  (It is quite easy to prove when n=2)(But what
| to do when n>2???)

If your library has a copy of the book "Information theory and coding"
by Norman Abramson (it's from 1963, so it may be hidden away in the
basement), you can find a clear explanation there.  Otherwise, you can
do it yourself, by using the Lagrange multiplier method on the sum
with the constraint Sum{pi}=1.  But the book is a good read if you can
get hold of it.

-- 
* Harald Hanche-Olsen     <URL:http://www.math.ntnu.no/~hanche/>
- "There arises from a bad and unapt formation of words
   a wonderful obstruction to the mind."  - Francis Bacon

On Wed, 13 Oct 1999, Simon wrote:
> X is a discrete random variable that takes on one of the values x1, x2,
> ..... , xn, with respective probabilities p1, p2, .... ,pn.
> 
> The entropy of X is defined as:  H(X) = -Sum{pi*log(pi)} in which log means
> log with base 2 and Sum means summation over all i.
> 
> Please, could someone explain to me why H(X) is maximized when all of the pi
> are equal??
> (It is quite easy to prove when n=2)(But what to do when n>2???)

You can do this without using Lagrange multipliers explicitly. First note 
that Ln x <= x-1

Thus      Ln (1/(n.p_k)) <=  1/(n.p_k)-1 

Hence     sum p_k Ln (1/(n.p_k)) <= 1 - sum p_k =0

and so    sum p_k log (1/n) <=  sum p_k log p_k   (logs to base 2)

so                log n    >=  H

See Dominic Welsh "Codes and Cryptography" OUP 1988 for more 
details.

Steve.                

Simon wrote:
> 
> To all
> 
> X is a discrete random variable that takes on one of the values x1, x2,
> ..... , xn, with respective probabilities p1, p2, .... ,pn.
> 
> The entropy of X is defined as:  H(X) = -Sum{pi*log(pi)} in which log means
> log with base 2 and Sum means summation over all i.
> 
> Please, could someone explain to me why H(X) is maximized when all of the pi
> are equal??
> (It is quite easy to prove when n=2)(But what to do when n>2???)
> 
You have the function

H=-Sum[p_i log p_i]

which you like to maximize. But there is also a constraint, namely

Sum p_i=1

To solve this problem we use the Lagrange-method and build

h=-Sum[p_i(lambda+log p_i)]

Now we maximise this function treating all p_i as independently. Thus we
have to differntiate with respect to p_j

\partial_{p_j} h=-(lambda+1+log p_j)=0

Thus we get:

p_j=exp[-(lambda+1)]=const.

We have to chose further lambda such that you fulfill the constraint,
i.e.,

p_j=1/N

if j runs from 1...N.

How to solve the same problem for continuous probability variables read
my script about statistical physics from my home page. There you find
the physical applications to information theory the maximum entropy
principle comes from (your H has to be read as an eta, which notation
was introduced by Boltzmann ;-))).



-- 
Hendrik van Hees		Phone:  ++49 6159 71-2755
c/o GSI-Darmstadt SB3 3.162	Fax:    ++49 6159 71-2990
Planckstr. 1			mailto:h.vanhees@gsi.de
D-64291 Darmstadt		http://www.gsi.de/~vanhees/index.html