Binäärilukujonoja

Insinööriosastojen valintakoetehtävä vuodelta 1999

Datalähde tuottaa binäärilukujonoja, joissa bitti 0 esiintyy todennäköisyydellä p ja bitti 1 todennäköisyydellä 1 - p. Millä todennäköisyyden p arvoilla lähteen informaatiomäärä (entropia), joka määritellään funktiona

E(p) = -plog₂p - (1 - p)log₂(1 - p) (0 < p < 1).

saavuttaa suurimman arvonsa? Mikä tämä suurin arvo on? (log₂ tarkoittaa 2-kantaista logaritmia)

Ratkaisu

(Huom: log₂x = lnx-
ln2

.)
Funktio E on derivoituva välillä 0 < p < 1, ja

E'(p) = -log₂p - p 1
-----
pln2 + log₂(1 - p) + (1 - p) 1
-----------
(1 - p)ln 2 = log₂( 1 - p
------
p ).

Siis E'(p) = 0 jos ja vain jos 1-p
p

= 1 eli p = 1
2

.
Selvästi E'(p) > 0, kun 0 < p < 1
2

, ja E'(p) < 0, kun 1
2

< p < 1, joten p = 1
2

on todella funktion E maksimikohta välillä 0 < p < 1.
Kysytty maksimiarvo on

E( 1
--
2 ) = - 1
--
2 log₂( 1
--
2 ) - 1
--
2 log₂( 1
--
2 ) = 1
--
2 + 1
--
2 = 1.

Piilota ratkaisu