Kategori: Entropi og ulighed

Nu bliver det spændende.

Vi har set på Theil-indekset \(T\) for en mængde individer, hvor indeks i summerer over alle n individer. Her er \(x_i\) indkomsten for person nummer i, og \(\mu\) er den gennemsnitlige indkomst.

\(T = \frac{1}{n} \cdot \sum_{i=1}^{n} \frac{x_i}{\mu} \cdot \log_2(\frac{x_i}{\mu})\)

Vi har set på Theil-indekset \(T_G\) for grupper af individer, hvor indeks j summerer over alle m grupper. I udledningen antog vi at alle individer i samme gruppe har samme indkomst \(x_j\), med \(n_j\) som antallet af medlemmer i gruppe j, og med \(\mu\) er den gennemsnitlige indkomst udregnet ud fra samtlige n individer.

\( 
T_G = \sum_{j=1}^m \frac{n_j}{n} \cdot \frac{x_j}{\mu} \cdot \log_2(\frac{x_j}{\mu})
\)

Formlen for Theil-indekset for grupper svarer til Theil-indekset for individer, dog er bidraget fra hver gruppe ganget med \(\frac{n_j}{n}\) som er den andel individerne i gruppe j udgør af det totale antal individer.

Vi vil nu se på det der kaldes for dekomposition af Theil-indekset.

Antag at vi har n individer. Hver af de n individer hører til i én gruppe. Vi kan beregne Theil-indekset for alle individer. Det giver et mål for den samlede ulighed. Det viser sig, at Theil-indekset for alle individer kan deles i to del:

Del 1 : Theil-indekset for grupperne, der sammenligner ulighed mellem grupperne.
Del 2 : Theil-indekset for individer i samme gruppe, der sammenligner ulighed indenfor grupperne.

Har vi f.eks. data over alle individer i Danmark, deres indkomst, og i hvilken kommune de hører til, så kan vi beregne Theil-indekset for alle danskere. Dette Theil-indeks kan opdeles i to dele, nemlig et bidrag fra ulighederne kommunerne imellem, og et bidrag fra ulighederne indefor de enkelte kommuner. Og vigtigt; vi kan faktisk beregne de forskellige bidrag. Dermed kan vi ikke bare sammenligne kommune med kommune, men også indkomstfordelingen indenfor de de enkelte kommuner.

Det viste sig at være lidt vanskeligt at få det, med dekomposition af Theil-indekset, ‘i kassen’, for det er ikke al information man finder på nettet som er lige præcis, troværdig, gennemarbejdet. Heldigvis kan man jo regne på det selv, og så sammenligne resultatet man får med de forskellige kilder. Jeg mener selv at jeg har nået frem til et korrekt udtryk for dekompositionen, og jeg er ret sikker på fortolkningen af dekompositionen.

Der indgår mange forskellige størrelser i den endelige formel, og det siger sig selv, at det ikke er lige meget hvad hver enkelt størrelse betyder. Her er en oversigt over de størrlser jeg bruger.

Der er n individer i alt. Gennemsnitsindkomsten for alle er \(\mu\).

Alle individer inddeles i m grupper:

Gruppe 1 består af \(n_1\) individer. Deres gennemsnitsindkomst er \(x_1\)
Gruppe 2 består af \(n_2\) individer. Deres gennemsnitsindkomst er \(x_2\)
...
Gruppe m består af \(n_m\) individer. Deres gennemsnitsindkomst er \(x_m\)

Jeg bruger indekset j til grupperne. Når j = 1 er der således tale om gruppe 1, når j = 2 er der tale om gruppe 2, o.s.v.

De forskellige individers indkomst benævnes \(x_{ji}\), hvor j er gruppens nummer, og i er individets nummer i denne gruppe. F.eks. er \(x_{53}\) indkomsten af individ nummer 3 i gruppe 5.

Desuden er \(x_j\) gennemsnitsindkomsten for alle individer i gruppe j.

