Hva er sannsynligheten for at ditt telefonnummer er primtall?

Et illustrasjonsbilde for å gjøre artikkelen mer interessant. Det har ingenting med matematikk å gjøre. Kilde: Wikipedia.

Et illustrasjonsbilde for å gjøre artikkelen mer interessant. Det har ingenting med matematikk å gjøre. Kilde: Wikipedia.

La oss snakke litt om telefonnummer og primtall og sannsynlighet. Hva er sannsynligheten for at ditt telefonnummer er primtall?

La oss starte med telefonnummer. I prinsippet kan et telefonnummer være en hvilken som helst åttesifret tallkombinasjon mellom 0 og 10^8-1. Men la oss være litt mer realistiske. Ingen privatpersoner i Norge har et mobilnummer som begynner på 0, 1 eller 8. De resterende tallene er enten fasttelefon eller mobil (her er kilden min denne to år gamle tråden på Norsk Freakforum). Så for oss er definisjonen på et telefonnummer et hvilken som helst 8-sifret tall som starter på en av tallene 2,3,4,5,6,7 eller 9 (det gir 7 \cdot 10^{7} mulige nummer, altså ca. 14 nummer per person i Norge. Dette er egentlig ikke så mye - ettersom bedrifter ofte har mange nummer).

La oss snakke litt om primtall. Et primtall er et tall som ikke er en 1, og er delelig med kun seg selv og 1. (for de matematisk sofistikerte: vi vil at restkroppen \mathbb Z/(p) skal være en kropp, og hvis p=1, får vi \mathbb Z/(p) =0, altså "kroppen med ett element", som er problematisk). For å friske minnet, her er de første primtallene: 2,3,5,7,11,13,17,19,23,29,31,37,41,43..,101,... So far so good!

Det er lett å se at det er uendelig mange primtall. Dette ble bevist for flere tusen år siden, og det mest kjente beviset, som fremdeles er det eneste man lærer i dag, ble gitt av Euklid. Det går som følger: Vi skal konstruere en uendelige følge med primtall (ikke nødvendigvis alle, men likefullt en uendelig følge). La første tall i følgen være 2. Anta så induktivt at vi har konstruert følgen opp til a_k. Dann så tallet a_1a_2a_3 \cdots a_k + 1 (produktet av alle tallene i følgen sålangt pluss en). Dette er et tall som ikke har noen faktor felles med noen av tallene i følgen så langt, så det må finnes et primtall p som er ulik a_i for i=1,2,\cdots,k. Sett a_{k+1}=p. Dette viser at vi kan danne en uendelig lang liste med forskjellige primtall. QED.

Legg merke til at teknikken i beviset ikke produserer alle primtall. For å se dette, prøv å konstruér følgen over, og se hvilke primtall som mangler. Hint: følgen vil starte med 2,3,7,....

