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) = -plog2p - (1 - p)log2(1 - p) (0 < p < 1).

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


Ratkaisu

(Huom: log2x = lnx-
ln2.)
Funktio E on derivoituva välillä 0 < p < 1, ja

E'(p) = -log2p - p  1
-----
pln2 + log2(1 - p) + (1 - p)     1
-----------
(1 - p)ln 2 = log2(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
--
2log2(1
--
2) - 1
--
2log2(1
--
2) = 1
--
2 + 1
--
2 = 1.

Piilota ratkaisu