Numb3rs

Matematikken denne gang var primært krypteringsalgoritmer: Bacons kode, straddling dambræt (to straddle betyder- ifølge Gyldendals røde ordbøger – at skræve, at stritte med benene, at være ubeslutsom, at skyde sig ind på, så vælg selv, hvad I vil oversætte med her…), Merkle Hellman rygsækalgoritme, Musikkoder (?). Og så var der igen en reference til spilteori – “k-level thinking” og kongen, der lovede en kvik undersåt et hvedekorn på første felt i et skakbræt, to på det næste, 4 på det næste etc. Altså 1+2+2^2+2^3+2^4+…+2^63 hvedekorn.

Om hvedekornene:
Det bliver til rigtig mange: Man kan vise, at
1+2+2^2+2^3+2^4+…+2^63 =2^64-1=18.446.744.073.709.551.615

Mere generelt er 1+a+a^2+a^3+…+a^63=(a^64-1)/(a-1) hvilket man kan overbevise sig om ved at gange med a-1 på begge sider. Mange led “spiser hinanden”.
Når a=2 er nævneren på højresiden så 1.

Et andet argument fås ved at gå via totalssystemet for dem, der forstår det:

1+2+2^2+2^3+2^4+…+2^63 er i totalssystemet 111111…1111 (64 cifre) Hvis man lgger 1 til, får man 100000…0000 (65 cifre) altså et 1-tal på pladsen svarende til 2^64.

Charlie sagde i øvrigt et forkert ciffer, – han sagde et nital i stedet for et nul et sted, men det var ikke en pointe – bare en fejl fra Krumholz’ side. Tror jeg da…

Bacons kode
Her er oversættelsen fra bogstaver til tal til A’er og B’er – (det sidste svarer til at skrive talene i totalssystemet, hvis man synes, det er nemmere at forstå).
a = 0 = AAAAA g = 6 = AABBA n = 12 = ABBAA t = 18 = BAABA
b = 1 = AAAAB h = 7 = AABBB o = 13 = ABBAB u,v=19 = BAABB
c = 2 = AAABA ij = 8 = ABAAA p = 14 = ABBBA w = 20 = BABAA
d = 3 = AAABB k = 9 = ABAAB q = 15 = ABBBB x = 21 = BABAB
e = 4 = AABAA l = 10 = ABABA r = 16 = BAAAA y = 22 = BABBA
f = 5 = AABAB m = 11 = ABABB s = 17 = BAAAB z = 23 = BABBB
Bemærk, at der kun er 24 bogstaver – man havde ikke i og j som forskellige bogstaver og tilsvarende med u og v på Bacons tid.
Bacon oversatte så A og B til f.eks. kursiv og ikke-kursiv i en lang tekst. Så kan man skjule sin besked i en tekst, der ser uskyldig ud, bortset fra, at nogen ikke kan bestemme sig til, om de bruger kursiv eller ej. Eller man kan bruge store bogstaver for A og små for B, så HUNdEHOVed betyder AAABAAAABB, som jo er cd i koden ovenfor.

Straddling checkerboard

Igen drejer set sig i første omgang om at oversætte fra bogstaver til tal. Problemet i den slags koder, hvor man oversætter hvert bogstav til et andet symbol – et tal, et andet bogstav eller nogen symboler, man selv har fundet på, er, at man ved, at visse bogstaver optræder hyppigere end andre i sædvanlig tekst. Og så kan man bryde koderne ved frekvensanalyse: e er det bogstav, der forekommer hyppigst på dansk, så man gætter på, at det symbol, der optræder hyppigst i den krypterede tekst, skal oversætte til e. Og så videre. Man kan gøre noget tilsvarende med grupper af symboler og sammenligne med hyppigt forekommende ord i dansk. Det er dog ikke helt simpelt, for hyppigheden af bogstaverne afhænger af typen af tekst – se hos sproget.dk om bogstaver og om ord.

I straddling checkerboard forsøger man at omgå det problem. Jeg tillader mig at antage, at de otte mest hyppige bogstaver på dansk er strandeo (men det afhænger jo altså af, hvilke tekster, man undersøger) Dem skriver jeg ind på 8 af de ti pladser i anden række et 4 gange 10 skakbræt, hvor der i øverste række står 0123…9. Resten af bogstaverne fordeles i felterne nedenfor

Der er to pladser i øverste række, der ikke er fyldt ud, under 2 og under 6. De bruges til at “nummerere” de to sidste rækker.
Skal jeg nu skrive bogstavet a, skriver jeg 3. bogstavet r er 7. Bogstavet f står også under 3, men det skriver jeg 23 – række nummer 2, plads 3. Og for b skrives 62 for rækken nummer 6 og plads 2.

28229620825 kan nu brydes, nar jeg har mit skakbræt: Den starter med et 2-tal, så det må være et rækkenummer. Altså er første bogstav 28 svarende til L det næste er 22, altså I, så er 9 bogstavet S, 6 må være et rækkenummer, så vi skal finde bogstavet 62, altså B etc. (der står LISBETH.) Man kan kryptere yderligere ved at tage de talfølgen og bruge en anden algoritme på den. Man kan også lade tallene i første række fremkomme ved en indviklet metode etc.
Metoden har været brugt som en del af kryptering af mindst en spion for Sovjet Unionen, Reino Häihänen

Merkle Hellman rygsæk
Merkle Hellman kryptering refererer til et Public Key System, hvor man kan offentliggøre den måde, man skal kryptere på (en offentlig nøgle), så folk kan skrive hemmelige beskeder til en. Men uden at de derved selv kan dekryptere – altså læse beskeder skrevet med den kryptering. Metoden ovenfor er ikke af den type – har man tabellen til kryptering, kan man også dekryptere.