Men dette var en digresjon. Det neste store spørsmålet med primtall, nå når vi vet at det er uendelig mange av dem, er: hvordan fordeler primtallene seg? Med andre ord, hvor mange primtall er det i intervallet [0,x] når x varierer? For eksempel, for x=10, ser vi at det er 4 primtall mellom 0 0g x=10. Mellom 0 og 20 har vi 8 primtall. Mellom 0 og 30 har vi 10 primtall. Allerede nå ser vi et mønster: primtallene blir sjeldnere og sjeldnere. Faktisk kan vi komme med en tilnærmet formel for hvordan hvor mange primtall det er lavere enn x (vi kaller "antall primtall lavere enn x for \pi(x)):

 \pi(x) \sim \frac{x}{\ln x}.

Her betyr "\sim" at formelen er en god tilnærming for store x. Denne formelen er kjent som "primtallssatsen", og ble først bevist av Hadamard og Poussin ved hjelp av komplekse teknikker (både billedlig og bokstavelig talt). Et mer elementært bevis ble gitt mye senere av den norske matematikeren Atle Selberg og den ungarske matematikeren Paul Erdös uavhengig av hverandre (noe som forøvrig skapte en ørliten plagiatkonflikt i matematikermiljøet, men det er annen sak...).

y-aksen viser antall primtall lavere enn x. Bildet er sakset fra Wolphram Mathworld.

y-aksen viser antall primtall lavere enn x. Bildet er sakset fra Wolphram Mathworld.

Det som er så fint med primtallssatsen, er at vi nå kan beregne hvor mange telefonnummer som er primtall (circa, selvfølgelig!). Siden ingen telefonnummer starter på 8, må vi gjøre dette i to omganger. Først regner vi ut hvor mange primtalltelefonnummer det er som begynner på 2,3,4,5,6,7, og så hvor mange som begynner 9. Det første tallet er \pi(80000000)-\pi(20000000) (klarer leseren å se hvorfor??). Det andre tallet er \pi(100000000)-\pi(90000000). Nå kan vi bruke primtallformelen over for å regne ut hva disse differansene er. Gjør vi det får vi henholdsvis 3.206.519  og 514.762 (rundet til nærmeste heltall). Dermed er det circa 3.206.519+514.762=3.721.281 \approx 3.7 \cdot 10^6 telefonnummer som er primtall.

Vi konkluderer med at prosentmessig er det

 100 \cdot \frac{3.7 \cdot 10 ^6}{7 \cdot 10^7}\approx 5.3\%

Så med andre ord, det er omtrent like mange folk med primtallstelefonnummer som Venstre-velgere i dette landet.

Posted in Uncategorized | Leave a comment

Matematisk julepynt

Det er jul og eksamenstid. Det betyr at vi har ekstra motivasjon til å gjøre ting som ikke innebærer å lese til eksamen - for eksempel å lage julepynt.

Først en liten forhistorie

Et polyeder er en matematisk figur som er satt sammen av polygoner. Eksempler på polyedre er:

image003 Leonardo_polyhedra

Polyedret til venstre er satt sammen av 18 kvadrater og 8 trekanter. Polyedret til høyre, også kjent som en såkalt "fotball" (red. anm: utstyr brukt av sportsinteresserte), er satt sammen av 12 femkanter og 20 sekskanter.

Men noen polyedre er likere enn andre. Dette er polyedre som er satt sammen av helt like figurer, og der alle figurene møtes på samme måte i hvert hjørne. Dette er de platonske legemene:

 platonic

Disse er satt sammen av trekanter, kvadrater eller femkanter. Det gule polyedret er satt sammen av fire trekanter, det grønne er satt sammen av åtte trekanter, det røde er satt sammen av seks kvadrater (red. anm: også kalt en terning). Det lilla er satt sammen av 20 trekanter, og det blå er satt sammen av 12 femkanter. De kalles (i samme rekkefølge) for tetraeder, oktaeder, hexaeder, icosaeder og dodekaeder (på engelsk bytter man ut "eder" med "hedron").

Her er en funfact kjent som Eulers teorem: teller du antall hjørner (H), antall kanter (E) og antall flater (F) i figurene over, får du alltid at forskjellen H-E+F=2. (prøv selv!)

Julepynt

Nå har vi kommet til poenget med denne posten. Polyedre eksisterer ikke bare i matematikernes fantasi, men også på juletrærne - ihvertfall om man henger dem der. Du må bare lage dem først.

Alt du trenger er piperensere, gjerne av typen som glitrer. Jeg fant mine på juggelbutikken "Tiger" på Arkaden i Oslo. Antakelig selges de andre steder også.

Greia er følgende: bruk en linjal, og brett piperenserne slik at du deler dem i tre, fire, eller fem like store deler (ha en liten del til overs slik at du "knyte" kantene). Så setter man dem sammen. Her er noen bilder:

2013-12-12 10.40.18De over er tetraederet, kuben og oktaederet. (Beklager bildekvaliteten, men jeg skal liksom drive med matematikk og ikke drasse på gode kameraer!)2013-12-12 10.40.22Her er oktaederet på nytt, og på høyresiden er dodekaederet.

2013-12-12 10.40.30Til slutt har vi ikosaederet. Det var vanskeligst å lage, og ble ikke så veldig symmetrisk. Utfordring: gjør det bedre selv.

Posted in Uncategorized | Leave a comment

"hva er MATEMATIKK" av Liza Lorentzen

Hva er matematikk?Boken "hva er MATEMATIKK" av professor i matematikk ved NTNU, Lisa Lorentzen, kom ut i november. Den er en del av Universitetsforlagets "hva er"-serie. Jeg fullførte nylig boken.

Boken er ment for folk flest, og det er meningen at hvem som helst skal kunne lese boken uten å gå glipp av noe.  Boken har syv kapitler, hvor de seks siste begynner med "matematikk og ...": tall, verden, struktur, sannhet, uendeligheten og skjønnhet.

Målet med boken er ikke å gi noe hurtigkurs i matematikk eller å være noe "survival kit" gjennom Kalkulus-kurset. Den prøver, tvert om, å beskrive hva matematikk er gjennom å appellere til hva en matematiker gjør og hva som er så fascinerende med matematikk. Nettopp på siste punktet skinner forfatterens egen fascinasjon gjennom. Matematikk er utrolig fascinerende, og har man ikke allerede denne fascinasjonen, smitter den over fra Lorentzens engasjerte beskrivelser.

På enkelte steder virker hun så fascinert at det nesten virker kunstig - men man skal ikke klage så mye over overdreven fascinasjon for matematikk! Slikt finner man ikke over alt.

Hun tar blant annet opp Möbius-båndet, at \sqrt{2} er irrasjonal, Koch-snøflak, fraktaler, matriser, matematiske modeller, uendelighet, tesseleringer av planet, Euler-karakteritistikk, med mer.

Boken er lettlest (kan hende enkelte deler ikke er kjempelettlest om man ikke er vant til å lese tung matte) - fin sengelesing/trikkelesestoff.

Posted in Anmeldelser | Leave a comment

Fire farger-teoremet

Jeg postet for ikke lenge siden følgende tweet@MatematikkFakta:

Du vil aldri trenge mer enn 4 farger om du skal fargelegge et kart.

Kort tid etterpå var noen av mine observante følgere ute og kommenterte at påstanden ikke var helt presis. Dette er selvsagt riktig, og kudos til dem og alle andre med observant blikk.

For at påstanden skal stemme, må den gjøres presis. Det er to ting som er uklart slik påstanden står nå. 1) Hva menes med å fargelegge et kart? 2) Hva er et kart!?