Man tager så udtrykket for Theil-indekset for alle individer; det er det udtryk vi har øverst på siden. Efter en del omskrivninger (kommer senere) kan dette udtryk skrives om til følgende udtryk:

\(
T = \sum_{j=1}^m \sum_{i=1}^{n_j} \frac{x_{ji}}{n \cdot \mu} \cdot \log_2(\frac{x_{ji}}{x_j})
+
\sum_{j=1}^m \frac{n_j}{n} \cdot \frac{x_j}{\mu} \cdot \log_2(\frac{x_j}{\mu})
\)

Den første sum på højre side kan skrives som

\(
\sum_{j=1}^m \frac{n_j}{n} \cdot \frac{x_j}{\mu} \cdot T_j \quad \textrm{ med } \quad 
T_j = \frac{1}{n_j} \cdot \sum_{i=1}^{n_j} \frac{x_{ij}}{x_j} \cdot \log_2(\frac{x_{ji}}{x_j})
\)

hvor \(T_j\) er Theil-indekset for alle individer i grupper j .

Den sidste sum er Theil-indekset \(T_G\) for grupperne, se næstøverste formel.

Dermed ender vi med dekompositionen

\(
\sum_{j=1}^m \frac{n_i}{n} \cdot \frac{x_i}{\mu} \cdot T_j + T_G
\)

Første sum måler uligheden indenfor hver gruppe j, og vægter dem efter antal individer i gruppe j og gennemsnitsindkomsten i gruppe j, i forhold til det samlede antal individer og det samlede gennemsnit. Anden del er, som nævnt, ikke andet end Theil-indekset for grupperne; her måles uligheden mellem de forskellige grupper.

Pointen i dekompositionen er, at den samlede ulighed for alle individer kan skrives som én del der måler uligheden indenfor hver enkelt gruppe, og én del som måler uligheden mellem de forskellige grupper.

Eksempel 1. Hvis alle indkomster er ens, så er der ingen ulighed mellem grupperne, og der er ingen ulighed indenfor grupperne, så begge bidrag til Theil-indekset er nul, og hele Theil-indekset er nul.

Eksempel 2. Er gennemsnitsindkomsten i alle grupper nogenlunde ens, men er der er forholdsvis stor spredning indefor de enkelte grupper, så vil bidraget til det samlede Theil-indeks fra gruppeuligheden være lille, og bidraget fra uligheden indenfor de enkelte grupper være forholdsmæssig stor.

Eksempel 3. Simulation med Maple. 10 grupper, 100 personer i hver gruppe. Gennemsnitsindkomst i gruppe j er normalfordelt med middelværdi 5000+1000 j og spredning 1000.

Tabellen viser bidragene til det samlede Theil-indeks fra ulighed indenfor de enkelte grupper og fra ulighed grupperne imellem. Det samlede Theil-indeks blev 0.06077.

	Internt i gruppe	Grupperne imellem
Gruppe 01	0.000941	-0.046299
Gruppe 02	0.000894	-0.039794
Gruppe 03	0.000860	-0.027383
Gruppe 04	0.000828	-0.016148
Gruppe 05	0.000652	-0.009024
Gruppe 06	0.000591	0.007728
Gruppe 07	0.000624	0.022502
Gruppe 08	0.000428	0.036204
Gruppe 09	0.000562	0.054449
Gruppe 10	0.000497	0.071667
Samlet	0.006877	0.053900

Vi ser at bidragene til Theil-indekset, fra intern ulighed i grupperne, er størst for de første grupper. Det skyldes at gennemsnits-indkomsten i disse grupper er mindst, og med en fast spredning er variationen i indkomsterne større end i de sidste grupper med en større gennemsnitsindkomst, og samme spredning på indkomsten.

