RELATIVNA ENTROPIJA KOT MERA PRESENE ˇ CENJA ˇ ZIGA VIRK Fakulteta za raˇ cunalniˇ stvo in informatiko Univerza v Ljubljani Math. Subj. Class. (2010): 94A17, 94A24 Skozi interpretacijo teorije informacij razloˇ zimo, kako merimo koliˇ cino informacij, pov- preˇ cno koliˇ cino informacij (entropijo) ter preseneˇ cenja, ki izhajajo iz dolˇ zin sporoˇ cil. Mera preseneˇ cenja je poznana pod razliˇ cnimi imeni: relativna entropija, Kullback-Leiblerjeva divergenca . . . RELATIVE ENTROPY AS A MEASURE OF SURPRISE Using the interpretation developed by the coding theory we explain how we measure the amount of information, average content of information (entropy) and surprisal arising from the lengths of codes. The measure of surprisal is known under various names: relative entropy, Kullback-Leibler divergence . . . Uvod V danaˇ snjih ˇ casih smo nenehno v stiku z veliko koliˇ cino podatkov. Nekateri podatki nam podajo veliko informacij, drugi malce manj. V tem ˇ clanku bomo predstavili osnove teorije informacij (informatika in teorija informacij sta razliˇ cni podroˇ cji), skozi katere bomo lahko merili koliˇ cino informacij, povpreˇ cno koliˇ cino informacij (entropijo) in preseneˇ cenje, izhajajoˇ ce iz ko- diranja. Kot motivacijo si oglejmo naslednji dialog. oseba a: ? prevod 1: Kako si se imel za vikend? oseba b: . prevod 2: Dobro. oseba a: ? prevod 3: Je deˇ zevalo? oseba b: . prevod 4: Malce je deˇ zevalo dopoldne. Ravno dovolj, da mi je opralo vesoljsko plovilo. Popoldne ob kosilu pa je ˇ ze sijalo sonce. Obzornik mat. fiz.70 (2023) 1 1 Žiga Virk ˇ Ceprav osebi govorita v nam neznanem jeziku, so nekateri prevodi (pred- postavimo, da so prevodi ustrezni) bolj presenetljivi kot drugi. Izstopata prevoda 3 in 4. Prevoda 1 in 2 sta primerljive dolˇ zine z originalnim zapisom. Prevod 3 je presenetljiv, saj je precej krajˇ si od originalnega zapisa. Kot tak nakazuje na to, da je podajanje informacij v originalnem zapisu precej neu- ˇ cinkovito. V nasprotnem smislu je presenetljiv prevod 4: kratek originalen zapis s ˇ stirimi simboli vsebuje tri povedi. V tem primeru bi podvomili o kva- liteti prevoda ali pa ugibali, da je morda standarden naˇ cin pozdrava (mate- matiˇ cno gledano bi to pomenilo, da se v neznanem jeziku pojavlja z visoko verjetnostjo). Karkoli je ˇ ze razlog, preseneˇ cenji, ki izhajata iz prevodov 3 in 4, sta povezani s priˇ cakovano dolˇ zino prevoda in s tem povezano koliˇ cino informacij. Namen tega ˇ clanka je, da omenjene opazke formuliramo v ma- tematiˇ cni obliki. Pri tem bomo namesto prevajanja obravnavali kodiranje. Obˇ sirna moderna obravnava omenjene matematiˇ cne osnove in interpretacija v kontekstih teorije informacij ter bioloˇ ske raznolikosti je podana v [6]. Zaˇ cetki merjenja informacij segajo v ˇ stirideseta leta dvajsetega stole- tja, ko je Shannon [9] definiral koliˇ cino informacije v kontekstu verjetnosti. Ob tem bi opozorili, da so zaradi interdisciplinarne in ˇ siroko aplikativne narave teorije koncepti veˇ ckrat dobili razliˇ cna imena. Koliˇ cina informacij je poznana pod naslednjimi izrazi: information content, self-information, surprisal (v naˇ sem kontekstu bo preseneˇ cenje nekaj drugega) ter Shannon information. Na osnovi te koliˇ cine je Shannon definiral entropijo sluˇ cajne spremenljivke kot povpreˇ cno koliˇ cino informacij. Koncept entropije je bil takrat seveda ˇ ze poznan, zato se entropiji v naˇ sem kontekstu vˇ casih reˇ ce informacijska entropija ali Shannonova entropija. Entropija je na enak ali podoben naˇ cin definirana v termodinamiki in kvantni fiziki. Kratek pregled literature pokaˇ ze ˇ se ˇ stevilne druge kontekste, v katerih se entropija pojavlja v taki obliki. Na osnovi Shannonovega dela in razumevanja entropije v kontekstu in- formacij je Huffman kot ˇ student razvil algoritem za optimalno kodiranje jezikov [3]. Njegov pristop je poznan pod imenom Huffmanovo kodiranje in je osnova za kompresijske metode brez izgube informacij. Med drugim se izboljˇ save Huffmanovega kodiranja uporabljajo pri raˇ cunalniˇ skih formatih .JPEG [8] in .MP3 [4] datotek. Zadnji koncept, ki ga bomo predstavili v ˇ clanku, je relativna entropija. Le-ta meri preseneˇ cenje v smislu zgornjega primera. Formalno sta jo defini- rala Kullback in Leibler [5], matematiˇ cno pa predstavlja koliˇ cino razliˇ cnosti dveh sluˇ cajnih spremenjivk na n toˇ ckah. Natanˇ cno definicijo bomo podali v zadnjem poglavju. Na tem mestu le omenimo, da gre za nesimetriˇ cno koliˇ cino, zato se je ne omenja z izrazom metrika. V literaturi se omenja pod izrazoma razdalja (distance) ali divergenca (divergence). Kljub nesimetriˇ c- nosti se je relativna entropija izkazala za pomembno koliˇ cino na razliˇ cnih po- 2 Obzornik mat. fiz.70 (2023) 1 Relativna entropija kot mera preseneˇ cenja droˇ cjih. V tuji literaturi je poznana pod razliˇ cnimi imeni: Kullback-Leibler information, Kullback-Leibler distance, Kullback-Leibler divergence, direc- ted divergence, information divergence, information deficiency, amount of information, discrimination information, relative information, gain ali in- formation ali information gain, discrimination distance in error. Na koncu bomo omenili ˇ se pomen in uporabo relativne entropije v zadnjem ˇ casu. Koliˇ cina informacij Koliˇ cino podatkov merimo z biti. Spominska celica v klasiˇ cnem (ne-kvant- nem) raˇ cunalniku praviloma zavzame vrednost 0 ali 1. Koliˇ cina podatkov shranjena v eni taki celici predstavlja 1 bit podatkov. Z enim bitom lahko opiˇ semo dve razliˇ cni stanji, z n biti pa 2 n stanj. Koliˇ cina podatkov pove, ko- liko razliˇ cnih stanj lahko s podatki opiˇ semo. Bite tradicionalno zdruˇ zujemo v byte, ki so osnova za veˇ cje koliˇ cine podatkov: MB, GB . . . Koliˇ cina podatkov na sploˇ sno ni enaka koliˇ cini informacij. Medtem ko koliˇ cina podatkov meri njihovo razseˇ znost v spominu, je informacija odvisna od konteksta. Izjavo »V Ljubljani ob polnoˇ ci ne sije sonce « lahko kot po- datke zapiˇ semo z nekaj sto biti v standardnih kodiranjih, teˇ zko pa bi rekli, da vsebuje kakˇ sno informacijo. Za opredelitev koliˇ cine informacij potrebujemo kontekst. V matematiˇ cnem jeziku bo kontekst diskretna sluˇ cajna spremen- ljivka X z izidi x 1 ,x 2 ,...,x m in pripadajoˇ cimi verjetnostmi p 1 ,p 2 ,...,p m . Koliˇ cino informacij lahko definiramo podobno kot koliˇ cino podatkov. ˇ Ce n bitov podatkov opiˇ se 2 n razliˇ cnih stanj, n bitov informacije opiˇ se 2 n raz- liˇ cnih enako verjetnih dogodkov x 1 ,x 2 ,...,x 2 n (katerih verjetnost je torej 2 − n ). Definicija 1. Koliˇ cina informacij , vsebovana v dogodku verjetnostip, je ena- ka log 2 (1/p ) =− log 2 p bitov. Enota je bit oz. shannon. Osnova 2 v logaritmu izhaja iz dejstva, da en bit podatkov opiˇ se dve razliˇ cni stanji. Obˇ casno se za osnovo uporablja kakˇ sno drugo ˇ stevilo a> 1. Pri tem se zaradi lastnosti logaritmov koliˇ cina informacij spremeni za faktor, odvisen le od a. Pri osnovi e se enoti informacije vˇ casih reˇ ce nat, pri osnovi 10 pa digit oz. hartley. Primeri koliˇ cin informacij v dogodkih: 1. Izid meta poˇ stenega kovanca: 1 bit. 2. Ob 23:00 v Ljubljani ne bo sijalo sonce: 0 bitov, ˇ ce upoˇ stevamo, da se izid zgodi z verjetnostjo 1. 3. V izidu ura je 14:23 (brez podatka o sekundah) je manj informacij kot v izidu ura je 14:23:15. 1–13 3 Žiga Virk 4. Izid meta poˇ stene standardne kocke: log 2 6 = 1 + log 2 3 bitov. 5. Sodost-lihost izida meta poˇ stene standardne kocke: 1 bit. 6. Ostanek izida meta poˇ stene standardne kocke pri deljenju s 3: log 2 3 bitov. Zadnji trije primeri nakazujejo, da naˇ sa definicija zadoˇ sˇ ca priˇ cakovani la- stnosti: ˇ ce sta dogodka A in B neodvisna (torej je P (A∩ B) =P (A)P (B)), potem je koliˇ cina informacije podana z dogodkom A∩ B enaka vsoti koliˇ cin informacij posameznih delov. Sledeˇ ci izrek pove, da ta lastnost do osnove a natanko doloˇ ci funkcijo koliˇ cine informacij (in nedvoumno utemelji defi- nicijo 1). Izrek 2. Naj bo f : [0, 1]→ [0,∞ ) funkcija, ki zadoˇ sˇ ca naslednjim pogojem: 1. f(1) = 0, oz. gotovi dogodki ne podajo niˇ c informacij. 2. f je strogo padajoˇ ca v p, oz. redkejˇ si dogodki podajo veˇ c informacij. 3. f(p· q) =f(p) +f(q). Tedaj je f(p) =− log a p za neki a> 1. Dokaz. Naj bo x = f(1/ 2) > 0. Z induktivno uporabo predpostavke 3 dobimo enakost f((1/ 2) m ) =x· m, za vse m∈ N. (1) Za naravno ˇ stevilo k velja x =f(1/ 2) =f (1/ 2) 1/k k =kf (1/ 2) 1/k in torej f (1/ 2) 1/k = x/k . ˇ Ce v tem primeru ponovno induktivno upora- bimo predpostavko 3, dobimo f (1/ 2) m/k =x· m/k, za vse m,k ∈ N. (2) Izberimot∈ [0,∞ )\Q ter konvergentni zaporedji racionalnih ˇ stevil iz [0 ,∞ ) z limito t: zaporedje s i naj monotono naraˇ sˇ ca proti t, zaporedje z i pa naj monotono pada proti t. Po predpostavki 2 dobimo x· t = lim i→∞ f ((1/ 2) z i )≤ f (1/ 2) t ≤ lim i→∞ f ((1/ 2) s i ) =x· t. 4 Obzornik mat. fiz.70 (2023) 1 Relativna entropija kot mera preseneˇ cenja Torej velja f (1/ 2) t =x· t, za vse t∈ [0, 1]. (3) Iz predpostavk 1 in 2 sledi, da je x > 0. Tedaj je a = 2 1/x > 1, velja x = 1/ log 2 a in po enaˇ cbi (3) sledi f(p) =f (1/ 2) log 1/ 2 p =x· log 1/2 p = 1 log 2 a · (− log 2 p) =− log a p, za vsak p∈ [0, 1]. Entropija kot povpreˇ cna koliˇ cina informacij Entropija diskretne sluˇ cajne spremenjivke je povpreˇ cna koliˇ cina informacij vsebovana v izidih. Definicija 3. Naj bo X diskretna sluˇ cajna spremenljivka z izidi x 1 , x 2 ,... , x m in pripadajoˇ cimi verjetnostmi p 1 ,p 2 ,...,p m . Entropija X je enaka H(X) = m X i=1 p i log 2 (1/p i ). Izraz 0· log 2 (1/ 0) matematiˇ cno ni definiran. V naˇ sem kontekstu bomo kljub temu uporabljali dogovor 0· log 2 (1/ 0) = 0. Prvi razlog je dejstvo, da lahko spremenljivki X vedno umetno dodamo nov izid x m+1 z verjetnostjo 0. S tem spremenljivke praktiˇ cno ne spremenimo, ˇ ceprav smo formalno spremenili (razˇ sirili) njen opis. ˇ Zelimo, da omenjena sprememba ne vpliva na entropijo, tj., da dodaten ˇ clen 0 · log 2 (1/ 0) v vsoti ne spremeni entropije. Drugi razlog je, da izraz 0· log 2 (1/ 0) v entropiji dejansko izhaja izp· log 2 (1/p ) pri p = 0 in lim p↘ 0 p· log 2 (1/p ) = 0. Namesto omenjenega dogovora bi lahko torej vsak izraz p i log 2 (1/p i ) v de- finiciji 3 zamenjali z lim p↘ p i p· log 2 (1/p ). Opazimo, daH(X) lahko zavzame katerokoli vrednost na intervalu [0, log 2 m]: • Minimum: H(X) = 0 natanko tedaj, ko obstaja gotov izidx i , tj.,p i = 1. • Maksimum: H(X) = log 2 m natanko tedaj, ko X predstavlja enako- merno porazdelitev. Veˇ canje entropije pri fiksnem m torej predstavlja premikanje proti ena- komerni porazdelitvi na m toˇ ckah. 1–13 5 Žiga Virk Primeri entropije: • Entropija meta poˇ stenega kovanca je enaka log 2 2 = 1. • Entropija meta poˇ stene kocke je enaka log 2 6. • ˇ Ce kovanec ni poˇ sten, je entropija manjˇ sa kot 1. Veˇ c primerov je podanih na sliki 1. 0 1 2 1 3 4 1 4 1 2 3 4 H = log 2 4 = 2 0 1 2 1 3 4 1 4 1 2 3 4 H = 7 4 0 1 2 1 3 4 1 4 1 2 3 4 H = 1 0 1 2 1 3 4 1 4 1 2 3 4 H = 0 Slika 1. Entropija nekaterih porazdelitev na ˇ stirih toˇ ckah. Uˇ cinkovita kodiranja Pogosto ˇ zelimo, da je naˇ se komuniciranje uˇ cinkovito. Informacije ˇ zelimo izraziti oz. prenesti na ˇ cim bolj ekonomiˇ cen naˇ cin. Med drugimi v ta na- men lahko uporabljamo uˇ cinkovite tipkovnice (npr. tipa Dvorak), okrajˇ save (npr.), kratice (DMFA), bliˇ znjice (Ctrl-C) ipd. Poleg tega se je matematiˇ cni zapis (npr. raˇ cunov) skozi zgodovino razvil v tako obliko, ki uˇ cinkovito poda veliko koliˇ cino informacij. Zapis enaˇ cbe »Osnova naravnega logaritma na potenco korena prvega negativnega celega ˇ stevil pomnoˇ zenega s kvocientom obsega in premera kroga je enaka prvemu negativnemu celemu ˇ stevilu « je rahlo manj uˇ cinkovit kot e iπ =− 1. Uˇ cinkovitost komuniciranja je lepo pov- zel Pitagora: »Ne izrecite malo z veliko besedami, raje povejte veliko v le nekaj besedah.« V tem poglavju si bomo ogledali uˇ cinkovita kodiranja v smislu uˇ cinko- vitega zapisa informacij. Kot obiˇ cajno naj bo naˇ s kontekst diskretna slu- ˇ cajna spremenljivka X z izidi x 1 ,x 2 ,...,x m in pripadajoˇ cimi verjetnostmi 6 Obzornik mat. fiz.70 (2023) 1 Relativna entropija kot mera preseneˇ cenja p 1 ,p 2 ,...,p m . V okviru kodiranja izidi x 1 ,x 2 ,...,x m predstavljajo abe- cedo (seznam ˇ crk oz. simbolov x i ), verjetnosti p i pa so relativne frekvence, s katerimi se ˇ crke x i pojavljajo v danem jeziku ali besedilu, sestavljenem iz zaporedja ˇ crk. Na primer, besedilo lahko predstavlja del zapisa DNK v obliki zaporedja iz ˇ crk A, C, G in T. V primeru besedila v slovenˇ sˇ cini bi bila (kodirna) abeceda sestavljena iz velikih in malih ˇ crk, presledka in loˇ cil (ter potencialno drugih uporabljenih znakov). V naˇ sem kontekstu torej na podlagi podanega besedila generiramo slu- ˇ cajno spremenljivko X, ki predstavlja relativne frekvence ˇ crk. Kodiranje besedila pomeni, da vsaki ˇ crki priredimo dvojiˇ sko kodo (konˇ cno zaporedje niˇ cel in enic), s katero bomo dotiˇ cno ˇ crko predstavili v raˇ cunalniˇ skemu po- mnilniku. Definicija 4. Kodiranje sluˇ cajne spremenljivke X je injektivna preslikava, ki vsakemu izidu x i priredi kodo (vˇ casih omenjeno kot kodno besedo) y i v obliki konˇ cnega dvojiˇ skega zaporedja (tj. zaporedja, sestavljenega iz ˇ stevil 0 in 1). Kode morajo biti seveda take, da lahko iz njih enoliˇ cno rekonstruiramo originalno besedilo. Znano je kodiranje ASCII, ki vsak znak obiˇ cajno zako- dira s sedmimi oz. osmimi biti. Rekonstrukcija besedila je v tem primeru enostavna, saj vsakih osem bitov predstavlja en simbol abecede. Za zapis besedila dolˇ zine n bomo torej porabili 8n bitov. Bistveno vpraˇ sanje je, ali lahko to dolˇ zino zmanjˇ samo brez izgube informacij. Izkaˇ ze se, da je odgovor pogosto da. Zaˇ cnimo razlago s primerom. ˇ crka frekvenca kodiranje 1 kodiranje 2 neustrezno kodiranje a 0,5 0 0 0 0 b 0,25 0 1 1 0 0 1 c 0,25 1 0 1 1 1 0 d 0 1 1 11 povpreˇ cna dolˇ zina kode 2 3/2 - Tabela 1. Primer kodiranja. Tabela 1 podaja abecedo (a, b, c, d) s pripadajoˇ cimi relativnimi frekven- cami ˇ crk/vrednostmi. Ker so ˇ crke ˇ stiri, lahko vse enoliˇ cno zapiˇ semo z dvema bitoma, kar porodi kodiranje 1. V tem primeru je povpreˇ cna dolˇ zina kode ˇ crke enaka 2. Kodiranje 2 predstavlja alternativno kodiranje, pri katerem je povpreˇ cna dolˇ zina kode ˇ crke enaka 0, 5· 1 + 0, 25· 2 + 0, 25· 2 = 3/ 2. 1–13 7 Žiga Virk Z uporabo tega kodiranja bodo torej kodiranja v podani abecedi precej krajˇ sa brez izgube informacij. Ideja pri kodiranju 2 je, da bolj pogostim oz. verjetnim ˇ crkam priredimo krajˇ so kodo. Pri tem morajo biti ˇ crkam prirejene take kode, da lahko iz kodiranja enoliˇ cno rekonstruiramo besedilo. To najlaˇ zje doseˇ zemo, ˇ ce so zaˇ cetki kod razliˇ cni: Definicija 5. Kodiranje sluˇ cajne spremenljivke X s kodami y 1 ,y 2 ,...,y m je predponsko (instantaneous oz. prefix-free), ˇ ce se nobena koda y i ne pojavi kot zaˇ cetno zaporedje kakˇ sne druge kode. Primer kodiranja, ki ni predponsko, je podan v tabeli 1 pod stolpcem neustrezno kodiranje: koda 0 ˇ crke a je zaˇ cetni odsek kode 0 1 ˇ crke b. Zapis 010 lahko predstavlja besedo ac ali ba. Rekonstrukcija v tem primeru ni enoliˇ cna, s kodiranjem smo torej izgubili nekaj informacije. Tabeli 2 in 3 podata ˇ se nekaj podobnih primerov kodiranja. ˇ crka p kodiranje 1 kodiranje 2 a 0,5 0 0 0 b 0,25 0 1 1 0 c 0,125 1 0 1 1 0 d 0,125 1 1 1 1 1 povpreˇ cna dolˇ zina kode 2 7/8 Tabela 2. Drugi primer kodiranja. ˇ crka p kodiranje 1 kodiranje 2 a 1/3 0 0 0 b 1/3 0 1 1 0 c 1/3 1 0 1 1 povpreˇ cna dolˇ zina kode 2 5/3 Tabela 3. Tretji primer kodiranja. Pri tem se zastavi vpraˇ sanje: do kolikˇ sne mere lahko skrajˇ samo pov- preˇ cno dolˇ zino kode? Izkaˇ ze se, da je spodnja meja podana z entropijo X (glej alinejo 2 v izreku 6). Izrek 6. Naj bo X diskretna sluˇ cajna spremenljivka (abeceda) z izidi (ˇ cr- kami)x 1 ,x 2 ,...,x m in pripadajoˇ cimi verjetnostmi (relativnimi frekvencami) p 1 ,p 2 ,...,p m . Podano naj bo predponsko kodiranje, ki ˇ crki x i priredi kodo y i dolˇ zine L i . Tedaj velja: 8 Obzornik mat. fiz.70 (2023) 1 Relativna entropija kot mera preseneˇ cenja 1. P m i=1 (1/ 2) L i ≤ 1. 2. Povpreˇ cna dolˇ zina kode je veˇ cja ali enaka entropiji: P m i=1 p i L i ≥ H(X). Dokaz. 1. Vsakemu ˇ stevilu t na intervalu [0, 1) lahko priredimo dvojiˇ ski zapis (upoˇ stevajoˇ c le decimalke): t = 0,b 1 b 2 b 3 ... oziroma t = ∞ X i=1 b i · 2 − i . Pri tem se za ˇ stevila z dvema zapisoma (npr. 0 , 011111... = 0, 1) omejimo le na tisti zapis, ki se ne konˇ ca z neskonˇ cnim zaporedjem enic. Vsaki kodi y i priredimo interval J i ={ t∈ [0, 1)| dvojiˇ ski zapis t se zaˇ cne z y i } . Na primer: • ˇ Ce je y 1 = 1, potem je J 1 = [1/ 2, 1), saj so dvojiˇ ski zapisi vseh ˇ stevil na J 1 oblike 0, 1 ∗ (zapis 0, 1 ∗ pomeni, da je prva decimalka 1, druge decimalke pa so poljubne). • ˇ Ce je y 2 = 011, potem je J 2 = [3/ 8, 4/ 8), saj so dvojiˇ ski zapisi vseh ˇ stevil na J 2 oblike 0, 011 ∗ (zapis 0, 011 ∗ pomeni, da so prve tri decimalke 0, 1 in 1, ostale decimalke pa so poljubne). Intervali J i so disjunktni zaradi predponskosti kodiranja in vsebovani v [0, 1). Po definiciji so njihove dolˇ zine (1 / 2) L i . Skupna dolˇ zina ne more presegati dolˇ zine intervala [0 , 1), kar pomeni P m i=1 (1/ 2) L i ≤ 1. 2. Pri dokazu alineje 2 bomo uporabili konkavnost funkcijef(x) = log 2 x (za neenakost med vrsticama 2 in 3) ter alinejo 1 (na zadnjem koraku). H(X)− m X i=1 p i L i = m X i=1 p i log 2 (1/p i ) + m X i=1 p i log 2 (1/ 2) L i = m X i=1 p i log 2 (1/ 2) L i p i ≤ log 2 m X i=1 p i · (1/ 2) L i p i ! = log 2 m X i=1 (1/ 2) L i ! ≤ log 2 1 = 0 Sledi H(X)≤ P m i=1 p i L i . 1–13 9 Žiga Virk Opomba 7. Alineja 1 izreka 6 se imenuje Kraft–McMillanova neenakost, glej str. 46 v [6]. Kodiranje sluˇ cajne spremenljivke X, pri katerem za dolˇ zine kod L i izi- dov x i velja L i = log 2 (1/p i ), se imenuje idealno kodiranje. V praksi takˇ sno kodiranje obstaja natanko tedaj, ko so p i potence ˇ stevila 1 / 2. Po definiciji entropije za idealna kodiranja velja, da je njihova povpreˇ cna dolˇ zina kode enaka entropiji. Kodiranji ˇ stevilka 2 v prvih dveh tabelah sta idealni ko- diranji, kodiranje v tretji tabeli pa ne. Naslednji izrek pove, kako lahko konstruiramo kodiranje sluˇ cajne spremenljivke X, pri katerem se povpreˇ cna dolˇ zina kode spodnji meji pribliˇ za do enega bita natanˇ cno. Izrek 8. Naj bo X diskretna sluˇ cajna spremenljivka (abeceda) z izidi (ˇ cr- kami)x 1 ,x 2 ,...,x m in pripadajoˇ cimi verjetnostmi (relativnimi frekvencami) p 1 ,p 2 ,...,p m . Tedaj obstaja predponsko kodiranje, ki ˇ crki x i priredi kodo y i dolˇ zine L i =⌈ log 2 (1/p i )⌉ . Poleg tega velja P m i=1 p i L i