I denne bloggposten skal jeg prate litt om punktene 1) og 2), og litt om hvordan påstanden til slutt ble bevist. Vi vil se at å reformulere problemer er vanlig og nyttig i matematikken.

"Moteksempel" til fire farger-teoremet. Fra Wikimedia Commons, laget av Inductiveload.

Først og fremst, i virkeligheten er påstanden feil. For at fire farger skal holde om vi skal fargelegge et kart, må landene være enkeltsammenhengende. Dette betyr at tilfeller som Russlands Kaliningrad eller andre land med enklaver ikke kan tillates. Se bildet til høyre. Det skal forestille et land A med en enklave. Resultatet er at vi er nødt til å bruke 5 farger. I tillegg må vi tillate at hjørnene til landene får lov til å møte i samme farge.

Så, siden vi har utelukket Russland med Kaliningrad (også Aserbajdsjan med Nakhitsjevan), så virker plutselig ikke teoremet særlig relevant for virkeligheten. Faktisk forteller Wikipedia-artikkelen om teoremet at selv ikke folk som lager kart bryr seg - for de velger som regel å bruke flere farger uansett.

Så vi kan likegjerne omdefinere hva problemet handler om. For å unngå problemer med rare kart, hjørner, pussige kurver, og så videre - reformulerer vi problemet ved hjelp av grafteori. Kort sagt: fra et kart lager vi en graf (en graf er en samling noder, med kanter mellom dem), som i bildet under:

Fra kart til graf. Fra Wikimedia Commons, laget av Inductiveload.

Det vi gjør er følgende: la hvert land være representert med en node (=prikk). Om to land grenser til hverandre, tegner vi en strek mellom dem. Fire farger-teoremet kan nå reformuleres til følgende:

Nodene til enhver graf i planet kan fargelegges med 4 farger slik at ingen nabo-noder har samme farge.

Eller mer teknisk: "enhver planar graf kan fire-farges". Fordelen med denne omformuleringen er at vi nå kan bruke masse verktøy fra algebraisk topologi og grafteori for å arbeide med problemet (i tillegg til at problemstillingen er mye mer presis).

Teoremet har en lang historie. Det ble først formodet i 1852, hvoretter flere gale bevis ble presentert. I 1890 ble fem farger-teoremet bevist - som faktisk er betraktelig lettere å bevise enn fire farger-teoremet. Først på 60-70-tallet begynte man igjen å gjøre framskritt, og da ved hjelp av datamaskiner. I 1976 annonserte Kenneth Appel og Wolfgang Haken ved University of Illinois at de hadde bevist teoremet - mye ved hjelp av en datamaskin.

