Jeg har skrevet om entropi og Theil-indeks da jeg, for få år siden, havde en elev som skulle skrive en SRP (et studieretningsretningsprojekt) om ulighed. Da man typisk i 2.g ser på gini-koefficient, besluttede vi os for at se på et anden mål for ulighed, nemlig Theil-indekset. Det var svært at finde materiale på dansk om Theil-indekset, det var i det hele taget svært at finde noget for en gymnasielev om Theil-indekset. Vi koblede Theil-indekset med entropi, for på den måde at få lidt teoretisk dybde.
Indholdet er inspireret af Flemming Topsøes bog ‘Informationsteori’ fra 1973.
Man kan spørge hvad entropi har at gøre med kryptologi; måske ikke så meget, men entropi hænger sammen med informationsteori og dermed pakning af data, dvs. kodningsteori.
Vi vil her se på hvad der menes med begrebet entropi. Entropi er en størrelse der beskriver mængden af uorden i et system. Jo mere uorden, jo større er entropien.
Vi definerer den reelle entropi \(H_0\) som det antal ja/nej spørgsmål man, i gennemsnit, i en given situation skal stille, for at få klarhed.
Vi skal senere se på den ideelle entropi \(H\).
Den reelle entropi \(H_0\) er altså et tal. Er den reelle entropi \(H_0 = 3\) i en eller anden situation, så skal man altså, i gennemsnit, stille 3 spørgsmål for at få klarhed. Det er klart at det antal spørgsmål man skal stille afhænger af hvor snedigt man spørger, så vi antager at vi spørger så snedigt som muligt. Man snakker så om en optimal spørgestrategi.
Lad os begynde med at se på nogle eksempler.
Person A slår plat eller krone med en mønt. Person B er interesseret i at få at vide om det blev plat eller krone. Det er klart at person B skal stille ét spørgsmål for at få klarhed, så den reelle entropi ved forsøget er 1.
Person A tager et tilfældigt kort fra et kortspil. Person B er interesseret i hvilken kulør kortet har. Peron B kan ikke spørge hvilken kulør kortet har, for person B skal stille et ja/nej spørgsmål. Der er forskellige måder at spørge på.
Spørgestrategi 1 : Person B kan først spørge om kuløren har farven rød, og herefter, hvis svaret er ‘ja’, om kuløren er hjerter, hvis ‘nej’ så er kuløren hjerter. Hvis svaret på om kuløren er rød er ‘nej’, så kan man spørge om kuløren er klør, hvis ‘ja’ så er kuløren klør, eller må den være spar.
Spørgestrategi 2 : Person B kan også straks spørge om kuløren er klør, hvis ‘ja’, så kendes kuløren, hvis ‘nej’, så spørges om kuløren er hjerter. Hvis ‘ja’, så kendes kuløren, hvis ‘nej’, så spørges om næste kulør. Det virker meget kompliceret og uoverskueligt med al den tekst, det er bedre at opstille et ‘spørge-træ’:
Men hvad med den reelle entropi? Den reelle entropi er antallet af spørgsmål, men i gennemsnit skal stille, for at få svar på spørgsmålet ‘Hvilken kulør blev der så?’
Spørgestrategi 1 : Vi bliver nødt til at bruge sandsynligheder for at beregne den reelle entropi . Spørger man om farven er ‘rød’, så er der 50% for ‘ja’, og 50% for ‘nej’. Er farven sort, og spørger man om ‘klør’, så er der 50% for ‘ja’, og farven er klør, og 50% for ‘nej’ og farven er spar. Samme hvis farven er rød, så er der 50% for hjerter og 50% for ruder.
Hver af de fire muligheder har en sandsynlighed på 25%, og de kræver hver to spørgsmål. Det gennemsnitlige antal spørgsmål er dermed
\( p = 0.25 \cdot 2 + 0.25 \cdot 2 + 0.25 \cdot 2 + 0.25 \cdot 2 = 2 \)Spørgestrategi 2 : Betragt træet herover. Først spørger vi om det er en klør. Er det en klør, så har vi fået svar ved brug af ét spørgsmål. Sandsynligheden for, at det er en klør, er naturligvis 1/4. Så sandsynligheden for, at vi kun skal stille et spørgsmål, er 1/4. Er det ikke en klør, så er næste spørgsmål “er det en hjerter”. Hvis svaret på dette er et ja, så har vi fået svar ved brug af to spørgsmål. Sandsynligheden for at vi får svar med to spørgsmål er 3/4 for at det ikke er en klør, ganget med 1/3 for at det er en hjerter. De sidste to kølører kræver begge tre spørgsmål. Beregningen er vist herunder.
\( p = \frac{1}{4} \cdot 1 + \frac{3}{4} \cdot \frac{1}{3} \cdot 2 + \frac{3}{4} \cdot \frac{2}{3} \cdot \frac{1}{2} \cdot 3 + \frac{3}{4} \cdot \frac{2}{3} \cdot \frac{1}{2} \cdot 3 = \frac{1}{4} + \frac{1}{2} + \frac{3}{4} + \frac{3}{4} = \frac{9}{4} = 2,25 \)Bemærk at vi, for hvert ‘blad’ på træet ganger ‘antal grene der fører til bladet’ med alle de sandsynligheder der er undervejs, hvorefter vi lægger dette sammen for alle blade.
Ved at lade en computer vælge et tilfældigt kort (et tilfældigt tal blandt 1, 2, 3 eller 4), og så bruge spørgestrategi 2 til at gætte det udtrukne tal, så kan man let teste resultatet 2,25. Ved 100 gennemløb ender jeg med en reel entropi på 2,23. Ved 1000 gennemløb ender jeg med en reel entropi på 2,254. Ved 1 mio. gennemløb ender jeg med en reel entropi på 2,249.
Her er mit lille Basic-program:
10 rem Antallet af gennemløb kaldes for n
20 rem Det totale antal spørgsmål brugt kaldes for l
30 rem Der vælges så et tilfældigt tal blandt 1, 2, 3, 4
40 rem Hvis r=1 skal antal spørgsmål forøges med 1
50 rem Hvis r=2 skal antal spørgsmål forøges med 2
60 ren hvis r = 3 eller r = 4 skal antal spørgsmål forøges med 3
70 let n = 1000000
80 let l = 0
90 for i = 1 to n
100 let r = rnd(4)+1
110 let l = l+r
120 if r = 4 then let l = l-1
130 next i
140 print n,l/nVi ser altså, at den første spørgestrategi var mere effektiv end den anden spørgestrategi. Da den reelle entropi er det gennemsanitlige antal spørgsmål i den optimale spørgestrategi, så er den reelle entropien altså højst 2. Vi ved nemlig ikke om der er en spørgestrategi der er bedre end spørgestrategi 1.
Men det vender vi tilbage til…