Et rygsækproblem handler om at fylde en rygsæk optimalt – i.e. at løse et optimeringsproblem under visse bibetingelser: Hvis vi har visse værdier på det, vi kan vælge at proppe i rygsækken (eller bilens bagagerum), hvad skal vi så tage med, når vi ikke kan have plads til det hele.

I kryptering er problemerne af typen:
Man har en stribe hele tal. 1,5,7,13,22 for eksempel.
Nu kan vi kryptere beskeder med 5 cifre i totalssystemet ved at lade 1 betyde “skal med” 0 “skal ikke med”, så 10110 giver 1+7+13= 21 fordi 1 skal med, 5 skal ikke med, 7 skal med, 13 skal med og 22 skal ikke med.
Dekrypteringen består nu i at skrive 22 som en sum af nogen af tallene 1,5,7,13,22.
Det er et “subset-sum” problem, og de er NP-fuldstændige, altså meget tidkrævende på en computer. (Den tid, der skal bruges, vokser meget hurtigt som funktion af, hvor stor en mængde tal, vi har som udgangspunkt.) Problemet er selvfølgelig, at det så vil være vanskeligt for den rigtige modtager at dekryptere beskeden, og det var jo ikke meningen.
I midlertid er der visse af den type “subset-sum” problemer, som er lettere at løse, nemlig dem, hvor rækken af tal, vi går ud fra, opfylder, at hvert tal er større end summen af de foregående. (Tænk over det. Hvis det tal, vi skal skrive som en sum, er større end det sidste tal, skal det sidste tal være med – ellers skal det ikke være med. Skal det med, trækker vi det fra. Nu ser vi på, om det næstsidste tal skal med etc.) det er et let rygsækproblem

I Merkle Hellmann var det i virkeligheden et let rygsækproblem, der blev brugt. Man tog en stribe tal, a1,a2,a3,a4,… som kunne bruges i et let problem. Så tog man et stort tal N,større end summen af a’erne, et tal k, som er primisk med N (deres største fælles divisor er 1) og udregnede for alle a’erne resten af ra ved division med N. Den stribe tal offentliggøres, og det ligner nu et svært rygsækproblem. For at dekryptere kan man oversætte til det lette problem ved passende algebra – læs mere her eller mange andre steder på nettet.
Merkle Hellmann kan imidlertid brydes i polynomiel tid, og det er jo skidt, så det bruges ikke mere. Det viste Adi Shamir i 1982. I øvrigt er Shamir den ene af de tre, der lavede RSA (Rivest, Adleman og Shamir), som har overlevet som public keysystem.

Charlie brugte Dijkstras algoritme til at finde korteste vej. Han snakkede om Frank – Wolfe algoritmen til at finde ligevægt i transportnetværk og han foreslog Don at bruge det gamle logiske trick med at finde ud af, hvem der lyver, ved at lade dem udtale sig om hinanden. Der var også noget om “Vulture funds”. Det kan man læse om her, hvor præcis de data, der optræder i Numb3rs, er nævnt: Et firma køber dele af Zambias statsgæld til hugpris på et tidspunkt, hvor Zambia får eftergivet en del gæld til udlandet (firmaet giver 3,3 millioner dollars – gælden var oprindelig 15 millioner dollars, som Zambia skyldte Rumænien). Firmaet sagsøger derefter Zambia for 55 millioner dollars, som er gælden plus renter. Men det er vist ikke matematik, bortset fra rentesregningen…

Dijkstras algoritme.
Der er mange problemer, der kan formuleres som “korteste vej” problemer. Et helt oplagt eksempel er det, man f.eks. får løst i krak.dk eller andre ruteplanlægningsprogrammer. Man skal finde en effektiv vej fra A til Å, og man kender en masse mellemliggende stykker: fra A til K, fra K til M, fra K til U,…
Man ved, hvor lange, de mellemliggende stykker er, enten i tid – hvis jeg vil finde den hurtigste rute, eller i egentlig længde i km, hvis det er den korteste rute, jeg vil have. Her er et eksempel på dele af ruter tegnet ind mellem byerne a,b,c,d,e og f. Det er en graf med retning, der er pile på kanterne.

Man kan beskrive Dijkstra’s algoritme generelt, men lad mig nøjes med at give eksemplet. det generelle kan I Google jer til. Eller kig f.eks. i wikipedia. Man kan også nogenlunde regne det overordnede princip ud udfra eksemplet.
Mit udgangspunkt er a, og jeg vil gerne finde kortest afstand fra a til de andre byer. Dijkstras algoritme siger:
1. Kortest afstand til a er 0.
2. Gå til de byer, hvortil man kan komme med en kant fra a. (Det er b og c) Skriv den kortest kendte afstand til a, b og c indtil videre (0 til a, 25 til b og 76 til c). b er den by, der er tættest på a, og vi finder ikke en kortere vej til b, så nu kender vi kortest afstand til a og til b.
3. Gå til de byer, der kan nås med en kant længere fra b (den, der var tættest på a)  (Nu får vi to ruter til c, en til d og en til e.) Skriv de nye korteste afstande ind – bemærk, at vi bruger de afstande, vi har fundet i første skridt. Nu ser grafen sådan ud:

i mere avanceret grafik skulle b, som var tættest på i første step, males gul og pilen a til b, som er den korteste vej dertil skulle også males gul. Man maler desuden d gul nu, fordi den er tættest på a via b, og der kan ikke opstå kortere veje senere (overvej det – nye veje til d vil gå via nogen af de stumper, vi har fundet, og de er længere end den vej, vi har fundet til d via b). Og pilen fra b til d skal være gul.