Det de hadde gjort, var å redusere problemet. De fant ut at, enkelt sagt, enhver slik graf kan bli bygd opp av et endelig antall enklere grafer. De fant 1,936 slike, så for å bevise teoremet var det nok å be en datamaskin gå gjennom alle disse mulighetene, og sjekke èn og èn.

Dette var langt fra enkelt, og krevde mye manuelt arbeid. For å finne disse 1,936 tilfellene, måtte de gjøre mye for hånd. Det endte opp med et over 400 sider langt bevis. De tekniske detaljene krevde mange originale ideer og annen matematisk analyse. En rekke observasjoner reduserer teoremet til såkalte triangulerte grafer, og litt tellearbeid setter begrensninger på eventuelle moteksempler. Til slutt med en metode som er inspirert fra fysikk brukt; på engelsk "method of discharging". Man ser for seg at grafen er en elektrisk ledning, og har en viss ladning. Så kan man redusere grafen steg for steg sålenge man holder styr på "ladningen". Mer informasjon om dette smarte trikset er på Wikipedia-artikkelen om beviset.

Men matematikere er kresne typer, og beviset fikk mye kritikk. De mente for eksempel at for at et bevis skulle være et ordentlig matematisk bevis, måtte det kunne sjekkes av mennesker. Andre mener at datamaskiner kun skal gjøre utregninger, og ikke steg i bevisene (det er en forskjell her).

Tross dette er det et faktum at maskiner tross alt gjør færre feil enn mennesker. Den største innsigelsen mot teoremer bevist av datamaskiner er estetisk: beviset gir ikke noen ny innsikt i problemet eller gir opphav til nye nyttige begreper. Det er jo tross alt dette som er vakkert med matematikk: det å få innsikt i et stort problem.

Til slutt: På en torus (=smultring) stemmer heller ikke 4-farge-teoremet. Her kreves 7 farger:

Torusen krever 7 farger.

Posted in Applications, Smalltalk | 2 Comments

En altfor vanskelig måte å løse en enkel ligning på

La oss si at vi har ligningen x=2x-2. Dette lærte man å løse på ungdomsskolen ved å få x-ene på èn side. (i dette tilfellet ser vi raskt at x=2 er eneste løsning). Men hva om vi har lyst til å være vanskelige?

Siden x=2x-2, kan vi skrive x=2(2x-2)-2=4x-6. Så vi har nå at x=4x-6. På samme måte kan vi sette inn for x i denne ligningen, og få x=4(2x-2)-6=8x-14. Fortsetter vi n ganger, får vi at x=2^nx-2^n-2^{n-1}+\cdots+2. Det siste leddet er en geometrisk rekke, som forenkler til 2^{n+1}-2.

Vi har altså nå at x=2^nx-2^{n+1}-2.  Vi deler på 2^n på begge sider og får \frac{x}{2^n}=x-2-\frac{2}{2^n}. Lar vi nå n gå mot uendelig, forsvinner venstresiden av ligningen og mye av høyresiden. Vi står igjen med 0=x-2, så x=2.

Posted in Smalltalk | 2 Comments

En veldig enkel tilfeldig tall-generator

Akkurat nå leser jeg boken "Chaos - A Very Short Introduction". Den definerer et kaotisk system til å være et system som er veldig ømfintlig overfor initialbetingelsene. På et tidspunkt nevner boken et veldig enkelt dynamisk system.

Hva mener vi med et dynamisk system? For våre formål mener vi bare en følge med tall, x_0, x_1, \ldots. En enkel klasse av dynamiske systemer er på formen x_0=a for en eller annen a, som vi kaller initialverdien. Så definerer vi rekursivt alle andre verdier av x_n som x_{n+1}=f(x_n) hvor f(x) er en eller annen funksjon.

Nå skal vi la f(x)=4x(1-x). Denne har to nullpunkter, nemlig x=0 og x=1. Den har et toppunkt i x=1/2.

Dette gir opphav til et dynamisk system så snart vi velger en initialverdi. Det kule med denne enkle funksjonen, er at i tidligere tider brukte man denne for å generere "tilfeldige" tall. La oss se litt på dette. En enkel, rekursiv implementasjon i SAGE er gitt ved:

def r(x,n):
    if n==0:
        return x
    else:
        return r(4*x*(1-x),n-1)

Vi genererer listen:

def generateList():
    return [[i,r(1/float(pi),i)] for i in range(0,500)];
L = generateList()

Og vi plotter den:

p = line(L)
p.show(xmin=0,xmax=500,ymin=0,ymax=1)

