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 =
.)
Funktio E on derivoituva välillä 0 < p < 1, ja
E'(p) = -log2p - p
+ log2(1 - p) + (1 - p)
= log2(
).
Siis E'(p) = 0 jos ja vain jos
= 1 eli p =
.
Selvästi E'(p) > 0, kun 0 < p <
, ja E'(p) < 0, kun
< p < 1, joten p =
on todella
funktion E maksimikohta välillä 0 < p < 1.
Kysytty maksimiarvo on
E(
) = -
log2(
) -
log2(
) =
+
= 1.