5-11 Arrow of Time

Charlie filosoferede om entropi i starten – man hørte ham i baggrunden. Amita betegnede kommunikationen mellem Larry og Charlie som en test af grænserne for Shannons kildekodningssætning. Charlie brugte Viterbi algoritmer til at forudsige Buck Winters næste træk (noget med skjulte tilstande). Simpleksalgoritmen indgik i en optimering under randbetingelser : Hvor lang tid tager det at lave et godt reb af tandtråd givet mængden af tandtråd i fængslet – eller noget i den retning.

Entropi
Det har været på bloggen her før, og jeg tillader mig at gentage en del af det her; man skal jo ikke genopfinde det varme vand. Entropi kaldes populært for et mål for uorden, og det optræder både i fysik (i termodynamik) og i informationsteori.
Ideen om, hvordan man kan give et mål for mængden af information i f.eks. en besked, der skal sendes over nettet, skyldes Claude Shannon i artiklen A mathematical theory of Communication fra 1948, hvor han bl.a. definerer informationsmængden, entropien. Entropi defineres via sandsynlighedsteori; man skal have et mål for, hvor meget klogere, man er blevet af at få en bestemt information. Vi forudsætter, at man på forhånd har en ide om, hvad der sandsynligvis kunne ske. Er beskeden så, at noget, vi anså for meget usandsynligt, er sket, vil vi anse det for mere information, end hvis vi får vished om, at noget, vi allerede mente var ret sandsynligt, rent faktisk er sket. Er informationen udfaldet af at slå et slag med tre terninger, vil jeg blive mere overrasket over 3 seksere, end over 2 seksere og en treer, fordi det sidste er et mere sandsynligt udfald (der er tre måder, man kan få 2 seksere og en treer svarende til, hvilken terning, der giver en treer). Man vil også blive mere overrasket over at få at vide, at det regnede i San Francisco i juni, end at det regnede i København. Så man måler informationen udfra, hvad man ved om sandsynligheden for de forskellige mulige informationer.
Med formler:

H(X) er entropien af x1,…,xn, hvor sandsynligheden for xi er p(xi). b er grundtallet for den logaritmefunktion, der bruges. Ofte er b=2 – hvis informationen x1,…,xn er 0’er og 1’er. Mere præcist er x1,…,xn er de mulige  udfald af en stokastisk variabel X. Det modellerer kommunikation i den forstand, at man forestiller sig, visse bits (ord eller sætninger skulle det være, men her er det nok nærmere bogstaver) er mere sandsynlige end andre.

H(X) måler en middelværdi af informationsindholdet, I(x). Informationsindholdet i xi er log(1/p(xi)) =-log(p(xi). Informationsindholdet er altså stort, hvis sandsynligheden for xi er lille, – jo mere usandsynlig, xi er, jo mere information er der, når xi rent faktisk sker. Det opvejes så af, at der ganges med p(xi), når man udregner H. Hvis noget er meget usandsynligt, er der megen information i, men det sker jo så heller ikke ret tit.

Eksempel: Hvis alle udfald er lige sandsynlige, så er p(xi)=1/n. Altså er H(X)=log(n) =1, hvis vi bruger logaritmen med grundtal n. Hvis et udfald har sandsynlighed 1 og alle andre aldrig sker, så er H(X)=0. (Hvis p(xi)=0, er reglen, at p(xi)logp(xi)=0, selvom man ikke kan tage logaritmen til 0.). Andre værdier af H(X) ligger imellem 0 og 1 (når man bruger en passende logaritme.)

Et aspekt af informationsteori er at uddrage hvor lidt plads, der skal til for at repræsentere informationen – hvor mange bits eller bogstaver. De bits, der er overflødige er redundante. Hvis vi ved, beskeden handler om N gange plat og krone, hvor mønten er fair, altså sandsynligheden for plat er 1/2, så er vi nødt til at informere om alle udfald. Vi skal bruge NH(X) bits til at lagre informationen, hvor H(X)=1, altså strenglængde N. Shannons kildekodningssætning siger, at det gælder generelt: Hvis man slår N gange med en mønt, hvor plat har sandsynlighed p, altså H(X)=-( p log(p) +(1-p)log(1-p))=-(p log(p/(1-p))+log(1-p)), så kan man give informationen om udfaldet i en streng af længde NH(X) (eller længere naturligvis). -Der indgår en grænseovergang, så det gælder for lange strenge, og sandsynligheden for informationstab falder, jo længere streng, man vil lagre. Og omvendt: Bruger man kortere strenglængde, er man næsten sikker på at miste information.

Et andet aspekt af sagen er, at man faktisk ofte sender overflødig information med: Hvis man skal sende på en “kanal med støj”. Som f.eks. afspille en CD eller sende noget over nettet. Hvis beskeden risikerer at blive ændret lidt undervejs, vil man gerne kunne rekonstruere den. Det kan man f.eks., hvis man har sendt samme besked flere gange, altså sendt overflødig information. Men det kan gøres noget mere intelligent – det er det, kodningsteori beskæftiger sig med. Se f.eks. Olav Geils hjemmeside. Hvor meget ekstra information, der skal med, afhænger af, hvor meget støj, der er på linien. Men siger, at man indkoder – pakker informationen ind- inden afsendelse og dekoder, pakker den ud igen bagefter.

Shannons kanalkodningssætning siger, at uanset hvor støjfyldt en kanal er, så kan man finde måder at sende information over den uden tab af information, eller igen: med meget lille sandsynlighed for tab af information. Og sætningen siger, hvor god en kodning, man kan lave, i.e., hvor meget ekstra information er man nødt til at sende med, hvis der er en given mængde støj (sandsynlighed for fejl) og man kun vil acceptere en vis (lille) maksimal sandsynlighed for fejl i det budskab der når frem. Shannon giver ikke en opskrift på disse optimale kodningsalgoritmer – det er et forskningsområde at finde gode koder. Og at sørge for, at de ikke er for komplicerede i den forstand, at de skal have lav kompleksitet: Man skal ikke bruge rigtig lang tid på at indkode (skrive beskeden om, pakke den ind, inden afsendelse) og dekode (pakke den ud, når den kommer frem), for så kunne man måske lige så godt have sendt en længere streng i stedet for – have brugt en mindre effektiv kode.

Entropi er også et begreb i termodynamik – det får I ikke noget om nu, men måske senere. Det er igen et mål for “uorden”. Eksempelvis er en balje med lunkent vand mere uordentlig end en, hvor man havde koldt vand i og lige har hældt varmt i, som ikke har blandet sig med det kolde endnu. Og her er det klart: Entropien vokser – vandet blander sig og bliver lunkent. Og det er karakteristisk, at man ikke kan gå tilbage og skille hurtige molekyler (varmt vand) fra langsomme. Det er det, de mener med “arrow of time” – det går kun en vej, og det fortæller hvad tidsretningen er.