I næste skridt bliver afstanden til e ændret til 80, fordi vejen a til b til d til e er 80 lang. Nu er der afstand 65 til c og 80 til e, så vi maler c gul, maler pilen fra b til c gul og ser på pile fra c. Det giver en pil til f, som så har afstand 65+80= 145 til a.

I sidste skridt er e nærmest, mal den gul, mal pilen fra d til e gul. Udregn afstand til f via e til 80 + 40=120. Det er mindre end før, så vi maler f gul, maler pilen fra e til f gul.

Vejen fra a til f bliver så fra a til b til d til e til f. Man skal følge de gule pile. Der kan godt være mere end en mulighed for den korteste vej, men det er der ikke i dette eksempel.

Jeg har lavet de “gule” pile lidt fede, men det er ikke let at se. Alle pile, undtagen de tre, der går skråt ned mod højre, er gule..:

Man kan lege med en java applet på denne side. Man kan selv lave sig grafer, men man kan også vælge knappen eksempel, hvor der allerede er lavet en graf.

Ligevægt i trafikflowproblemer. Frank-Wolfe
Charlie og hans far snakker om Frank-Wolfe algoritmen til at bestemme ligevægte i trafikflow.
Trafikflow ligevægtsproblemet drejer sig om at forudsige trafikken alle steder i et netværk, hvis man ved, hvor mange, der skal bevæge sig mellem hvert par af punkter. I grafen ovenfor ved man måske, at 100 personer tager fra a til f, 150 fra b til f etc. Nu vil trafikken, altså afstandsmålene i grafen afhænge af, hvor mange andre, der er på vejen, og så er den mest fordelagtige vej for de sidste , der tager afsted fra a, måske ikke den samme, som for de første. Frank-Wolfe algoritmen løser bestemte optimeringsproblemer (kvadratiske, nærmere bestemt), og den bruges i bl.a. trafiknetværksanalyse.

Jeg har aftalt med mine kolleger i Esbjerg, at I får et indlæg fra dem om analyse af netværk. I mellemtiden kan I se på dette fra tidligere på bloggen. Der skriver jeg lidt om netværk og hvad man kan kigge på i den forbindelse.
Hilsner
Lisbeth.

Jeg holder efterårsferie i den kommende uge, så I må vente med at få udredet matematikken i afsnit 3-22. Det er noget med terrornetværk, et emne, der bl.a. forskes i ved Aalborg Universitets afdeling i Esbjerg. Området er datamining – læs mere hos Nasrullah Memon, Henrik Legind Larsen
eller David Hicks. De har bl.a. skrevet en artikel, der hedder “Detecting hidden Hierarchy in Terrorist Networks”
Jeg vil forsøge at få et indlæg fra deres gruppe.
God ferie
Lisbeth.

Jeg lagde mærke til en “vulnerability analysis” – en sårbarhedsanalyse – af fængslet. En del spilteori: Tit for Tat og Grim trigger strategier. Og der var en del med løgnedetektorer, men dem er der nu ikke noget videnskab, endsige matematik i, så vidt jeg har forstået. Der får I noget om, hvordan man vurderer en test generelt – for sygdom eller løgn – ideen er den samme.
Emnerne nedenfor er altså Sårbarhedsanalyse, Tit for Tat og Løgnedetektorer, herunder generelt vurdering af test for løgn, sygdom eller andet.
Sårbarhedsanalyse:

Det dækker over mange områder: Sårbarhed af computernetværk overfor f.eks. hacking, sårbarhed af fødevaresikkerhed i forskellige områder (se World Food Program), miljøets sårbarhed etc. F.eks. har NSA (det amerikanske National security agency) en Vulnerability analysis and operations group.
Et vigtigt område er sammenligning af sårbarhed: Hvis der er fejl mange steder i systemet, hvilken er så mest kritisk. Man har typisk ikke ressourcer til at lukke alle huller, og derfor skal problemerne prioriteres. Man skal altså have et mål for sårbarhed, en metrik. Det involverer mål for, hvad konsekvenserne af en fejl er og hvor dyrt det er at undgå den.
Charlie regnede på fængselssystemet, men jeg kunne nu ikke se, hvordan han gjorde det.
Beredskabsstyrelsen har et værktøj til risiko og sårbarhedsanalyse hvor man bliver guidet gennem en sådan vurdering. Målgruppen er organisationer, der varetager kritiske opgaver for staten – vandforsyning, energi, hospitaler,… der er en liste over diverse trusler fra isvinter til terrorangreb, som man kan tage udgangspunkt i og vurdere, hvilken indflydelse de kan have. Altså hvor galt kunne det gå og hvor sandsynligt er det, at det går så galt. hvis det er meget sandsynlig og det vil være meget skidt: dyrt, mange syge,… skal man bruge mange ressourcer på at undgå det. Er det meget sandsynligt, men konsekvenserne små skal man måske ikke anstrenge sig for at undgå det.

Tit for Tat og andre strategier
Det handler om strategier i situstioner, hvor mennesker påvirker hinanden og hvor der er flere udvekslinger mellem dem. Skal man samarbejde med den anden eller ej? Tit for tat strategien siger, at man skal samarbejde i første omgang og derefter følge den andens strategi, altså gengælde.
Rammen er en slags “fangernes dilemma”, som vi havde på bloggen under Beskidt bombe og mere generelt er det spilteori.

Fangernes dilemma er følgende:
To forbrydere afhøres hver for sig om en forbrydelse, de har været fælles om. Og der er gevinst ved at sladre om den anden.
Man laver en udbyttematrix