Her er resultatet vi får (klikk på bildet for noe større versjon):

Dette er kanskje litt overveldende. La oss bare ta 100 punkter:

Dette er ganske kult, for vi ser at oppførselen til følgen er helt vill. Betydningen av "vill" kan defineres matematisk, men la oss hoppe over det. Poenget er at følgen i stor grad oppfører seg "tilfeldig". Vi ser også at små endringer i startverdien kan gi helt forskjellige følger. Under er først for startverdien 0.3, så for startverdien 0.31.

Vi ser at grafene er ganske like, men at verdiene opptrer på ganske forskjellige steder. Dette kan utnyttes for å lage tilfeldige tall. Man kan for eksempel først velge en initialverdi, så kjøre det dynamiske systemet, og bruke dette til å generere en følge av 100 tall. Neste gang velger man en annen initialverdi, og man vil få en følge som ikke ligner på den forrige.

Posted in Applications, Smalltalk | 1 Comment

Litt om telling

La oss være litt filosofiske. Du er et steinaldermenneske, eller noe enda eldre enn det, eller bare dum. Du kan nemlig ikke tallene, men vil likevel finne ut om det er du eller naboen som har flest fisk.

Hadde du kunnet telle,  hadde det vært mye enklere, for det er lett å sjekke om et tall er større enn et annet. Matematisk kan vi si at du har en funksjon fra mengden av fiskehauger (F) til heltallene. La oss kalle den f:F \to \mathbb{N}. Så om din fiskehaug kalles A, og naboen B, er alt vi trenger å sjekke om f(A) > f(B).

Men du kjenner ikke til heltallene \mathbb{N}! Fiskehauger er mengder bestående av fisk. Symbolsk kan vi si A = \bigcup_{a \text{ fisk}} \{a\}. Så hvordan kan vi telle uten tall? Vel, det kan vi ikke! Men vi er ikke helt fortapte. La oss si at du har to hauger, A og B,  med like mange fisk. Da kan hver fisk fra haug A "parres" med nøyaktig en fisk fra haug B, og hver fisk fra haug B kan parres med èn fra haug A. Vi ser at vi får en 1-1-korrespondanse mellom fisk i haug A og fisk i haug B.  Matematisk har vi en bijeksjon g:A \to B, det vil si en funksjon fra A til B som er både 1-1 og "på"/surjektiv.

Men hvordan er situasjonen om det er færre fisk i haug A enn i haug B? (for enkelhets skyld kan du tenke at det er to fisk i haug A og 5 i haug B) Da ser vi at det er umulig å få til en funksjon fra A til B som er "på" B, eller surjektiv. Det betyr at det er umulig å gi hver fisk i haug B en "partner" i A, fordi det er færre fisk i haug A.

Motsatt, om det er flere fisk i haug A enn i haug B, sier litt ettertanke oss at det er umulig å få til en injeksjon A \to B. En injeksjon er en funksjon som ikke sender to forskjellige tall til samme tall b . Om det er flere fisk i haug A, må minst to a sendes til samme b.

Dermed ser vi at det eneste tilfellet hvor vi klarer å få til en funksjon som er både surjektiv og injektiv, er når det er like mange fisk i haug A som i haug B. Dette gir oss også muligheten til å si når det er færre eller flere fisk i haug A enn i haug B. Vi definerer det til å være flere fisk i haug A enn i haug B om det ikke finnes noen injeksjoner A \to B, og vi definerer det til å være færre fisk i haug A enn i haug B om det ikke finnes noen surjeksjoner A \to B. Til slutt sier vi at det er like mange fisk om det finnes en bijeksjon mellom A og B, altså både en injeksjon og surjeksjon.

Hva forteller alt dette oss? Det første vi kan si, er at heltallene har mye mer struktur enn vi trenger om vi bare skal sjekke om noe har like mange elementer som noe annet. Å sjekke om det finnes en injeksjon/surjeksjon/bijeksjon sier ingenting om hvor mange elementer det er i mengdene, bare om det er færre/flere/like mange. Å telle er en kvantitativ operasjon, mens å sjekke hva slags funksjoner det finnes mellom to mengder er en kvalitativ operasjon.

Men ok, vi har kommet fram til at vi ikke trenger heltallene for å sjekke hvilken mengde som har flest elementer. Men hva er poenget? Hvorfor gjøre det så tungvindt? Vel - nå har vi en mer elementær måte å sjekke størrelse på mengder på, og dette hinter om at vi kanskje kan generalisere definisjonene av "flere/færre enn" til andre mengder enn bare endelige.