Bidragene til Theil-indekset fra grupperne er negative for de første grupper. Det skyldes at gennemsnits-indkomsten i disse grupper er mindre end den samlede gennemsnitsindkomst. Bemærk at bidragene fra ulighederne internt i grupperne alle er positive; det skyldes at hver af størrelserne er reelle Theil-indeks, bare beregnet for hver gruppe for sig.

Vi vil nu udlede en formel for Theil-indekset for grupper.

Vi betynder med Theil-indekset for ‘individer’:

\( 
T = \frac{1}{n} \sum_{i=1}^{n} \frac{x_i}{\mu} \cdot \log_2(\frac{x_i}{\mu})
\)

Vi har N personer, men nu er de samlet i m grupper.
Alle individer i samme gruppe har samme indkomst \(x_j\).
Antallet af personer i gruppe j kalder vi \(n_j\).
Vi bruger bogstavet j som fodtegn for at tydeliggøre hvilken gruppe vi ser på.

Gruppe 1. j = 1. Indkomst for hvert individ i gruppe 1 er \(x_1\).
Gruppe 2. j = 2. Indkomst for hvert individ i gruppe 2 er \(x_2\).
...
Gruppe m. j = m. Indkomst for hvert individ i gruppe m er \(x_m\).

Den gennemsnitlige indkomst for alle de N personer kalder vi \(\mu\).

Summen i formlen for Theil-indekset er en sum over alle personernes indkomst. Vi kan opdele summen så vi først summerer over alle personer i gruppe 1, så summerer over alle personer i gruppe 2, o.s.v. Dermed får vi:

\( 
T = \frac{1}{N} \sum_{j=1}^m
  \sum_{i=1}^{n_j} \frac{x_j}{\mu} \cdot \log_2(\frac{x_j}{\mu})
\)

I den inderste sum \(\sum_{i=1}^{n_j} \frac{x_j}{\mu} \cdot \log_2(\frac{x_j}{\mu})\) summerer vi over alle individer i samme gruppe, og deres personlige indkomst er ens. Vi får derfor \(n_j\) led der er ens, og den inderste sum giver så

\(
\sum_{i=1}^{n_j} \frac{x_j}{\mu} \cdot \log_2(\frac{x_j}{\mu})
= n_j \cdot \frac{x_j}{\mu} \cdot \log_2(\frac{x_j}{\mu})
= \frac{n_j \cdot x_j}{\mu} \cdot \log_2(\frac{x_j}{\mu})
\) 

Vi ender med at få

\( 
T = \frac{1}{N} \sum_{j=1}^m \frac{n_j \cdot x_j}{\mu} \cdot \log_2(\frac{x_j}{\mu})
  = \sum_{j=1}^m \frac{n_j \cdot x_j}{N \cdot \mu } \cdot \log_2(\frac{x_j}{\mu})
\)

Dermed har vi udledt formlen for Theil-indekset for grupper:

\( 
T = \sum_{j=1}^m \frac{n_j \cdot x_j}{N \cdot \mu } \cdot \log_2(\frac{x_j}{\mu})
\)

Når vi skal sammenligne indkomsterne mellem grupperne, så beregner vi Theil-indekset ved brug af formlen herover. I formlen er \(n_j\) antallet af personer i gruppe j, \(x_j\) er den individuelle indkomst i grupper j, \(\mu\) er den gennemsnitlige indkomst for alle personer, og n er antallet af personer i alt i alle grupper.

Bemærk at \(n_j \cdot x_j\) er den totale indkomst i gruppe j, og \(N \cdot \mu\) er den totale indkomst i befolkningen.

Man kan diskutere det fornuftige i at antage at alle personer i samme gruppe har samme indkomst. Det kan jo være at man har udvalgt sine grupper udfra indkomst-nivaeu, og så er det naturligvis en fornuftig antalelse. Andre gange er det ikke en fornuftig antagelse, og man kan så undersøge/overveje hvilken betydning det så får. Se også ‘dekomposition af Theil-indekset’ hvor man både sammeligner individer og grupper, og finder ud af hvor meget variation i individuelle indkomster betyder for det samlede Theil-indeks, og hvor meget gruppe-variation i indkomster betyder for det samlede Theil-index.

