Re: entropy

Article View: de.sci.mathematik

Article #14

#14

From: Steve Noble
Date: Wed, 13 Oct 1999 00:00

27 lines
1860 bytes

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.

Technical Details

Message-ID: <Pine.SUN.3.91.991013182045.22006J-100000@molnir.brunel.ac.uk>

Path: arc1-ca.pugleaf.net!unknown!not-for-mail

References: <7u0bf5$4k3$1@tesla.a2000.nl>

Show Full Headers

Complete Article Headers

X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 10d29f,a1b4de0cf05f260e
X-Google-Attributes: gid10d29f,public
X-Google-Thread: 10d67e,a1b4de0cf05f260e
X-Google-Attributes: gid10d67e,public
X-Google-Thread: 1032cb,a1b4de0cf05f260e
X-Google-Attributes: gid1032cb,public
From: Steve Noble <Steven.Derek.Noble@brunel.ac.uk>
Subject: Re: entropy
Date: 1999/10/13
Message-ID: <Pine.SUN.3.91.991013182045.22006J-100000@molnir.brunel.ac.uk>
X-Deja-AN: 536330698
Approved: Daniel Grayson, dan@math.uiuc.edu, moderator for sci.math.research
References: <7u0bf5$4k3$1@tesla.a2000.nl>
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Complaints-To: usenet@brunel.ac.uk
X-Trace: mimas.brunel.ac.uk 939835954 16644 134.83.108.7 (13 Oct 1999 17:32:34  GMT)
Organization: Brunel University, Uxbridge, UK
Mime-Version: 1.0
NNTP-Posting-Date: 13 Oct 1999 17:32:34 GMT
Newsgroups: de.sci.mathematik,aus.mathematics,sci.math.research
Originator: dan@orion.math.uiuc.edu

Reply to Parent Message