For nå, la oss anta at leseren skjønner hva som menes med en uendelig mengde. Et eksempel på en slik mengde er mengden av alle heltall. Det er lett å sjekke at det er flere heltall enn, la oss si, elementer i mengden A=\{1,2,3,4,5\}. Det finnes nemlig ingen surjeksjoner A \to \mathbb{N} (Bevis: om det finnes en slik surjeksjon, finnes også en surjeksjon A \to \{1,2,3,4,5,6\} ved restriksjon. Dette går bare ikke).

Et annet eksempel på en uendelig mengde er mengden av partall, altså tallene E=\{2,4,6,8,\cdots\}. Siden partallene er en ekte delmengde av heltallene (det finnes heltall som ikke er partall), er det naturlig å tro at det er flere heltall enn partall. La oss sjekke med vår definisjon: Kan vi bevise at det ikke finnes noen injeksjoner \mathbb{N} \to E? Svaret er nemlig nei: et eksempel på en injeksjon er funksjonen n \to 2n. Det er lett å sjekke at denne er injektiv, så vi må konkludere (med vår definisjon av "færre enn") at det er færre/like mange heltall som partall. Det er også lett å se at den er surjektiv, så vi er faktisk nødt til å konkludere med at det er like mange partall som heltall, selv om det åpenbart finnes mange heltall som ikke er partall.

Nå blir du kanskje frustrert, river deg i håret, og tenker at matematikere lager helt pussige definisjoner. Er alle mengder like store, bare de er uendelige? Nei, det finnes mange forskjellige "uendeligheter", alle av forskjellige størrelse (det vil si, det finnes ingen bijeksjoner mellom dem). Det kan vi ta i en senere bloggpost.

Posted in Set Theory, Smalltalk | Leave a comment

Beregne volum av kuler

I anvendelser av matematikk har man ofte behov for å regne ut volumer av avanserte geometriske objekter. Som regel går det ikke an å regne ut slikt for hånd eller med pene formler, så matematikere jobber mye med å finne algoritmer som datamaskiner kan utføre for å finne en tilnærmet løsning.