Lad os som eksempel se på data fra nogle amerikanske stater:

Vi vil beregne Alabamas bidrag til Theil-indekset:

\(T_{Alabama} = \frac{3449846}{203798722} \cdot \frac{2978}{4095} \cdot \log_2(\frac{2979}{4095})
  = -0.0057\)

Alabamas bidrag til Theil-indekset bliver negativt da gennemsnitsindkomsten i Alabama ligger under gennemsnitsindkomsten i USA. Alaskas bidrag til Theil-indekset beregnes på samme måde, og man får 0.00068.

For at beregne Theil-indekset for USA skal vi beregne hver af staternes bidrag til Theil-indekset, og så addere dem.

Den ideelle entropi \(H(F)\) for et forsøg \(F\) kan beregnes ved brug af formlen

\(H(F) = -\sum_{i=1}^n p_i \cdot \log_2(p_i) \)

Bemærk at logaritmen er to-tals logaritmen. Sandsynlighederne \(p_i\) er sandsynlighederne for de forskellige udfald.

Formen kan udledes ved bl.a. at se lidt nærmere på optimale spørgsstrategier, men det springer vi over her. Der henvises til Flemming Topsøes bog ‘Informationsteori’, Gyldendal 1973 hvorfra inspiration til gennemgangen af entropien er fundet.

Figurerne herunder viser et punktplot over sandsynligheder for 10 udfald, og en beregnet ideel entropi. Bemærk, at jo større variation der er i sandsynlighederne, jo mindre en entropien. Det skyldes, at når der er udfald med stor sandsynlighed, så skal de, i en optimal spørgestrategi, spørges til først, og mindst sandsynlige udfald skal der spørges til sidst – på den måde skal der stille færrest mulige spørgsmål, og entropien bliver lille.

Theil-indekset kan bruges til at vurdere ulighed.

Antag at vi har n = 10 personer, der tjener følgende antal kr. i timen:

\(x_1 = 100, x_2 =200, x_3=300, x_4=400, x_5=500, .. ,x_{10}= 1000\) 

Lad \(\mu\) være gennemsnittet af indtægterne

\(\mu = \frac{1}{10} \cdot (100+200+300+...+1000) = 550\)

Da bestemmes Theil-indekset ved formlen

\(T = \frac{1}{n} \cdot \sum_{i=1}^{n} \frac{x_i}{\mu} \cdot \log_2(\frac{x_i}{\mu})\)

Ved at indsætte indkomsterne \(x_i\) og gennemsnittet \(\mu\) af indkomsterne, så udregnes Theil-indekset til 0.21829. Her har jeg brugt to-tals-logaritmen \(\log_2(x)\). Det er sådan set lige meget hvilken logaritme man bruger, bare man hele tiden bruger den samme, ellers kan man jo ikke sammenligne resultaterne.

Hvis man skal bestemme Theil-indekset for grupper af personer, f.eks. hvis man skal sammenligne indkomster i forskellige lande, så er det bedst at tilpasse formlen for Theil-indekset. Som den er nu, sammenligner den individer, ikke grupper. Forskellen på individer og grupper er, at grupper varierer i størrelser, det skal der tages hensyn til ved beregning af Theil-indekset.

Formlen for Theil-indekset kommer tydeligvis fra formlen for ideel entropi. Der er dog en omvendt sammenhæng; ens sandsynligheder i formlen for ideel entropi giver stor ideel entropi. Ens indkomster i formlen for Theil-indeks giver et lille Theil-indeks.

Vi skal nu, ud fra formlen for ideel entropi, udlede formlen for Theil-indeks. Formlen for ideel entropi er givet ved

\(H=- \sum_{i=1}^{n} p_i \cdot \log_2(p_i)\)