Det, der står øverst i det, der ligner brøker, er udbyttet for fange 1 og nederst (i “nævneren”) står udbyttet for fange 2. For eksempel får fange 1 en straf på 11 år, hvis han holder mund og den anden sladrer. Hvorimod fange 2 i den situation går fri. Hvis begge holder mund, slipper de med 1 år. Man kan altså alt i alt få mere ud af at samarbejde/stole på hinanden. Men for fange 1 vil det, hvis den anden sladrer, bedst kunne betale sig at sladre. Og hvis den anden holder mund vil det igen kunne betale sig at sladre. Og tilsvarende for fange 2. Man kunne også forestille sig to lande, som har handelsbarrierer. Hvis begge opretholder dem er det skadeligt for begge, men hvis den ene fjerner sine og den anden beholder dem, taber den, der har fjernet barriererne.

I Tit for tat forestiller man sig en tilsvarende udbyttematrice, men nu “spiller” vi flere gange. Man ved altså, om modparten samarbejdede (her, holder mund) sidst eller ej. Tit for Tat siger, at man skal gøre det, modparten gjorde sidst. Og at man skal samarbejde første gang. Det handler om at opbygge tillid. Ved man, at man skal “samspille” flere gange, betaler det sig at investere for at opbygge tillid. Se f.eks. Statens Byggeforskningsinstitut for en diskussion af problemerne i, at det er forskellige partnere, der indgår i forskellige byggerier, så man ikke opnår en samarbejdsrelation.
Hvis man her starter med, at en holder mund og den anden sladrer, vil tit for tat fra begge spillere føre til, at man skiftes til at holde mund og sladre. Hvis begge fra starten er samarbejdsvillige, vil man have situationen i nederste højre hjørne konstant.
For at nå ud af en “dødsspiral”, som Charlie beskriver det (en grim trigger strategy), hvor man er i øverste venstre hjørne og bliver der, kan man bruge en tilgivende tit for tat, hvor den ene ind imellem (med en vis sandsynlighed) vil samarbejde, selvom den anden ikke gjorde det i forrige spil. Det vil bringe situationen ud af dødsspiralen og ned, hvor man skifter mellem øverst til højre og nederst til venstre. Og derefter ned i nederste højre hjørne.
Charlie foreslår tit for two tats, hvor man samarbejder indtil modparten to gange i træk ikke har samarbejdet. Så gengælder man.

Strategierne er afprøvet i simulationer, hvor tit for tat vinder, i den forstand, at det giver det største samlede udbytte. Man kan altså individuelt have gavn af en samarbejdsstrategi på længere sigt. Der er, så vidt jeg ved, ikke noget bevis for, at tit for tat er optimal (under nogen forudsætninger formodentlig).

Manden bag tit for tat strategien er Robert Axelrod. Læs mere her. Han bruger strategien til at forklare, hvordan biologiske systemer kan se ud til at “samarbejde”, hvor det måske er en genetisk disposition for tit for tat.

Løgnedetektorer
Der bruges en “polygraph”, som vi kender dem fra amerikanske film og nu også fra et TV3 program. Og senere laves der en “Functional MRI”. Og ingen af dem giver “det rigtige”. Forbryderen tilstår at have slået et barn ihjel, og det har han ikke. Men han har bildt sig selv ind, at han har…
Jamen virker det da ikke? Nej, det ser bestemt ikke ud til. I bogen The Lie behind the Lie detector er en lang udredning om problemerne ved løgnedetektorer. Man kunne ellers forestille sig at man ret let kunne lave kontrollerede forsøg, eller undersøge noget af alt det data, man har fra allerede udførte løgnedetektioner, og det har man  også gjort, men det giver ikke gode resultater. Problemet er bl.a., at de fysiologiske reaktioner, man måler, også kan komme fra andet, end at man lyver. Og det er meget vanskeligt at skille ad. En uskyldig, som er mistænkt for noget virkelig forfærdeligt vil være nervøs og muligvis fremstå løgnagtig. Især hvis den, der tester, tror, vedkommende er skyldig. Og så er vi jo et stykke væk fra noget objektivt. Se også The polygraph and lie detection.
Et andet problem er, at forskellige personer fortolker et løgnedetektorudkrift forskelligt – i en Nature artikel fra 1984 tog man 207 udskrifter fra løgnedetektorer i en stribe senere opklarede sager og fik dem analyseret af 14 andre løgnedetektoreksperter. Det gav dom til 43 % af de uskyldige og frikendelse til 36 % af de skyldige…

Hvordan ved man, om en test er god? En test for en sygdom skal jo finde de syge, men helst ikke udpege for mange raske som værende syge. Lad os sige, man har en positiv test, hvis den viser, man er syg.

Der er set antal falsk positive FP (raske, som tester positivt)

Et antal falsk negative FN (syge med en negativ test)

Et antal sandt positive SP( De syge med positiv test)

Og et antal sandt negative SN (raske med negativ test)

Specificitet er SN/(SN+FP), andelen af de raske, som tester negativt P(testrask|rask). Sensitiviteten er SP/(SP+FN), andelen af syge, der tester positivt P(testsyg|syg).

Den positivt prædiktive værdi er SP/(SP+FP), andelen af positivt testede, som rent faktisk er syge, sandsynligheden for at være syg, når testen viser, man er det, P(syg|testsyg). Eller, man kan se på den negativt prædiktive værdi SN/(SN+FN) andelen af negativt testede, der rent faktisk er raske P(rask|testrask). De prædiktive værdier afhænger af, hvor stor en andel af de testede, der er syge, prævalensen. Og ikke kun af sensitivitet og specificitet.

Eksempel: En test har sensitivitet 0,86 og specificitet 0,92

På et hospital henvises folk, som mistænkes for at have  sygdommen, til test. På et andet er det en test, der laves på alle.