Tenk deg at du har fått i oppdrag å regne ut arealet av en kule i n dimensjoner. Først av alt - hva i all verden mener vi med dette? En sirkel i planet med radius 1 kan beskrives som alle punkter (x,y) i planet slik at  x^2+y^2=1 (hvorfor? hint: Pythagoras' setning). På samme måte kan vi beskrive en kule som alle punkter (x,y,z) i rommet slik at x^2+y^2+z^2=1.

Vi generaliserer, og definerer en  kule i n dimensjoner til å være alle punkter (x_1,x_2,\ldots,x_n) i \mathbb{R}^n slik at \sum_{i=1}^n x_i^2 = 1.

Men la oss nå si at du har lyst å regne ut arealet av en sirkel i planet. Vi kan anta sirkelen har radius 1 og er plassert i origo. Tegn så et kvadrat rundt sirkelen, med diagonaler med lengde 1, som på figuren under:

Enhetssirkelen på innsiden av en firkant.

Siden firkanten har sidelengder på 2, har den arel 4. Her kommer trikset: kast masse "dart-piler" (eller punkter, om du vil) på firkanten slik at de havner tilfeldig spredt omkring. Kall arealet til sirkelen for A. Da vil A/4 av dart-pilene havne på innsiden av sirkelen.  Dermed, for å få arealet av sirkelen, ganger vi dette forholdet med 4.

Fordelen med denne metoden er at det er veldig lett å sjekke om et punkt er på innsiden av sirkelen eller ikke. Vi sjekker bare om x^2+y^2 < 1 eller ikke. Om x^2+y^2 < 1, så er punktet (x,y) på innsiden av sirkelen. Dette generaliserer lett til flere dimensjoner enn 2 og til andre figurer enn sirkler.

Jeg har testet denne metoden på sirkler i Python. Jeg laget et program som jeg kalte for areal_kule.py. Vi tester for sirkelen og med 1000 dart-piler:

Fredriks-MacBook-Air:Python Fredrik$ python areal_kule.py 2 1000
Tilfeldig volum: 3.196
Ekte volum: 3.14159265359
Error: 0.0544073464102

Ikke veldig imponerende, kanskje - vi kastet tross alt 1000 dart-piler! Vi tester med èn million dart-piler i stedet (dette tok litt under 10 sekunder på min maskin):

Fredriks-MacBook-Air:Python Fredrik$ python areal_kule.py 2 1000000
Tilfeldig volum: 3.144456
Ekte volum: 3.14159265359
Error: 0.00286334641021

Nå ble resultatet en god del bedre. La oss prøve å regne ut volumet av en kule:

Fredriks-MacBook-Air:Python Fredrik$ python areal_kule.py 3 1000000
Tilfeldig volum: 4.184968
Ekte volum: 4.18879020479
Error: 0.00382220478639

Ikke dårlig! Denne metoden kalles for Monte Carlo-integrasjon, og det viser seg at slike "tilfeldige" metoder ofte er mer effektivt i høyere dimensjoner.

Når vi først snakker om sirkler, kan man lure på hva som skjer med volumet til sfærer når vi øker dimensjonene. Resultatet er litt kontraintuitivt:

Volum kuler

Vi ser at volumet til kulene øker fram til dimensjon 4, hvor det begynner å falle. Faktisk går kulevolumet i dimensjon n mot null når n går mot uendelig. Dette er fordi diagonallengden på kvadratet rundt kulen blir større og større etterhvert som n øker.

For ordens skyld, her er Python-programmet jeg brukte for å regne ut volumene:

from random import random
from math import pi, gamma, fabs
import sys

if len(sys.argv) == 1:
    sys.exit("Skriv areal_kule d n. d dimensjon, n antall, std n=1000")
if len(sys.argv) == 2:
    d = int(sys.argv[1])
    n = 1000
if len(sys.argv) == 3:
    d = int(sys.argv[1])
    n = int(sys.argv[2])

i = 1
s = 0.
cube_area = 2**d #area of cube in dimension d

while i < n:
    if (sum([random()**2 for j in range(d)])) < 1:
        s += 1
    i += 1

random_area = (s/n)*cube_area
true_volume = pi**(0.5*d)/gamma(0.5*(d+2))

print "Tilfeldig volum: " + str(random_area)
print "Ekte volum: " + str(true_volume)
print "Error: " + str(fabs(random_area-true_volume))
Posted in Smalltalk | 3 Comments

Monty Hall-paradokset

"Monty Hall"-problemet er et statistisk paradoks som ble kjent etter at Marilyn vos Savant skrev om det i et amerikansk blad i 1990. Problemet går som følger:

"Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1 [but the door is not opened], and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?"

Eller på norsk: Du er med på en konkurranse, og skal velge èn av tre dører. Bak en av dørene er det en bil (som er premien), og bak de to andre er det geiter. Om du velger, la oss si, dør nummer 1 - så åpner programlederen en dør, f.eks nummer 3, og bak den er det en geit. Han gir deg nå mulighet til velge dør på nytt. Er det til din fordel?

Intuitivt burde det ikke hjelpe å bytte dør. Du vet fra før at sjansen for at du finner en bil er 1/3. Om programlederen viser deg en dør med geit, vet du at enten er bilen i den du har valgt eller den andre døren som ikke er vist.  Burde det da ha noe å si om du bytter? Det paradoksale (i betydningen at det kan overraske), er at det alltid vil lønne seg å velge ny dør. Hvorfor? Det finnes flere intuitive måter å forklare dette på.

Forklaringen er overraskende enkel: Du taper om du bytter dør hvis og bare hvis du valgte bilen første gang. Sjansen for å velge bil første gang er 1/3. Dermed er sjansen for å vinne med bytting lik 1-\frac{1}{3}=\frac 23.

Eller vi kan teste problemet med empiri (og litt logisk tenking). Jeg programmerte to Monty Hall-funksjoner i SAGE (Python-kode). Den ene funksjonen bytter dør, mens den andre ikke gjør. Så tester vi. Her er koden til funksjonen som bytter dør:

def montyhall_change(choice): # med bytting
   if choice == 1:
       return False
   else:
       return True

Kort forklaring av funksjonen: Vi kan anta bilen ligger bak dør nummer 1. Hvis du velger å bytte, og velger dør nummer 1, taper du. Derfor returnerer funksjonen False. Hvis ikke, viser Monty deg en dør med geit i. Det er bare to dører med geiter, så han må åpne den du ikke valgte. Om du skal bytte, er eneste mulighet å velge døren med bilen, og funksjonen returnerer derfor True.

Vi lager også en funksjon for å ikke bytte dør. Den er naturligvis noe enklere:

def montyhall_keep(choice):
    if choice == 1:
        return True
    else:
        return False

Til slutt simulerer vi konkurransen et stort antall ganger, og ser på tallmaterialet vi får:

k = 10000
s_change = 0
s_keep = 0
for n in range(k):
    random = ZZ.random_element(3)+1
    if montyhall_change(random) == True:
        s_change += 1
    if montyhall_keep(random) == True:
        s_keep += 1

print "Antall forsok: ", k
print "Antall suksess bytte: ", s_change,
      " Antall suksess beholde: ", s_keep
print "Prosent riktig bytte: ", s_change/float(k)
print "Prosent riktig bytte: ", s_keep/float(k)

Koden over kjører konkurransen 10.000 (ti tusen) ganger. For hver gang vi vinner bil, øker s_change eller s_keep med 1, avhengig av hvilken metode vi brukte. Resultatet vises under:

Antall forsok:  10000
Antall suksess bytte:  6721  Antall suksess beholde:  3279
Prosent riktig bytte:  0.6721
Prosent riktig beholde:  0.3279

Dette stemmer godt med utregningene vi gjorde.

Posted in Probability and statistics | Leave a comment

The probability distribution of the length of pop songs

Taking a course in probability can be extremely fun if you try to apply some of acquired knowledge to real world data sets. Finding data types that are easy to gather and at the same time interesting is a problem in itself. By a flash of inspiration, I came to think of this incredible easy example: the length (in seconds) of pop songs.

After a succesful Google search, I ended up with NRK's Spotify list "NRK mP3 - siste 400" and sampled the 42 first song lenghts.  Using the Python function below, the lengths were converted to seconds:

def mintilsek(n):
    min = floor(n)
    s   = (n-min)*100
    return int(round(min*60+s))

The sample data ended up as follows:

w = [52 241 223 231 225 242 263 222 200 220 238 213 210 213 210 183 321
 265 228 200 206 200 228 193 269 289 197 211 211 236 252 222 224 184
232 198 207 220 178 192 258 192]

The natural question to ask is: Which distribution does these numbers belong to? As so many real world populations distribute normally, the first thing I did was to plot the observed sample values in a normal QQ-plot (that is, normal quantiles on one axis, and sample quantiles on the other axis). I did that using the following R code:

> qqnorm(w); qqline(w)

Where w is the data set. The result is seen below:

The fit is not too bad, but there are noticable probability mass on the tails, so a probability distribution with heavier tails should be considered.

Let us for the moment assume that the distrubution is normal. We can do a maximum likelihood estimation, to estimate the parameters \mu,\sigma, the mean and standard deviation respectively. R has (obviously) a function for this:

> fitdistr(w, "normal")
      mean          sd    
  223.785714    29.214751 
 (  4.507934) (  3.187591) 

That is, if we assume that the distribution is normal, then a maximum likelihood estimate of the parameters tells us that the mean song length is 3:43 with a standard deviation of 29 seconds. That is, about 68% of all songs are between 3:14 and 4:12 minutes long.

If we now however assume that the population has a Cauchy distribution, which has heavier tails, then we get the following:

> fitdistr(w, "cauchy")
    location      scale   
  217.829335    15.684886 
 (  3.897386) (  3.090949)

Since neither the mean nor the variance exists for a Cauchy distribution because of its heavy tails, these numbers are difficult to compare with the previous numbers. According to this, however, 50% of all pop songs have length less than 3:37 minutes.

Finally: We know that for sufficiently large samples, the sample average \overline{X} is approximately normal. Thus we can find an approximate confidence interval for the real median \mu (page 386, Devore & Berk). The sample mean is 223.8 and the sample standard deviation is 29.6. Thus by the formula \overline{x} \pm z_{\alpha/2} \frac{s}{\sqrt{n}} we find that a confidence interval for \mu with approximately 95% confidence is  (215, 233).

Conclusion: Though I could, and maybe should, have written a lot more, it seems that assuming song lengths are normally distributed is a fair assumption, given that the data fit was nearly linear for values near the mean. (that is, if we ignore the "extremes", then the distribution is certainly "very" normal)

This proves that playing with statistics can be fun (as I have just been doing it for the last 3-4 hours).

Posted in Probability and statistics, Uncategorized | Leave a comment