Jeg vil nu prøve at udlede formlen for Theil-indekset fra formlen for ideel entropi.

Theil-indekset skal være tæt på nul når der er stor lighed. Men stor lighed giver stor ideel entropi. Vi beregner derfor Theil-indekset som forskellen mellem den maksimale ideelle entropi for n data og den ideelle entropi for de n data. Forskellen er dermed tæt på nul ved stor ulighed.

Vi vil nu beregne den maksimale ideelle entropi for n data.

Hvis alle udfald har samme sandsynlighed, så er den ideelle entropi størst. Antag at alle sandsynligheder er ens, dvs. \(p_i=p\) for alle i. Da er

\(
H=- \sum_{i=1}^{n} p_i \cdot \log_2(p_i)
 = - \sum_{i=1}^{n} p \cdot \log_2(p)
\)

Da de n led i summen alle er lige store, og lig \(p \cdot \log_2(p)\), så får vi videre

\(
H =- \sum_{i=1}^{n} p \cdot \log_2(p)
 = -n \cdot p \cdot \log_2(p)
\)

De n sandsynligheder lagt sammen må give 1, dermed er \(p=\frac{1}{n}\).

Da \(n \cdot \frac{1}{n} = 1\) og da \(\log_2(1/n) = -\log_2(n)\), så få vi

\(
H = -n \cdot p \cdot \log_2(p)
 = -n \cdot \frac{1}{n} \cdot \log_2(1/n)
 = -(-\log_2(n))
 = \log_2(n)
\)

Den største ideelle entropi får man altså når alle sandsynligheder er ens, og den maksimale ideelle entropi er i så fald lig \(\log_2(n)\).

Nu er vi klar til beregning af Theil-indekset.

Antag at vi har n personer med indkomsterne \(x_i\). De n personer samler deres indkomster i en kasse, vekslet om til enkroner. Den person som tjener mest, lægger altså flere enkroner i kassen end en person som ikke tjener så meget. Vi tager så en tilfældig enkrone fra kassen. Vi vil finde ud af hvilken af de n personer som var ejer af den enkrone vi har fået fat i. Vi må kun spørge ja/nej spørgsmål, f.eks. ‘Er mønten ejet af person nummer 1?’

Da gennemsnittet \(\mu\) af indkomsterne beregnes ved brug af formlen

\(\mu = \frac{1}{n} \cdot (x_1+x_2+...+x_n)\)

så må \(\mu \cdot n\) være lig summen \(x_1+x_2+…+x_n\) af indkomsternene.

Sandsynligheden for at mønten kommer fra person i er dermed

\(p_i = \frac{x_i}{n \cdot \mu}\) 

Vi tager så formlen for den ideelle entropi, og indsætter sandsynlighgederne \(p_i\) givet ved udtrykket herover. Husk at Theil-indekset beregnes som forskellen mellem den maksimale entropi \(H_{max}\) for n muligheder og den beregnede entropi for de n indkomster.

\( 
T=H_{max}-H 
\)

Vi indsætter udtrykkene for \(T_{max}\) og \(H\):

\( 
T=\log_2(n)-(- \sum_{i=1}^{n} \frac{x_i}{n \cdot \mu} \cdot \log_2(\frac{x_i}{n \cdot \mu}))
= \log_2(n)+ \sum_{i=1}^{n} \frac{x_i}{n \cdot \mu} \cdot \log_2(\frac{x_i}{n \cdot \mu})
\)

Alle led i summen er multipliceret med \(\frac{1}{n}\), så den brøk kan sættes udenfor en parentes:

\( 
T =\log_2(n)+ \frac{1}{n} \sum_{i=1}^{n} \frac{x_i}{\mu} \cdot \log_2(\frac{x_i}{n \cdot \mu})
\)

Brøken i logaritmen kan skrives som et produkt