På det første er 37 ud af 49 patienter syge. (Prævalensen er 37/49=0,76)

SP=32, SN=11, FP=1, FN=5.

Specificitet SN/(SN+FP)=11/12=0,92

Sensitivitet SP/(SP+FN)=32/37=0,86

Positiv prædiktiv værdi SP/(SP+FP)=32/33=0,97

Negativ prædiktiv værdi SN/(SN+FN)=11/16=0,69

På det andet er 37 ud af 157 syge. Prævalens 0,24

SP=32, SN=110, FP=10,  FN=5,

Specificitet SN/(SN+FP)=110/120=0,92

Sensitivitet SP/(SP+FN)=32/37=0,86

Positiv prædiktiv værdi SP/(SP+FP)=32/42=0,76

Negativ prædiktiv værdi SN/(SN+FN)=110/115=0,96

Hvis man tester en stor befolkningsgruppe med få syge, vil den negative prædiktive værdi være stor, i.e., hvis man tester negativt, er man med stor sandsynlighed rask. Men dem, der tester positivt vil i mange tilfælde være raske, i.e., sandsynligheden for at være syg givet testen viser syg, er lille. (Tallene er fra How sensitive is sensitivity, how specific is specificity, Phillips, Scott og Blasczcynski, American Journal of Roentgenology. Prøv selv at regne på, hvod der sker, hvis der er 37 syge ud af 12037. Så bliver positiv prædiktiv værdi 0.03 og negativ prædiktiv værdi 0,99. Der er altså rigtig mange blandt dem, der teseter positivt, som alligevel er raske – her 97 ud af 100. Det er det, man skal overveje, når man laver store screeninger for sygdomme.

For løgnedetektorer: Lad os nu antage, at de kan finde løgnere med en vis sandsynlighed (det kan de ikke, men alligevel…). Tester man alle, der ansøger om job i FBI, CIA,… og det gør man…vil dem, der ser ud til at lyve, stadig med ret stor sandsynlighed tale sandt. I.e., mange får et stempel som spion, uden at være det. Dem, der udses som ikke værende spioner, er det med ret stor sandsynlighed ikke, men det er mere fordi, der er rigtig mange, der ikke er spioner, end fordi man er god til at finde spioner. Der vil jo stadig være en enkelt spion der slipper ind nu og da.

Vi kan være glade for, at vi ikke bruger metoden i Danmark! I hvert fald kun til pjattede TV-programmer. Så fans af Doctor Phil eller Sandhedens time eller andre populære brugere af løgnedetektorer bør tage det med et gran salt.

Se også Illustreret videnskab.

Se også Weekendavisen, hvor den funktionelle MRI også afvises som anvendelig. Man kan efter sigende snyde den ved at tælle tilbage fra 20, da det giver aktivitet i hjernen, som gør, at man ikke kan bruge MRI billederne.

Jeg må have haft hovedet under armen, da jeg så dette igennem i torsdags. For jeg glemte at trykke på “udgiv”, men bedre sent end aldrig. Og nu er det snart tid til endnu et afsnit…

Charlie brugte geografisk profilering.Han henviste til Feynmanns foredrag fra 1959, hvor han forudser nanoteknologiudviklingen. Der var noget om paradigmeskift, om koherente tilstande for et kvantemekanisk system, om Misznay Schardin effekten og noget om “Risk award analysis” som vel må være en slags cost-benefit analyse.

Geografisk profilering

Det værktøj så vi første gang i den allerførste Numb3rs udsendelse. Her er en oversigt over diverse links vedrørende geografisk profilering. Kort fortalt udnytter man, at man udfra forbryderens bopæl kan sige noget om sandsynlige gerningssteder – her var det sandsynlige steder, han ville købe materialer og sende brevbomber fra. Den viden skal man have “vendt om”, så man kan slutte fra gerningssteder til, hvor forbryderen sandsynligvis bor. Det er altså et inverst problem. Matematikken bag er en avanceret udgave ef Bayes’ formel fra sandsynlighedsteori. Det er den, man bruger til at udregne sandsynligheden for, at A sker, givet, B er sket. Når man kender den omvendte sandsynlighed.

Misznay Schardin effekten
Man kan få effekten af en eksplosion til at gå i en bestemt retning, altså sørge for, at det, der slynges ud ved eksplosionen, ryger i en bestemt retning. Retningen er vinkelret ud fra overfladen af det, der eksploderer. Navnet Misznay Schardin refererer til to personer, Misznay var ungarer, Hubert Schardin var tysk. Schardin ønskede at udvikle en effektiv antitank mine for Nazi-tyskland. Misznay var ifølge mine oplysninger – via googling – formentlig dobbeltagent – og Schardin ville have hans hjælp til projektet. De var begge to fysikere. Anden verdenskrig sluttede, før de blev færdige. Men man ser effekten, som de har lagt navn til, hver dag i aviserne.
Eller, mere fredeligt, i Mythbusters.
Man kan regne baglæns fra, hvor man finder bomberester til, hvor bomben har været og hvad facon, den har haft. Det er formentlig et spørgsmål om rumlige trekanter – noget intelligent brug af sinus og cosinus.

Richard Feynmann 1959
Her kan man læse Richard Feynmanns foredrag “Plenty of room at the bottom”. Han udfordrer især studerende til at lave meget små maskiner og til at skrive en bogside på et knappenålshoved. Og han diskuterer muligheden for at have mikroskoper, der kan “se” ting på meget mindre skala, end man kunne på det dispunkt. Man kan sige, han forudser nanoteknologien. Se også denne artikel (på dansk) fra 2004 om nanoteknologi.

Richard Feynmann (1918-1988) er legendarisk og nævnes ofte i Numb3rs. Han var fysiker og professor på Caltech, hvor Numb3rs indslag fra det fiktive calSci optages.
Feynmann arbejdede som meget ung fysiker på Manhattan projektet, hvor også Niels Bohr arbejdede. Med at udvikle atombomben. Hans bidrag var ikke stort – han var meget ung, men blev dog placeret ganske højt i hierarkiet i betragtning af sin alder. Der er mange anekdoter om ham – læs f.eks. Wikipedias artikel om ham. Eller læs “Surely you’re joking, Mr. Feynmann”, hans selvbiografi. Eller en af de mange andre bøger, han har skrevet.
Han var en yderst farverig person – malede og spillede trommer, drak, røg hash og meget mere. Det siges, at Niels Bohr gerne diskuterede fysik med Feynmann, fordi han, i modsætning til mange andre, ikke lod sig dupere af den berømte Bohr, men sagde, hvad han mente.

Feynmann var en fantastisk formidler. Han mente, at et fysikbegreb ikke var forstået ordentligt, hvis ikke man kunne forklare det for første års studerende – så jeg har nok ikke nogen god undskyldning hvis I ikke kan forst, hvad jeg skriver på bloggen… Man siger nu, at de førsteårsstuderende ikke forstod så meget. Men hans forelæsninger var meget populære hos kolleger og ældre studerende.
Hans bidrag til fysik var omfattende, og også matematik er påvirket af Feynmann. Det er ikke usædvanligt, at et område i fysik i en vis forstand anvender matematiske metoder, før matematikken er helt på plads – man kan sige, fysikerne kan regne ting ud, som ikke helt giver mening, men eftersom det giver, hvad det skal på fysiksiden, er det jo matematik, der halter efter. Og så må matematikerne på arbejde.

Feynmann fik sat matematikerne igang med en større opgave med de såkaldte “path integrals”.
I klassisk mekanik er der to tilgange til de klassiske bevægelseslove, Hamiltonsk formalisme og Lagrangeformalisme. fra et matematik synspunkt giver hamiltonsk formalisme anledning til to første ordens differentialligninger,

Lagrange formalismen giver en anden ordens differentialligning, som i den simple udgave svarer til Newtons anden lov.

Feynmanns “path integral” formulering er en formulering af kvantemekanik i noget, der svarer til Lagrangeformalismen.

Hvor er matematikproblemerne så? Jo, Feynmann har brug for at integrere. Integraler findes, som jeg skrev om sidst, i mange versioner. De handler om at “summere” eller rettere lave en slags grænseværdi over nogen summer, der får flere og flere led, hvor hvert led bliver mindre og mindre.

Feynmanns formalisme skal bruge funktional integraler. Man har et funktional: en opskrift på at få et tal ud, når man har en funktion – det kunne være kurvelængde, hvis funktionerne er kurver – eller man kunne integrere hver funktion og få et tal. Kort sagt, et funktional tager en funktion ind og giver et tal ud.

Nu har man rigtig mange funktioner – for eksempel alle kurver fra et punkt a til et punkt b – og vil integrere sit funktional. Så er kunsten at få det til at give mening. Hvad skal man lægge sammen.Hvad er det for en “inddeling, der bliver finere og finere”, når det er mængden af funktioner, man skal dele ind? Funktionsrum er sædvanligvis uendeligt dimensionale. Og så bliver men jo lidt svimmel, hvis man ikke er vant til den slags.

Det er et højaktivt forskningsområde, og man kan stadig ikke give mening til “path integrals” i alle situationer. Men med passende styr på, hvad der skal integreres og hvilket rum, kurverne løber i, kan det gives mening. Ito Stratonovich integraler, som jeg skrev om i sidste uge, er eksempler på sådanne integraler. Hvor man integrerer over alle brownske bevægelser.

På Wikipedia er der lange velskrevne artikler om “path integrals”, Path integral formulation, Richard Feynmann, Lagrangian Mechanics, Classical Mechanics og meget mere, for dem, der kan læse engelsk og er interesserede i at vide mere.

Vi måtte undvære Charlie i går. Men der er håb: Onsdag 1.oktober sendes afsnittet Burn Rate. Og der er jo også genudsendelser ugen igennem.

Og så er der vel også nogen, der synes, det er fint med noget fodbold…

Der var temmelig heftig matematik med denne gang:

Ito Stratonovich driftintegraler (Analyse af flystyrtet)

Heterogen Poisson proces (Charlies analyse af indbruddet)

Wavelet baseret dekonvolutionsalgoritme (slørede fingeraftryk rekonstrueret)

Strange Loop theory (ledte tilbage til det skumle programs forfatter)

Wavelet baseret dekonvolutionsalgoritme
Sådan en har vi set tidligere i Numb3rs. Man har et billede, der er tværet lidt ud – f.eks. ved, at man har det i en lav opløsning – få pixels, eller ved, som i dette Numb3rs afsnit, at nogen har gnedet et fingeraftryk lidt ud. Kan man få flere pixels med, altså rekonstruere det rigtige billede?
Det kan man faktisk gøre forbavsende effektivt. Ideen er som følger: Det udtværede billede er fremkommet ved, at man tager en slags middelværdi – et grovkornet billede har en større ensfarvet grå firkant i stedet for de 4 underliggende mørkegrå og lysegrå.
Der er altså en sammenhæng mellem det fine billede og det grove ved at “midle”. Så man skal “midle tilbage igen”.
Det kan man ikke umiddelbart gøre. Det er et “ill posed” problem. Der er flere muligheder for, hvordan billedet kunne have set ud, inden midlingen. Men der findes metoder til “udfoldning, dekonvolution”. En af dem involverer at beskrive billedet ved brug af wavelets, som Kenneth har beskrevet under “Provenance”, og Arne Jensen har skrevet om det til bloggen her. Det grovere billede betragtes som en wavelet beskrivelse, hvor der mangler noget af den finere information – og pointen er, at hierarkiet i wavelets ikke er som i beskrivelsen med en pixel ad gangen, hvor en underdeling i flere pixels blot giver flere ensfarvede pixels til erstatning for en pixel. Wavelets er en bedre tilgang til at “midle tilbage igen”.
I det sidste link finder man et 32×32 pixel billede af Lincoln, som ved hjælp af wavelets forfines til et 128×128. Det er uhyre overbevisende!

“Ito Stratonovich drift integrals”
Ito og stratonovich er to matematikere, og der refereres til to forskellige tilgange til integraler, vel at mærke af stokastiske differentialligninger. Det er overordentlig langhåret matematik, som bl.a. bruges i matematiske finansiering. Når man har en ide om, hvordan noget udvikler sig, og denne beskrivelse involverer noget “støj” – som man kan beskrive ved sandsynligheder. Det er den slags beregninger, der åbenbart indgår i at beskrive, hvordan vragdelene spredes efter et flystyrt.

Der findes også forskellige integraler af funktioner uden stokastiske bidrag.

I gymnasiet møder man mest integralet som areal under en graf. Eller som en stamfunktion evalueret i endepunkterne. Det er Riemann integralet, der ligger til grund for den tilgang. Men der findes andre integraler, som kan håndtere en større klasse af funktioner. Lebesgue integralet er den bedst kendte generalisering.
Man kan tænke på Riemann integralet som en approksimation til arealet under kurven med smallere og smallere rektangler på højkant, i.e., man inddeler mere og mere langs x-aksen. Lebesgue integralet er “på den anden led” – rektangler på langs, så inddelingen langs y-aksen forfines mere og mere.

På billedet man se hvordan – det er Riemann for oven og Lebesgue for neden. I Riemann integralet forlanger man, at det samlede areal af de kasser, der “stikker ovenfor”, nærmer sig det samlede areal af de kasser, der stikker nedenfor, når inddelingen bliver fin nok. Hvis funktionen hopper i et punkt – så f(x)= 2x bortset fra f(2), som er 17 – bliver det tilsvarende areal i begge tilfælde det samme, som hvis den ikke hoppede. Men en funktion, der hopper rigtig tit, som funtionen, der er 1 for alle rationale tal og 0 ellers, er ikke Riemann integrabel. Den er Lebesgue integrabel og integralet giver 0.

Strange Loops

Mærkelige løkker… Her bliver jeg helt nostalgisk. For mange år siden, da blogskribenten var noget yngre, udkom bogen “Gödel Escher Bach, an eternal golden braid.” af Douglas Hofstadter. Den blev en slags kult. Og man burde læse den. Jeg købte den, men kom med skam at melde aldrig igennem den. Det er derfra, ideen om strange loops stammer. Et strange loop er en bevægelse “opad” og “rundt”, hvor man ender, hvor man startede. Som i den Escher tegning, Charlie viste. Andre eksempler findes i musik, hvor man f.eks. hos Bach kan modulere opad i toneskalaen, men alligevel ende tilbage, fordi man ender ved sammen grundtone. Man kan høre et eksempel her på wikipedia

Hofstadter har mange referencer – det er en lang bog, og jeg har den stadig – i matematik er strange loops bl.a. den slags paradokser, der opstår ved selvreferencer:

Manden, der siger “jeg lyver”.

Grellings paradoks: Kald et ord heteorologisk, hvis det ikke beskriver sig selv. Er ordet “heteorologisk” så heteorologisk?

Russels paradoks: Lad M være mængden af mængder, der ikke tilhører sig selv. Er M da et element i M?

Eller Halfdan Rasmussens løsning af barber-paradokset (Barberen barberer alle dem, der ikke barberer sig selv. Hvem barberer så barberen?)

Øen i søen har kun en barber

Til gengæld så klipper han alt hvad han ser.

Han klipper sin fætter, sin hund og sit får

Han klipper billetter, når færgerne går

Han klipper sin plæne, sin hæk og sit hegn

Men selv er han skaldet som Roskildevej’n

Charlie påstår, at man kan finde en ophavsmand til et virusagtigt program ved at følge et strange loop. Det ved jeg ikke, om han har ret i, men dataloger er velkomne til at bidrage! I dette tilfælde skulle programmet jo aktiveres udefra, så måske opstår der en slags loops i den forbindelse.

Der er masser af referencer til strange loops på nettet. Det er vist stadig kult. Imponerende, når man tænker på, bogen er fra 1979.

Plottet drejede sig om fusk med den computerbaserede stemmeafgivning i dels Californien og dels hele USA.
Om der kan svindles med den slags, afhænger selvfølgelig af, hvem der har adgang til maskinerne, hvordan sikkerheden er omkring stemmeafgivningen, hvilke check, der laves af maskinerne, og hvem der laver dem etc.

Charlie bidrog med

En udregning af sandsynligheden for, at de 4 dødsfald blandt Rachels 25 kolleger var en tilfældighed.
Noget organisationsteori brugt på den kriminelle organisation bag fusk med stemmerne.
En analyse af data på det “Flash drive”, der var i Rachels ur.

Og så var der forøvrigt en morsom oversættelse på den DVD, jeg har. Algorithm var blevet til algorytme – shake it baby…

Sandsynligheden for, at dødsfaldene var tilfældige.
Charlie påstod, at sandsynligheden for, at det var tilfældigt, at 4 ud af de 25 personer døde indenfor 2 uger, var 1:10 millioner.
Don siger noget om forudsætningerne – det var 25-45 årige, men ikke alt er med i den endelige sammenklipning, så jeg gætter lidt.
Man skal vide, hvor mange, der gennemsnitligt dør indenfor den aldersgruppe i løbet af de to uger. Den slags data findes for USA her. Tallene siger, hvor mange ud af 100000, der dør i løbet af et år. Hvis man antager (og det er forkert), at dødsraten ikke afhænger af, hvornår på året, det er, skal man tage den årlige dødsrate og dividere med 26 for at finde dødsraten i en 2-ugers periode.
Charlie har gjort noget i den stil og fået 1/5000. Sansynligheden for, at en tilfældigt udvalgt person i den givne aldersgruppe falder død om i en bestemt to-ugers periode.
Nå, men der var jo 4 døde, og de døde i samme to-ugers periode. Man kan sige sig selv, at sandsynligheden så bliver endnu mindre. Charlies udregning på tavlen var noget i retning af: Vi har 25 personer. Vi vil finde sandsynligheden for, at 4 af dem tilfældigt dør i 2-ugers perioden.
Der er 25!/(4!⋅21!) måder, hvorpå man kan tage en gruppe på 4 personer ud af en gruppe på 25. Her er 25!= 25⋅24⋅23…⋅2⋅1 et stort tal, men det skal divideres med (25-4)!=21! og med 4!

25!/(4!⋅21!)=25⋅24⋅23⋅22/24=12650

Det skal så ganges med (1/5000)^4, hvor ^4 betyder “i fjerde”. (Sandsynligheden for, at 4 personer dør) og med (4999/5000)^21 (sandsynligheden for, at de sidste 21 ikke dør)
Jeg får  2,0155⋅ 10^(-11)= 1:49615081730 og det er meget mere (en mindre sandsynlighed), end Charlie fik. Men der er faktisk også en fejl. Vi skal ikke se på sandsynligheden for, at der dør 4 i en tilfældig periode, men at der dør 4, når der allerede er en, der er død, for det er jo der, vi “regner” – måler de to uger – fra. Lad X være antal døde, så vil vi udregne sandsynligheden for X=4, givet X>0. Skrives P(X=4|X>0)

Fra Bayes formel ved vi, at det kan udregnes som P(X=4)/P(X>0). Tælleren er det, vi har regnet ud ovenfor. Nævneren er P(X>0)=1-P(X=0) og P(X=0) er (4999/5000)^25

Jeg får P(X>0)=0,004988, og P(X=4|x>0)=4,040715223*10^(-9)=1:247480939, hvilket er ca 25 gange så meget (min sandsynlighed er 1/25 gange Charlies), som Charlie får. Sandsynlighedsteori er ikke så let – især, når man ikke helt ved, hvad han har regnet på…

For mere om dødsrater m.v., se Plus magazine. Det er rigtig godt skrevet af bl.a David Spiegelhalter, som virkelig ved, hvad han snakker om. Det burde oversættes til dansk. Man kan lege med diverse grafer, og jeg kan f.eks. se, at min forventede levealder falder med tre år, hvis jeg pludselig bliver en mand (og er englænder og er en gennemsnitsperson).

Organisationsteori

Der er mange måder, hvorpå man kan studere en organisation. Og mange teorier. Fra økonomi, sociologi, psykologi,… Charlie analyserede forbryderorganisationen og konkluderede, at en demograf og en programmør måtte have været involveret. Og han skrev til sidst en artikel til et tidsskrift, hvoraf det fremgik, at overskurken måtte være lederen af organisationen.

Man kan modellere organisationer som grafer, hvor man holder styr på, hvem der kommunikerer med hvem. Man kan se på organisationens opgaver, hierarkier og meget mere. Og man kan ikke bruge samme teori på alle typer organisationer.

Jeg ved ikke, hvordan han gjorde det, men lagde mærke til følgende replikskifte: Charlie sagde, at organisationsteori kan bruges til at sige, at der ikke kan have været en sammensværgelse bag mordet på Kennedy, fordi den nødvendigvis ville involvere rigtig mange mennesker, og så mange kan ikke holde mund. Men som en af de andre personer bemærkede “så er det nok derfor, vi allesammen har hørt om den sammensværgelse…”

Metadata

Rachel har et flash drive – en slags hukommelse a la USB med en masse data. Oswald gennemskuer, at der er noget lusk med de data, og Charlie og Millie kigger ned over dem og siger, at der er for mange 3 taller og 7 taller. Det er en slags metadata- data om data.

Her henvises muligvis til Benfords Lov se her på bloggen, som siger, at i mange typer data vil første betydende tal være 1 meget oftere end andre cifre, og ikke kun i 1/9 af tilfældene, som man skulle tro.
Så forfalskede tal kan ofte genkendes på, at fordelingen af cifre er forkert i forhold til, hvad ægte data ville udvise.

Det kan også være noget med psykologi, at 3 og 7 vælges tit, hvis man skal sige et tilfældigt tal. Det har jeg ikke kunnet finde noget link om, men 3 og 7 er hellige tal i flere religioner, så der er måske noget om, at folk derfor har dem liggende “på tungen”, når de bliver spurgt.

Jeg ved, der er gymnasielærere, der har brugt Numb3rs og måske ovenikøbet bloggen her som udgangspunkt for undervisningsforløb eller studieretningsprojekter.
Hvis I vil dele dem med omverdenen, vil bloggen gerne stille serverplads til rådighed.
Så derfor: Send meget gerne links, pdf-filer,… . Så vil jeg lægge det på under ressourcer.