\(\frac{x_i}{n \cdot \mu}=\frac{x_i}{\mu} \cdot \frac{1}{n}\)

Vi bruger så at logaritmen til et produkt er summen af logaritmerne; \(\log(a \cdot b) = \log(a) + log(b)\).

\( 
T =\log_2(n)+ \frac{1}{n} \sum_{i=1}^{n} \frac{x_i}{\mu} \cdot (\log_2(\frac{x_i}{\mu})+\log_2(\frac{1}{n})) 
\)

Nu bruger vi så at logaritmen til en brøk er lig logaritmen til tælleren minus logaritmen til nævneren

\(\log_2(\frac{1}{n}) = \log_2(1) - \log_2(n) = 0 - \log_2(n) = -\log_2(n) \)

Dermed har vi så:

\( 
T = \log_2(n)+ \frac{1}{n} \sum_{i=1}^{n} \frac{x_i}{\mu} \cdot (\log_2(\frac{x_i}{\mu})-\log_2(n)) 
\)

Nu kan summen deles op i to:

\( 
T = \log_2(n)+ \frac{1}{n} \sum_{i=1}^{n} \frac{x_i}{\mu} \cdot \log_2(\frac{x_i}{\mu})- \frac{1}{n}  \sum_{i=1}^{n} \frac{x_i}{\mu} \cdot \log_2(n)
\)

Lad os se på den sidste sum. Her kan \(\mu\) og \(\log_2(n)\) sættes udenfor summen:

\( 
\frac{1}{n} \sum_{i=1}^{n} \frac{x_i}{\mu} \cdot \log_2(n) 
= \frac{1}{n} \cdot \log_2(n) \cdot \frac{1}{\mu} \cdot \sum_{i=1}^{n} x_i
= \frac{1}{n} \cdot \log_2(n) \cdot \frac{1}{\mu} \cdot \mu \cdot n
= \log_2(n)
\)

Hele sidste del kan altså reduceres til \(\log_2(n)\). Dermed får vi

\( 
T = \log_2(n)+ \frac{1}{n} \sum_{i=1}^{n} \frac{x_i}{\mu} \cdot \log_2(\frac{x_i}{\mu})-\log_2(n)
\)

Nu går \(\log_2(n)\) ud, så vi ender med resultatet

\( 
T = \frac{1}{n} \sum_{i=1}^{n} \frac{x_i}{\mu} \cdot \log_2(\frac{x_i}{\mu})
\)

Hermed har vi ‘udledt’ formlen for Theil-indekset.

Vores fortolkning er, at Theil-indekset er antal ja/nej spørgsmål man skal stille, for at finde ud af hvem der ejer en given krone, målt i forhold til det maksimale antal ja/nej spørgsmål man kan komme ud for at skulle stille i det tilfælde hvor der er total lighed.

Er der total lighed, så skal man stille det maksimale antal ja/nej spørgsmål, den ideelle entropi bliver maksimal, og Theil-indekset bliver lig nul.

Ved stor ulighed, så skal man stille færre spørgsmål end det maksimale antal, og dermed bliver Theil-indekset større.

Graferne herunder viser indkomst for hver person, samt Theil-indekset.

Vi ser, at jo større ulighed, jo større bliver Theil-indekset.

I den sidste figur har person nummer 10 en indkomst på 10000 kr, de andre 9 personer har en indkomst på 100 kr. Nu bliver Theil-indekser 3.22. Den maksimale ideelle entropi bliver tæt på nul, det er jo rimelig klart hvem der ejer den krone man vælger. Da den maksimale ideelle entropi, ved lige indkomst er \(\log_2(10)=3.3219\), så bliver Theil-indekset lige under 3.3219.

Hvis alle indkomster er ens, så bliver den ideelle entropi lig \(\log_2(10)=3.3219\).

Vi så før, at den reelle entropi \(H_0\) var det spørgsmål man i gennemsnit skal stille, for at få klarhed, når man spørger efter den optimale spørgstrategi.

Antag nu at vi trækker et kort fra et kortspil med 52 kort.

Først er vi interesseret i om kuløren er sort, dvs. om kuløren er spar eller klør. Det er klart at det kræver præcis ét ja/nej spørgsmål, så den reelle entropi er 1.

Antag nu at vi er interesseret i, om det er spar es. Vi kan spørge ‘er det spar es?’. Det er et ja/nej spørgsmål. Når vi har fået svar på det spørgsmål, så ved vi om det udtrukne kort var spar es. Igen kræves netop ét ja-nej spørgsmål, så den relle entropi er 1.

Men i hvilken af de to situationer vindes der mest viden? I føste tilfælde er der 50% chance for farven sort. I tilfælde 2 er der 1/52 chance, dvs. lidt under 2%, for at det er spar es.

Hvis man i første situation for at vide at kuløren er sort, så bliver man næppe overrasket, for det er et meget sandsynligt udfald. Hvis man i andet situation får at vide at det udtrukne kort er spar es, så bliver man nok noget overrasket.

Pointen er, at man ikke får ret meget ekstra viden når man får at vide at kortet ikke er spar es, men men får mere viden når man får at vide at kortets kulør er sort.

Den reelle entropi kan altså godt være ens i to forskellige situationer, der nok ikke umiddelbart kan sammenlignes.

Lad os nu se på plat eller krone med en uærlig mønt. Vi er interesseret i om det blev ‘krone’. Lad os antage at sandsynligheden for at få krone er 3/4 = 75%, og sandsynligheden for at få plat er 1/4 = 25%.

Der skal naturligvis bruges ét spørgsmål til at få svar på spørgsmålet; ‘blev det krone?’. Hvis vi gentager forsøget igen, så skal vi igen bruge et spørgsmål for at få svar på om andet kast gav ‘krone’. Gentages forsøget 10 gange, og skal vi hver gang finde ud af om det blev ‘krone’, så skal vi bruge 10 spørgsmål.

Men hvad nu hvis vi ikke spørger efter hver kast, hvad nu hvis vi, efter f.eks. to kast, spørger til det samlede resultat?

Hvis udfaldene skriver f.eks. (P,K) for første kast plat og andet kast krone, så er her de mulige udfald og de tilhørende sandsynligheder:

Udfaldet (P,P) , sandsynlighed = \(\frac{1}{4} \cdot \frac{1}{4} = \frac{1}{16} \)
Udfaldet (P,K) , sandsynlighed = \(\frac{1}{4} \cdot \frac{3}{4} = \frac{3}{16} \)
Udfaldet (K,P) , sandsynlighed = \(\frac{3}{4} \cdot \frac{1}{4} = \frac{3}{16} \)
Udfaldet (K,K) , sandsynlighed = \(\frac{3}{4} \cdot \frac{3}{4} = \frac{9}{16} \)

Spørgestrategi 1 : Vi kan spørge om første kast gav ‘krone’ Hvis ‘ja’, så gav første kast naturligvis ‘krone’, hvis ‘nej’, så gav første kast ‘plat. Nu kan vi spørge om andet kast gav ‘krone’. Det kræver, uanset sandsynlighederne, altid to spørgsmål:

Det er ikke den bedste spørgestrategi, for vi har ikke taget hensyn til at sandsynligheden for ‘krone’ er større end sandsynligheden for ‘plat’.

Spørgestrategi 2 : Vi spørger først om udfaldet (K,K). Hvis ‘ja’ bruger vi et spørgsmål, hvis ‘nej’ spørger vi om (P,K). Hvis ‘ja’ har vi brugt to spørgsmål, hvis ‘nej’ spørger vi om (K,P). Nu kender vi svaret.

Det gennemsnitlige antal spørgsmål er så

\(H_0 = \frac{9}{16} \cdot 1 + \frac{3}{16} \cdot 2 + \frac{3}{16} \cdot 3 + \frac{1}{16} \cdot 3 = 
         \frac{9}{16} + \frac{6}{16} + \frac{9}{16} + \frac{3}{16} = \frac{27}{16} = 1.68 \)

Sandsynlighederne i træet herover kunne også beregnes ved at gange sandsynlighederne fra roden og ud til grenene, det er dog en del mere besværligt, men det virker naturligvis:

Vi ser altså, at vi, ved at udføre forsøget to gange, og så spørge til sidst, kan spørge på en mere fornuftig måde, og ende med at skulle bruge et færre antal spørgsmål, end ved bare at spørge til hvert forsøg for sig.

Ved de to gentagelser skal vi bruge 0.84 spørgsmål pr. forsøg, med spørgestrategi 2.

Hvis vi gentager forsøget endnu en gang, og efterfølgende spørger fornuftigt, så har vi naturligvis brug for flere spørgsmål, men antal spørgsmål pr. forøg bliver nok lidt mindre end de 0.84 spørgsmål pr. forsøg.

Lad os gentage forsøget tre gange. Der er i princippet fire typer udfald, med sandsynligheder:

Udfaldet (K,K,K) , sandsynlighed = \(\frac{3}{4} \cdot \frac{3}{4} \cdot \frac{3}{4}= \frac{27}{64} \)
Udfaldet (K,K,P) , sandsynlighed = \(\frac{3}{4} \cdot \frac{3}{4} \cdot \frac{1}{4} = \frac{9}{64} \)
Udfaldet (K,P,P) , sandsynlighed = \(\frac{3}{4} \cdot \frac{1}{4} \cdot \frac{1}{4} = \frac{3}{64} \)
Udfaldet (P,P,P) , sandsynlighed = \(\frac{1}{4} \cdot \frac{1}{4} \cdot \frac{1}{4}= \frac{1}{64} \)

Vi kan lave et chancetræ ud fra en rimelig spørgestrategi:

Vi kan ud beregne den reelle entropi ud fra denne spørgestrategi:

\(H_0 = \frac{27}{64} \cdot 1 + \frac{9}{64} \cdot 3 + \frac{9}{64} \cdot 3 + \frac{9}{64} \cdot 3 + \frac{3}{64} \cdot 5 + \frac{3}{64} \cdot 5 + \frac{1}{64} \cdot 5 = \frac{79}{32} \cdot 3 = 2.4688 \)

Antal spørgsmål, pr. forsøg, er nu 0.8229. Bemærk dog, at vi ikke ved om vores spørgestrategi er optimal.

Som vi skal se i det efterfølgende, så vil antallet af spørgsmål, pr. forsøg, nærme sig mod en ‘nedre værdi’ jo flere forsøg vi udfører inden vi spørger.

Nu skal vi se på den ideelle entropi \(H\). Lad \(F\) være et forsøg, f.eks. et møntkast. Lad \(F^k\) betegne det forsøg, der består i, at forsøget \(F\) gentages k gange. Vi definere nu

\(H(F) = \lim_{k \rightarrow \infty} (\frac{1}{k} \cdot H_0(F^k))\)

Den ideelle entropi \(H\) er altså den reelle entropi for forsøget \(F^k\), divideret med k, når antallet k af forsøg går mod uendelig.

Sagt på en anden måde; den ideelle entropi er det gennemsnitlige antal spørgsmål man skal stille, pr. forsøg, når man spørger optimalt, når antallet af forsøg går mod uendelig.

Så kan man spørge hvad man skal bruge det til, for det kan man jo ikke bare regne ud. Forsøget herover med tre møntkast med den uærlige mønt var kompliceret nok i sig, selv, hvordan ser det så ikke ud for k = 10 eller k = 1000?

I næste afsnit præsenteres formlen der på en overraskende simpel måde beregner den ideelle entropi.

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/n

Vi 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…