Sommerferie – og masser af matematik

Det er sommer og der er stilhed på bloggen. Mens I venter er her et tilbud:

På The Aperiodical har de The Big Internet Math-Off – inspireret af VM i fodbold, I presume. Det er knock out fra begyndelsen af. To matematikformidlere fortæller om deres yndlingsmatematik og der kan så stemmes. Her er et forslag: Jeg lover, at vi vil fortælle mere her på bloggen om mindst et af emnerne. (Eller måske bare give en dansk version – det er svært at konkurrere med Matt Parker og co.)

Her er de hidtidige indlæg:

James Tanton mod Nira Chamberlain.

Tanton: Om at skære en kage op og samle den igen og få kage tilovers – og lave uendelig meget kage.

Chamberlain: Om Formel 1 og hvordan Reynoldsligningen sikrer, hjulene ikke falder af.

Samuel Hansen mod Paul Taylor

Hansen: Hvorfor dine venner har flere venner, end du har (Link til Soundcloud) og hvordan det kan bruges til at stoppe epidemier.

Taylor: Hvordan kan man være helt sikker på, Pythagoras’ sætning holder (se linket ovenfor – det er ikke en video.)

Peter Rowlett mod Alison Kiddle

Rowlett: Parabolske kurver – herunder at tegne dem med rette linjer. Og tikz-kode, så du kan gøre det i LaTeX. Også en lille video

Kiddle: Hagas sætning – matematisk origami, om at folde et kvadrat og få delt siderne i diverse brøkdele Se også Plus Magazine

Edmund Harriss mod Colin Wright

Harriss: Penrose fliselægning. Det har vi haft på bloggen før, men ikke med så fine fliser skåret i træ 🙂

Wright: Tag et spil kort og lav 13 bunker (med 4 i hver). Hvis der er alle kort es, 2,3,…, konge, (ikke nødvendigvis i rækkefølge) er du færdig. Ellers: Kan du omorganisere hver bunke, så du ender med at have es,to,…, konge øverst? Svaret er, ifølge Wright, altid ja.

Tiago Hirth mod Evelyn Lamb

Hirth: Et rebtrick med Borromeanske ringe

https://youtu.be/RRZqX2hOQvk

Lamb: Wallis’ si og sammenhængen med $\pi$ . (I familie med Sierpinskis tæppe, Mengers svamp,…) One level of the construction of the Wallis sieve Hun har mere om det på sin blog Det er et af en længere række af yndlingsobjekter (favourite spaces – svært at oversætte)

Matt Parker mod Matthew Scroggs

Parker: Machine Learning med perler i æsker. En “maskine” lærer at spille kryds og bolle.

Scroggs: Om at spille Asteroids i en kortprojektion (han kalder det Mathsteroids). Blogmosteren her synes, det er supercool, men kortprojektioner er altså virkelig god matematik.

Her er spillet i Mercatorprojekttionen

Der er andre, som er mere udfordrende: Billedet her viser rette linjer i den projektion, der bruges i FNs logo.

FNs logo

James Propp mod Zoe Griffiths

Propp: Om knuder og rebtrick.

Griffiths: Sandsynlihedsteori og placering af passagerer i et fly

Jo Morgan mod Tony Mann

Morgan: Hexaflexagons. Med link til Vi Harts videoer om netop det. De har danske undertekster!

Mann: Om tilfældige tal og at score 100% til enhver eksamen (Njah, mon dog)

Om at blande kort

Dette indlæg er motiveret af https://fredhohman.com/card-shuffling/.

Opdateret 24/6-2018 10:20: Links til Numb3rs-bloggen tilføjet.

Spillekort skal blandes. En gængs måde at gøre det på, er at dele kortbunken i to mindre bunker af (ca.) samme størrelse og mikse de to bunker fra bund til top. På engelsk hedder det et riffle shuffle. (Jeg kender ikke det danske navn for denne måde at blande på.) Man kan overveje hvor mange gange dette skal gøres for bunken “er godt nok blandet” (for en passende definition af det). 7 gange er tilsyneladende nok (hvis man gør det rigtigt osv.). En matematisk model for denne måde at blande på er Gilbert-Shannon-Reeds modellen. Ovre på Numb3rs-bloggen er der mere om spillekort og matematik i dette indlæg. Bemærk at videoen (“7 gange er tilsyneladende nok”) er med Persi Diaconis som også omtales i Numb3rs-indlægget.

En mere simpel måde at blande på, er at tage det øverste kort og indsætte det et tilfældigt sted i bunken. Og sådan fortsætter man. Man kan nu stille sig selv det samme spørgsmål: hvor mange gange skal man gøre dette for at kortbunken er blandet “nok” (jf. ovenfor)?

Man kan vise (se fx 7 gange er tilsyneladende nok / https://fredhohman.com/card-shuffling/), at man i gennemsnit skal gentage en sådan simpel blanding 235 gange for at kortbunken er blandet “nok”. En del af svaret er, at bunken er blandet “nok” når bundkortet (det nederste kort i bunken inden man går i gang med at blande) har nået toppen af bunken og også selv er blevet blandet (dvs. flyttet til et tilfældigt sted i bunken).

I dette indlæg skal vi se, hvordan man kan opnå viden om eksempelvis sådanne processer ved at få computeren til at simulere mange, mange af sådanne blandinger og så registrere interessante egenskaber ved hver realiserede blanding. Denne fremgangsmåde kaldes for Monte Carlo-metoder og er et kraftfuldt værktøj indenfor statistikken. Man kan med en beskrivelse af den datagenererende process finde egenskaber for processen ved at få computeren til at realisere processen mange, mange gange.

Teoretiske resultater er ekstremt vigtige af mange årsager. Men det betyder ikke, at det er den eneste måde at opnå viden om processer på. Med Monte Carlo-metoden kan man dels kontrollere de teoretiske resultater, men ofte kan man faktisk opnå resultater som kan virke umulige at opnå teoretisk.

I dette tilfælde vil vi bruge Monte Carlo-metoden til at dels at finde det gennemsnitlige antal gange man skal blande før bunken er godt nok blandet. Det kan man også relativt let finde teoretisk (se ovenfor). Men man kunne også være interesseret i at finde fraktiler i fordelingen af antal blandinger. Så kan angive, at man i 95% af tilfældene skal blande mellem L og U gange før at bunken er blandet “nok”.

Den letteste måde at lave sådanne simulationer er på computeren med en random number generator (RNG), der kan generere tilfældige tal. Ofte må man nøjes med pseudorandom number generator (PRNG), men det er som regel også tilstrækkeligt. Og så skal man bruge et interface til denne PRNG således man kan få nogle tilfældige tal i beskrivelsen af processen. Ovre på Numb3rs-bloggen er der mere om tilfældige tal i dette indlæg.

Jeg vil her bruge R, der er et helt programmeringsmiljø (inkl. programmeringssprog) hovedsageligt anvendt til statistik, big data, maskinlæring, kunstig intelligens, dataanalyse m.fl. Det er et rigtigt godt vækrtøj at have i sin værktøjskasse. Rstudio er et fint IDE (integrated development environment) til R. Nedenfor bruges R’s sample-funktion til at trække tilfældige tal.

(Helt til sidst i dette indlæg kan I finde den komplette R-kode. Nedenfor kommer koden med output.)

Først skal vi have repræsenteret kortbunken:

> # C: Clubs / klør
> # D: Diamonds / ruder
> # H: Hearts / hjerter
> # S: Spades / spar
> faces <- c("C", "D", "H", "S")
> nums <- c("A", 2:10, "J", "Q", "K")
> 
> # Vores kortbunke: CA, C2, C2, ..., CQ, CK, DA, ..., DK, ...., SK
> # Denne genereres automatisk, men man kunne også gøre det manuelt:
> # pile_init <- c("CA", "C2") # Osv.
> pile_init <- unlist(lapply(faces, function(x) paste0(x, nums)))
> 
> # De første 6 kort i bunken
> head(pile_init, n = 6)
[1] "CA" "C2" "C3" "C4" "C5" "C6"
> 
> # De sidste 6 kort i bunken
> tail(pile_init, n = 6)
[1] "S8"  "S9"  "S10" "SJ"  "SQ"  "SK" 
> 
> # Antallet af kort i bunken
> length(pile_init)
[1] 52

Det er ikke så vigtigt hvordan bunken er blandet når vi går i gang. Vi skal egentlig bare holde styr på det sidste kort som her er “SK”.

Og så går vi i gang med at simulere 1,000 kortblandinger. Hver gang registrerer vi antallet af blandinger, der blev foretaget før bunken var blandet “nok”:

> # Funktion der simulerer én blanding
> simulate_process <- function() {
+   # Vi starter med en ny bunke
+   pile <- pile_init
+   
+   # En tæller til antallet af blandinger
+   rifs <- 0
+   
+   while (TRUE) {
+     # Registrer at der nu er bladet én gang mere
+     rifs <- rifs + 1
+     
+     # Tilfældig position som topkortet skal hen til
+     top_pos <- sample(x = seq_along(pile), size = 1)
+     
+     # Med sandsynlighed 1/52 ender det igen i toppen
+     if (top_pos == 1) {
+       #pile <- pile
+     } else if (top_pos == length(pile)) {
+       # Det kan også ende i bunden
+       pile <- c(pile[-1], pile[1])
+     } else {
+       # Eller et sted midt i mellem
+       pile <- c(pile[2:top_pos], pile[1], pile[-(1:top_pos)])
+     }
+     
+     # Hvis topkortet er bundkortet; 
+     # her kunne man også have skrevet
+     #   if (pile[1] == "SK") {
+     # men dette virker også selvom man ændrer pile_init
+     if (pile[1] == pile_init[length(pile_init)]) {
+       break
+     }
+   }
+   
+   # Topkortet (der er nu er det oprindelige bundkort)
+   # skal også blandes, men vi er ligeglade med hvor det ender
+   rifs <- rifs + 1
+   
+   return(rifs)
+ }
> 
> # Indstiller PRNG til samme tilstand for at kunne reproducere resultaterne
> set.seed(1)
> 
> # Simulér processen 1,000 gange
> riffles <- replicate(1000, simulate_process())
> 
> # De første 6 blandinger:
> head(riffles, n = 6)
[1] 249 191 205 280 189 314
> 
> # Gennemsnittet af antal blandinger
> mean(riffles)
[1] 234.757

Som I kan se får vi også at der i gennemsnit skal 235 blandinger til.

Men vores simulationer gør os i stand til at finde og vise fordelingen af antal blandinger:

> # Estimer fordelingen
> rif_dens <- density(riffles)
> 
> # Equal-tailed interval (begge haler har samme sandsynlighed)
> qs <- quantile(riffles, c(0.025, 0.975))
> 
> # Find x-værdierne
> x1 <- min(which(rif_dens$x >= qs[1]))  
> x2 <- max(which(rif_dens$x <  qs[2]))
> 
> # De centrale 95%
> rif_dens$x[c(x1, x2)]
[1] 144.2375 384.8943
> 
> plot(rif_dens)
> polygon(x = c(rif_dens$x[c(x1, x1:x2, x2)]), y = c(0, rif_dens$y[x1:x2], 0), col = "gray")
> abline(v = mean(riffles), lty = 2)

Altså vil man skulle forvente at skulle blande mellem 144 og 385 gange (og i gennemsnit 235) før at denne måde at blande på giver en bunke der er blandet nok.

(Hvilket nok er medvirkende til at jeg aldrig har set nogen praktisere denne form for kortblanding.)

Komplet R-kode:

# C: Clubs / klør
# D: Diamonds / ruder
# H: Hearts / hjerter
# S: Spades / spar
faces <- c("C", "D", "H", "S")
nums <- c("A", 2:10, "J", "Q", "K")

# Vores kortbunke: CA, C2, C2, ..., CQ, CK, DA, ..., DK, ...., SK
# Denne genereres automatisk, men man kunne også gøre det manuelt:
# pile_init <- c("CA", "C2") # Osv.
pile_init <- unlist(lapply(faces, function(x) paste0(x, nums)))

# De første 6 kort i bunken
head(pile_init, n = 6)

# De sidste 6 kort i bunken
tail(pile_init, n = 6)

# Antallet af kort i bunken
length(pile_init)

# Funktion der simulerer én blanding
simulate_process <- function() {
  # Vi starter med en ny bunke
  pile <- pile_init
  
  # En tæller til antallet af blandinger
  rifs <- 0
  
  while (TRUE) {
    # Registrer at der nu er bladet én gang mere
    rifs <- rifs + 1
    
    # Tilfældig position som topkortet skal hen til
    top_pos <- sample(x = seq_along(pile), size = 1)
    
    # Med sandsynlighed 1/52 ender det igen i toppen
    if (top_pos == 1) {
      #pile <- pile
    } else if (top_pos == length(pile)) {
      # Det kan også ende i bunden
      pile <- c(pile[-1], pile[1])
    } else {
      # Eller et sted midt i mellem
      pile <- c(pile[2:top_pos], pile[1], pile[-(1:top_pos)])
    }
    
    # Hvis topkortet er bundkortet; 
    # her kunne man også have skrevet
    #   if (pile[1] == "SK") {
    # men dette virker også selvom man ændrer pile_init
    if (pile[1] == pile_init[length(pile_init)]) {
      break
    }
  }
  
  # Topkortet (der er nu er det oprindelige bundkort)
  # skal også blandes, men vi er ligeglade med hvor det ender
  rifs <- rifs + 1
  
  return(rifs)
}

# Indstiller PRNG til samme tilstand for at kunne reproducere resultaterne
set.seed(1)

# Simulér processen 1,000 gange
riffles <- replicate(1000, simulate_process())

# De første 6 blandinger:
head(riffles, n = 6)

# Gennemsnittet af antal blandinger
mean(riffles)

# Estimer fordelingen
rif_dens <- density(riffles)

# Equal-tailed interval (begge haler har samme sandsynlighed)
qs <- quantile(riffles, c(0.025, 0.975))

# Find x-værdierne
x1 <- min(which(rif_dens$x >= qs[1]))  
x2 <- max(which(rif_dens$x <  qs[2]))

# De centrale 95%
rif_dens$x[c(x1, x2)]

plot(rif_dens)
polygon(x = c(rif_dens$x[c(x1, x1:x2, x2)]), y = c(0, rif_dens$y[x1:x2], 0), col = "gray")
abline(v = mean(riffles), lty = 2)

Om matematikken bag kvantetransport

Når man zoomer ind på atomart-niveau, ser verden helt anderledes ud. Den består af små partikler, som vekselvirker med hinanden, og deres egenskaber er vidt forskellige fra alt det, som vi kender fra vores “egen størrelse”.

En af de mest effektive metoder, som er brugte til at forstå den elektroniske struktur af et givet stykke materiel, er at løbe en elektrisk strøm gennem det. Når dette stykke består af ganske få atomer, for at få ledningsprocessen ordenligt modelleret er man nødt til at bruge avancerede matematiske evolutionsligninger som Schrödingers eller Liouvilles.

I næste uge skal vi afholde en lille wokshop på instituttet, der skal samle på et sted flere førende forskere fra hele verden. Foredragsholderne tæller eksperter i matematisk-fysik, numerisk analyse og modellering. Målet er at kigge sammen (dog fra ganske forskellige synsvinkler) på det der er sket nyt i dette spændende forskningsområde. Nogle nøgleord er: spin og ledningstransport i topologiske isolatorer, Wannier funktioner i metalliske systemer, spredningsteori for langtrækkende vekselvirkninger m.fl.

Workshoppens hovedsponsor er DFF1 bevillingen 4181-00042 fra Det Frie Forskningsråd | Natur og Univers.

Ford-cirkler – og addition af brøker som vor mor IKKE gør det.

Vælg to hele tal p og q, som er parvis primiske (det eneste tal, der går op i både p og q er tallet 1). Tegn cirklen i planen med radius $\frac{1}{2q^2}$ og centrum i $(\frac{p}{q},\frac{1}{2q^2})$ . Bed nu en anden om at gøre det samme – med nyt valg af p og q. De to cirkler vil tangere x-aksen og enten tangere hinanden eller ikke have noget til fælles. Bliv ved og der opstår et fint mønster af cirkler. De kaldes Ford-cirkler, fordi de blev beskrevet i en artikel i American Mathematical Monthly i 1938 af Lester R. Ford Sr.

Notation: Fordcirklen svarende til p,q kaldes C(p,q).

Her på figuren er valgt $p\leq q$ , så $0\leq \frac{p}{q}\leq 1$ og dermed er x-koordinaten for centrum mellem 0 og 1. Tallet i cirklen er x-koordinaten for centrum (forkortet, så det svarer til p/q). Farven indikerer nævneren p.

Her er nogle konstateringer:

Ethvert rationalt tal a/b på x-aksen bliver rørt af en Fordcirkel: Forkort a/b og lav så Fordcirklen.
Radius og dermed højde af C(p,q) afhænger kun af q.

To Fordcirkler skærer ikke hinanden:

To Fordcirkler C(p,q) og C(r,s) vil enten tangere (kysse kaldte jeg det i indlægget om kuglepakninger) eller slet ikke røre hinanden:

De har centrum i hhv. $(\frac{p}{q},\frac{1}{2q^2})$ og $(\frac{r}{s},\frac{1}{2s^2})$ så afstand mellem centrene opfylder

$d^2=(\frac{p}{q}-\frac{r}{s})^2+(\frac{1}{2q^2}-\frac{1}{2s^2})^2$

Summen af de to radier er $s=\frac{1}{2q^2}+\frac{1}{2s^2}$

Nu sammenligner vi d og s ved at udregne $d^2-s^2$ . Hvis de to cirkler skærer hinanden er $d^2-s^2<0$ . Tangerer de, er $d^2-s^2=0$ .

$d^2-s^2$ = $(\frac{p}{q}-\frac{r}{s})^2+(\frac{1}{2q^2}-\frac{1}{2s^2})^2-(\frac{1}{2q^2}+\frac{1}{2s^2})^2$ = $(\frac{p}{q}-\frac{r}{s})^2- 4(\frac{1}{2q^22s^2})$ = $(\frac{ps-rq}{qs})^2- (\frac{1}{q^2s^2})$ = $\frac{(ps-rq)^2-1}{(qs)^2}$

Forskellige Fordcirkler skærer ikke:

Hvis de to cirkler skærer, er
$( ps - rq )^2 - 1<0$ og altså $( ps - rq )^2 <1$

Men ps – rq er et helt tal, så det vil kræve
ps – rq = 0 og altså ps = rq ,
så $\frac{p}{q}=\frac{r}{s}$
og altså er det samme cirkel.

Fareyfølger.

Hvis C(p,q) og C(r,s) tangerer, er |ps-rq|=1. Det leder til en anden pudsig observation. men først skal vi have indført brøkregning a la Farey:

Dette er de første Fareyfølger

$F_1=\frac{0}{1},\frac{1}{1}$
$F_2=\frac{0}{1},\frac{1}{2}, \frac{1}{1}$
$F_3=\frac{0}{1},\frac{1}{3},\frac{1}{2},\frac{2}{3}\frac{1}{1}$
$F_4=\frac{0}{1},\frac{1}{4},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{3}{4},\frac{1}{1}$
$F_5=\frac{0}{1},\frac{1}{5},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{4}{5},\frac{1}{1}$

Fareyfølgen $F_n$ er uforkortelige brøker mellem 0 og 1 med nævner højst n. Rækkefølgen er efter størrelse. De elementer, der tilføjes til $F_n$ for at få $F_{n+1}$ er medianten af naboerne:

I $F_5$ tilføjes $\frac{2}{5}$ . Naboerne er $\frac{1}{3},\frac{1}{2}$ . Medianten er dårlig brøkregning, Fareyplus:

$\frac{1}{3}\oplus\frac{1}{2}=\frac{1+1}{3+2}=\frac{2}{5}$

Her er det tilsvarende for Fordcirklerne

Hvorfor gælder det? Her er først nogle konstateringer:

Hvis $0<\frac{a}{b}<\frac{c}{d}<1$ ligger medianten imellem dem $\frac{a}{b}<\frac{a+c}{b+d}<\frac{c}{d}$ . Man viser det første ulighedstegn som følger: $\frac{a}{b}<\frac{a+c}{b+d}$ $\Leftrightarrow$ $(b+d)a<(a+c)b \Leftrightarrow da<cb$ og det følger af $\frac{a}{b}<\frac{c}{d}$ .
Medianten mellem to naboer i $F_k$ tilføjes i skridtet fra $F_n$ til $F_{n+1}$ , når nævneren den forkortede brøk svarende til $\frac{a+c}{b+d}$ er højst n+1.
Medianten af to naboer i en Fareyfølge $F_k$ er uforkortelig: Medianten er ikke i $F_k$ , da $\frac{a}{b}, \frac{c}{d}$ er naboer. Antag $\frac{a+c}{b+d}=\frac{rq}{rp}$ og $\frac{q}{p}$ er uforkortelig. Så er p>k, da medianten ikke er i $F_k$ . rp=b+d og $b+d\leq 2k$ . Altså er r=1.

Medianten tilføjes altså i skridtet fra $F_{b+d-1}$ til $F_{b+d}$ .

Nu mangler vi blot at se, at alle uforkortelige brøker kommer med i en proces, hvor vi begynder med $\frac{0}{1},\frac{1}{1}$ og tilføjer medianter.

Stern Brocot-træet.

Lad os undlade at holde styr på, hvor store nævnerne er. Så bygger vi Stern-Brocot-træet (opkadt efter Moritz Stern, matematiker, og Achille Brocot, urmager (!) ):

Vi bruger kun den venstre side. De stiplede linjer hjælper til at se, hvad der tages medianter af, men et lag eller “niveau” er kun de sidst tilkomne.

Påstand: Alle uforkortelige brøker kommer med i et lag i træet. (Og det er derfor ok at konstruere Fareyfølger via medianter.)

Først er hjælperesultat: Hvis $\frac{a}{b} < \frac{c}{d}$ er barn og forælder eller forælder og barn i træet (forbundet med en kant opad eller nedad fra $\frac{a}{b}$ til $latex \frac{c}{d}$, så er $bc-ad=1$ . Bevis: Induktion. Det er ok for 0/1 og 1/1. Hvis ok for $\frac{a}{b} < \frac{c}{d}$ , så er det ok for kanter til og fra medianten: Der er enten en kant nedad mellem $\frac{a}{b} < \frac{a+c}{b+d}$ eller opad $\frac{a+c}{b+d}<\frac{c}{d}$ .
$b(a+c)-a(b+d)=bc-ad=1$ pr antagelse. Og tilsvarende for den anden side. (Lav selv et særargument for medianterne med hhv. 0/1 og 1/1.) En konsekvens er, at afstanden er $|\frac{a}{b} - \frac{c}{d}|=\frac{1}{bd}$ .

Argument for, at alle uforkortelige brøker er med i Stern-Brocot-træet: : På det k’te niveau i træet er summen af nævner og tæller i brøkerne mindst k+2, da Niveau k fremkommer som medianter fra niveau k-1 og højere niveauer. (Der laves hele tiden medianter med 0/1 og 1/1).

Antag nu, at p/q ikke er med i træet. Specielt er den ikke med på niveau p+q-1. Men den ligger mellem to naboer (forbundet med en kant), hvor den ene er på niveau p+q-1: $\frac{a}{b} <\frac{p}{q}< \frac{c}{d}$ . Omskriv de to uligheder til

$bp-aq>0$ og $cq-dp>0$ . Det er hele tal, så vi kan skrive $\geq 1$ begge steder.

Heraf: $(bp-aq)(c+d)+(cq-dp)\geq c+d+a+b\geq p+q+1$ (Det sidste følger af, at den ene brøk er fra niveau p+q)

Udregn venstresiden og brug bc-ad=1, da disse er forælder og barn i træet. Venstresiden giver da p+q. Og vi har en modstrid.

Tilbage til Fordcirklerne:

To Fordcirkler C(p,q) og C(r,s) tangerer hvis og kun hvis |ps-rq|=1. Altså svarer brøker, som er naboer i en Fareyfølge til tangerende Fordcirkler. Og det gælder også omvendt, men det har vi ikke vist her.

Endnu et pænt billede. His Fordcirklerne skærer, så vil halvcirklen fra (p/q,0) til (r/s,0) passere skæringspunktet. Farven på halvcirklerne svarer til den Fareyfølge, hvori brøkerne er naboer.

God grafik – og Ihaka-foredrag

I dette indlæg vil jeg først vise noget grafik. Sidst i indlægget vil jeg give nogle links til nogle gode foredrag om grafik.

DR.dk bringer i dag artiklen “Ny måling: Danskerne har mest sympati med lønmodtagerne“. I den er der følgende graf:

(Kilde: DR.dk “Ny måling: Danskerne har mest sympati med lønmodtagerne“)

Min umiddelbare reaktion var: “Den graf er godt nok svær at tyde!”.

Der er flere problemer med den. For det første er cirkeldiagrammer/lagkagediagrammer svære at tyde – forstået på den måde, at det er svært at sammenligne størrelsen på de forskellige “lagkagestykker”. Hvor mange gange større er et stykke i forhold til et andet stykke? For det andet er farvevalget måske ikke velegnet til denne type graf, hvis man gerne vil bruge den til at illustrere forholdene mellem de forskellige svarmuligheder. Man kan (meget groft) dele farveskalaer op i to grupper: sekventielle (fra lyseblå til mørkeblå, fra rød til grøn osv.) eller kvalitative. De sekventielle bruges ofte til at illustrere en talværdi (fx indkomst) og de kvalitative bruges ofte til grupper (fx køn eller region).

Så alt i alt er grafen svær at tyde pga. både typen og farvevalget. Det skal dog siges, at man inde på artiklen kan køre musen over “lagkagestykkerne” for at få hjælpetekst og andelen oplyst. (Men man kan spørge om interaktivitet virkelig er nødvendig til at illustrere dette data.)

Til denne type grafer, vil man typisk anvende søjlediagrammer som fx:

Her er et par varianter. Først hvor søjlerne ordnes efter værdi:

Og vil man gerne have farver på, kan man da godt det:

Jeg vil påstå, at sådanne grafer er bedre til at hjælpe mig med at sammenligne svarmulighederne end cirkeldiagrammet er.

Det leder frem til det næste: Der er meget psykologi i grafik. Det handler ikke kun om statistik og om rent teknisk at få produceret noget grafik.

Og det er svært at lave god grafik!

Der forskes stadigvæk i, hvordan grafik tolkes – og om der er forskel mellem folkeslag. Fx er farver en oplagt del af grafik: Men man kan være farveblind og det kan man endda være på mange måder. Derfor er det vigtigt at producere grafik som også farveblinde kan læse – men det er ikke let. Og der kan muligvis også være forskel på, hvordan forskellige kulturer opfatter farver.

Auckland University (i New Zealand) har afholder hvert år en foredragsrække kaldet Ihaka lectures. Den blev første gang afholdt i 2017 og hver række består af 3 foredrag i marts måned. I år var der følgende tre foredrag:

“Myth busting and apophenia in data visualisation: is what you see really there?” med Dianne Cook. Link til foredraget på YouTube.
“Making colour accessible” med Paul Murrell. Link til foredraget på YouTube.
“Visual trumpery: How charts lie – and how they make us smarter” med Alberto Cairo. Link til foredraget på YouTube.

Alle disse tre foredragsholdere er kendte og gode. Jeg vil ikke bruge tid på at præsentere dem hver især her. Se i stedet deres foredrag. Men de alle illustrerer fint det sammenspil der er mellem statistik og psykologi når man laver visualiseringer/illustrationer/grafik.

Relateret til dette indlæg er måske specielt nr. 3 af Alberto Cairo. Han giver en masse gode eksempler på dårlig grafik. Ikke nødvendigvis åbenlys dårlig grafik, men grafik der kan vildlede læseren.

Di Cook (nr. 1 ovenfor) forklarer i sit foredrag også om, hvordan kan kan bruge visualiseringer til statistisk inferens i stedet for den traditionelle tilgang med hypotesetest. De har lavet forsøg med at lade folk vurdere visualiseringer, der er lavet med udgangspunkt i nulhypotesen og så se om folk kan genkende det observerede datasæt. Hvis de kan det, “stikker det ud” og kommer så måske ikke fra den model, man har specificeret i nulhypotesen. Der er muligvis nogle problemer med denne tilgang – fx er det ikke åbenlyst hvad den alternative hypotese er. Derudover er det svært at vælge teststatistik/teststørrelse (der i dette tilfælde svarer til typen af grafik brugeren skal vurdere, fx scatterplot, barplot osv.). Men det er bestemt interessant at høre om denne vinkel på statistisk inferens.

Langlands får Abelprisen 2018 for at stille gode og dybe spørgsmål.

I 1967 skrev den dengang 31-årige Robert P.Langlands et 17 sider langt brev til André Weil. Weil var 30 år ældre og en af den tids store og indflydelsesrige matematikere. De to mødte hinanden, da de ventede på at komme ind til et foredrag, Langlands gav sig til at fortælle om nogle ideer og Weil foreslog ham at skrive dem ned. Måske for at slippe væk… Weil inviterede desuden Langlands til at besøge ham på Institute of Advanced Studies, Princeton og det lange brev skrev han inden besøget. Billedet her viser, hvad Langlands skrev på forsiden: ”In response to your invitation to come and talk I
wrote the enclosed letter. After I wrote it I realized
there was hardly a statement in it of which I was certain.
If you are willing to read it as pure speculation
I would appreciate that; if not – I am sure you have
a waste basket handy.”

Weil fik renskrevet de 17 sider – på skrivemaskine – og det er det, derblandt matematikere kaldes Langlandsprogrammet.

Nu får Langlands Abelprisen for sine “spekulationer”! Han har naturligvis selv bevist matematiske resultater, men priskomitéen skriver, han får prisen for “sit visionære program, der forbinder repræsentationsteori og talteori.”

Langlands på en konference i 2016. (Dan Komoda/Institute for Advanced Study)

Langlandsprogrammet indeholder nogle formodninger (conjectures) og et program for, hvordan man bør kunne bevise, at disse er korrekte. Det drejer sig om nogle forbindelser mellem områder af matematik, som ellers er ret forskellige i både emneområde og metoder. Den slags forbindelser giver sædvanligvis anledning til rigtig mange nye indsigter i begge områder. Lad mig forsøge at kaste lys på et lille hjørne af, hvad det går ud på:

Nogle primtal kan skrives som en sum af to kvadrattal:

$2= 1^2+1^2$
$5= 1^2+2^2$
$13=2^2+3^2$
$17=1^2+4^2$
$29=2^2+5^2$

Hvis man ser bort fra 2 (vi skriver “for et ulige primtal”, men der betyder jo bare, at 2 ikke er med) har alle disse primtal en fælles egenskab: Et primtal p, som ikke er 2, kan skrives som en sum af to kvadrattal hvis og kun hvis $p=4k+1$ , hvor k er et naturligt tal. Det beviste Euler. Det er et eksempel på en reciprocitetslov – en egenskab ved primtallene udtrykkes ved division med rest . Her er det division med 4, som skal give rest 1. Vi skriver $p\equiv 1 \mod 4$

Et komplekst tal $a+bi$ kaldes et Gaussisk heltal, hvis $a,b$ er hele tal. Hvis $p=m^2+n^2$ , så er $(m+in)(m-in)=p$ ( husk, $i^2=-1$ og så er resten givet ved at gange ind i paranteser) og omvendt. Et primtal p er et produkt af to Gausisske heltal hvis og kun hvis det er en sum af to kvadrattal.

De Gaussiske rationale tal er tal $a+bi$ , hvor a og b er rationale tal (kan skrives som en brøk $\frac{c}{d}$ , hvor c og d er hele tal. Ganger, dividerer, adderer eller subtraherer man to Gaussiske rationale tal med hinanden, er resultatet rationalt. De Gaussiske rationale tal udgør derfor ikke bare en delmængde $\mathbb{Q}(i)$ af de komplekse tal, men et legeme. Man kan se det som en udvidelse af de rationale tal – man tilføjer $i$ og reglen $i^2=-1$ og “beholder” regnereglerne. Det kaldes en legemsudvidelse.

Nu ser vi på symmetrier.
Hvilke afbildninger har vi $f:\mathbb{Q}(i)\to \mathbb{Q}(i)$ , som er lineære: f((a+bi)+(c+di))=f(a+bi)+f(c+di) og bevarer produktstrukturen f((a+bi)(c+di))=f(a+bi)f(c+di) og desuden opfylder f(a+0i) = a+0i. Der er kun to afbildninger: Identitetsafbildningen f(a+bi)=a+bi og g(a+bi)=a-bi.

Da g(g(a+ib))=a+ib (man får skiftet fortegnet to gange), udgør funktionerne f og g en gruppe og g har orden 2 – sammensæt den med sig selv to gange, så får man identiteten.Det er Galoisgruppen for legemsudvidelsen $\mathbb{Q}(i)$ over $\mathbb{Q}$ .

Tilsvarende kan man se på Galoisgruppen for andre udvidelser af de rationale tal. Tænk på $\mathbb{Q}(i)$ som en udvidelse af $\mathbb{Q}$ med rødder i $x^2+1$ og dermed kvadratrødder af alle negative rationale kvadrattal. Vi ved, at alle andengradspolynomier $ax^2+bx+c$ med rationale a,b,c, har to rødder (mere præcist, kan skrives $a(x-r_1)(x-r_2)$ med $r_1,r_2\in \mathbb{R}(i)$ og en formel for disse rødder kan skrives blot med brug af kvadratrodssymbolet.

Alle tredjegradspolynomier med rationale koefficienter $x^3+ a_2x^2+a_1x+a_0$ har rødder, som kan opskrives ved brug af kvadratrødder og kubikrødder. Tilsvarende for 4.gradspolynomier, når man tilføjer fjerde rødder. Men for femtegradspolynomier går det galt. Det viste Abel og Galois. Det er altså ikke nok at kunne løse ligninger $x^5=a$ for at kunne løse alle femtegradspolynomieligninger. Det mere generelle spørgsmål er, om der er en sammenhæng mellem løsninger til et polynomium $P(x)$ og et andet $Q(x)$ .

Man kan formulere resultatet om primtal som sum af kvadrattal via Galoisgrupper. For et (ulige) primtal p er $i^p=i$ , hvis $p\equiv 1\mod 4$ og $i^p=-i$ , hvis $p\equiv 3\mod 4$ . Funktionen $z\to z^p$ kaldes en Frobeniusafbildning og er et element af Galoisgruppen. Frobeniusafbildningen er forbindelsen mellem “kan man skrive p som en sum af to kvadrattal” og “hvad er $p \mod 4$ “.

Tilsvarende spørgsmål. Polynomiet $x^2+x+1$ har rod 1, når man regner modulo 3, da $1^2+1+1=3\equiv 0\mod 3$ . Men 1 er ikke en rod modulo 5. Hvor meget information er der i, at kende antallet af rødder modulo primtal? Og hvad har det med Galoisgrupper at gøre?

Langlandsprogrammet foreslår en vidtrækkende generalisering af dette.

Det giver en forbindelse mellem harmonisk analyse – automorfe former, som er funktioner fra de komplekse tal til de komplekse tal med visse periodicitets egenskaber – og rødder i polynomier undersøgt via regning med rest som ovenfor. Andrew Wiles brugte en forbindelse af den type, da han løste Fermats problem.

Jeg har støttet mig til dels informationen på Abelprissiderne nogle noter fra et foredrag at Laurent Lafforgue, som fik Fieldsmedaljen for sit arbejde med Langlandsprogrammet og diverse populariseringer.

Grisecykler og differensligninger.

Cykler og cyklisk betyder her perioder og periodisk opførsel. Men der er faktisk et begreb i økonomi, som hedder “The Pork cycle” eller “The hog cycle” og det giver vel hos de fleste indre billeder af grise på cykel. Inden vi går videre, skal I have sådan en gris:

Billedresultat for buon compleanno in ritardo

I økonomi er det en anden historie: Med en meget simpel model, afhænger efterspørgslen efter grise(kød) (kun) af prisen og det gør udbuddet også. Der er to funktioner D er “demand”, efterspørgsel, S er “supply”, udbud og de er funktioner af prisen p: D(p) og S(p).

Men prisen varierer jo med tiden, så det er ikke hele historien. Her lader vi tiden gå i “hop” og altså gør priserne det også: $p_1, p_2,\ldots, p_{n-1}.p_n,\ldots$ Og naturligvis udbud og efterspørgsel: $S_1,S_2,\ldots,S_{n-1},S_n,\ldots$ og $D_1,D_2,\ldots,D_{n-1},D_n,\ldots$ .

Man kan lade hvert hop svare til en time, en dag, en uge, en måned eller hvad der nu passer i modellen.

Nu kan vi så skrive $D_n=f(p_n)$ for at indikere at efterspørgslen idag afhænger af prisen idag. Men udbuddet af grise kan ikke afhænge af prisen idag. Den kendte griseavleren ikke, da hun besluttede, hvor mange grise, der skulle produceres. Med en passende periode (den tid, det tager at få en gris klar til salg) kan vi skrive $S_n=g(p_{n-1})$ – udbuddet idag afhænger af prisen i forrige periode.

Hvad kan vi mere sige om funktionerne $f$ og $g$ ? Las os gå ud fra, de er differentiable funktioner af en variabel $f,g:\mathbb{R}\to \mathbb{R}$ , hvor input er pris og output er mængden af grisekød – i kilo eller en anden passende enhed. Højere pris giver mindre efterspørgsel og mere udbud, så $f'(x)<0$ og $g'(x) >0$ . Der er eksempler på varer, hvor det ikke er rigtigt – basale fødevarer, som er forholdsvis billige er et eksempel. Men det er en model, så nu går vi med den.

Her er en graf (fra Wikipedia, Creative Commons) med de to funktioner

Bemærk, at prisen er op ad andenaksen, mens mængden er på førsteaksen. Efterspørgsel er den røde kurve, udbud er den blå.

Pilene indikerer et tidsforløb: Griseavleren ved, at grisene til tid 1 er blevet solgt til prisen $p_1$ og sætter gang i produktion af $g(p_1)=Q_2$ grise. De udbydes til salg og man må forestille sig en slags auktion, hvor der nu er $Q_2$ grise, som give prisen $p_2=f^{-1}(Q_2)$ .

Det ser griseavleren og producerer så $g(p_2)=Q_3$ grise til salg. De går til prisen $p_3$ . Fortsætter man pilene rundt, kan man se, prisen svinge ind mod den pris, der svarer til skæringspunktet mellem de to kurver – den kaldes ligevægtsprisen.

Men det kunne også være gået anderledes:

Her vil prisen svinge længere og længere væk fra ligevægtsprisen. Modellen er en cobweb-model; det ligner et spindelvæv, hvis man tager flere ture rundt. Svingningen i priser er den såkaldte grisecykel.

Det afhænger tydeligvis af funktionerne $f$ og $g$ , om det går mod eller væk fra ligevægt. Det kan skrives op med en differensligning:

$S_n=D_n$ og altså $f(p_n)=g(p_{n-1})$ . Nu simplificerer vi yderligere og lader begge funktioner være lineære:

$f(x)=a+bx$ og $g(x)=c+dx$ , hvor $a>0, b<0,d>0$ og $a>c$ . c kan godt være negativ – måske produceres der ikke grise, hvis prisen er for lav.) Så bliver ligningen $a+bp_n=c+dp_{n-1}$ , som kan omskrives til

$bp_n-dp_{n-1}=c-a$

Skæringspunktet, ligevægtsprisen, er $\bar{p}=\frac{c-a}{ b-d}$ .

Sådan en førsteordens differensligning kan man løse. Generelt ser det sådan ud – vi ser på løsninger til differensligningen

$k_1y_n+k_2y_{n-1}=\varphi(n)$ med $k_1\neq 0$ og omskriver til $y_n+ky_{n-1}= h(n)$

Løs det tilhørende homogene problem $y_n+ky_{n-1}= 0$ . Løsningen er $latex y_n=(-k)^nA$ – det er ikke svært at se, at det er en løsning, uanset A, og at der ikke er andre. (Et induktionsbevis kan gøre det. Ikke noget fancy som for differentialligninger.)
Nu finder man en partikulær (altså bare en) løsning til det inhomogene problem. I vores tilfælde, hvor $h(n)$ er konstant, har vi fundet ligevægtsløsningen $\bar{y}$ .
Den generelle løsning er nu, som vi kender det fra differentialligninger, $y_n =A(-k)^n+\bar{y}$

Det bruger vi for $bp_n-dp_{n-1}=c-a$ – omskriv til $p_n+\frac{-d}{b}p_{n-1}=\frac{c-a}{b}$ og får

$p_n=A(\frac{d}{b})^n+\bar{p}$

Da $\frac{d}{b}<0$ , vil $p_n$ svinge omkring $\bar{p}$ . Hvis $d<b$ svinger det ind mod $\bar{p}$ , hvis $d=b$ svinger det frem og tilbage mellem de samme to værdier (grafen i midten nedenfor) og $d>b$ giver svingning væk fra ligevægten. Man kan selvfølgelig finde $A$ , hvis man kender en begyndelsesbetingelse. Kender man $p_ 0$ , er $A= p_0-\bar{p}$

Billedresultat for cobweb model

Man kan lege med andre forventede priser. Ovenfor tror griseavleren, prisen holder fra en periode til den næste og det synes lidt naivt… Måske ser producenterne på prisen i de to seneste perioder og så får man en andenordens differensligning. Mere generelt er adaptive forventninger det, at man lærer af, hvor meget, man skød forkert i de seneste perioder. Der findes naturligvis mere generelle modeller og prisdannelse på andre markeder såsom ejendomsmarkedet.

Hvor kommer DNA profilen fra?

De såkaldte Ancestry Informative Markers (AIMs) er genetiske markører som indeholder en høj grad af information omkring en persons genogenetiske ophav. Med genogenetisk menes der genetiske markører som relaterer sig til geografisk lokation af subpopulationer. Vi ved at mange fænotypiske træk (fx hud- og hårfarve) er defineret af genetiske markører, mens andre markører ikke nødvendigvis manifesterer sig i umiddeltbart synlige træk.

Det humane genom består af over 3 milliarder nukleobaser angivet ved bogstaverne A, C, G og T. Store dele af genomet er identisk for alle mennesker – idet dette netop gør os til homo sapiens. Den simpleste form for afvigelser er de såkaldte Single Nucleotide Polymorphisms (SNPs), som er enkelt position på genomet hvor fx mindst 1% af populationen har en alternativ base. Fx kunne A være den oprindelige tilstand for en markør mens C er en muteret tilstand. Sådanne markører er interessante fra et populationsgenetisk synspunkt idet fx alle afrikanere kunne have genotypen AA (et A fra mor og et A fra far) mens alle asiater er CC. Ved at benytte informationen fra flere af sådanne markører er det muligt at fastslå hvor det er mest sandsynligt at person kommer fra.

I retsgenetik, som er disciplinen hvor DNA benyttes i en retlig sammenhæng (fx straffe-, faderskabs- og familiesammenføringssager), rapporteres beviset typisk i form af et likelihood ratio, dvs. man evaluerer hvor sandsynligt bevismaterialet (her DNA profilen) er under to stridende hypoteser. Lad $E$ være bevismaterialet ( $E$ for evidence, mens $H_A$ er hypotesen at DNA profilen stammer fra Afrika, mens $H_E$ er hypotesen at profilen stammer fra Europa. I forhold til at vurdere om bevismaterialet taler for et europæisk ophav frem for et afrikansk, kan vi bestemme likelihood ratioet, $LR_{EA}$ ,
$LR_{EA} = \dfrac{P(E \mid H_E)}{P(E \mid H_A)},$
hvor $P(E \mid H_E)$ er sandsynligheden for $E$ hvis $H_E$ er sand, og tilsvarende for $P(E \mid H_A)$ hvis $H_A$ er sand. Typisk estimeres disse sandsynligheder ud fra en stikprøve fra hhv.\ de europæiske og afrikanske populationer. Hvis vores estimater gav $LR = 10^4 = 10000$ betyder det at det er titusind gange mere sandsynligt at se profilen i den europæsiske population frem for den afrikanske.

Problemet vi har fokuseret på i vores forskning (link til artikel i Theoretical Population Biology) er hvorledes man håndterer situationen hvor en konkret DNA profil stammer fra en subpopulation hvor fra vi endnu ikke har en stikprøve af DNA profiler. Fx hvis profilen $E$ stammer fra Grønland, men hvor vi kun har data fra Afrika og Europa. Hvad ville det give af information at vide en given profil er titusind gange mere sandsynlig i Europa end i Afrika når begge hændelser er ekstremt usandsynlige? I dette tilfælde, lad os antage at profilens hyppighed i Grønland er $P(E\mid H_G) = 10^{-2} = 0.01$ mens i Europa $P(E\mid H_E = 10^{-100}$ og Afrika er $P(E\mid H_A = 10^{-104}$ (således at $LR_{EA} = 10^{4}$). Idet vi konkret ikke kender til den Grønlandske hyppighed (vi antager at vi ikke har en stikprøve derfra) kan vi ikke bestemme hyppigheden relativt i forhold til den grønlandske.

At den relative hyppighed er stor betyder ikke nødvendigvis at DNA profilen stammer fra populationen med den største profil-sandsynlighed. Vores løsning var at fokusere på hvornår er en profil for sjælden i en given population? I statistiske termer kan dette oversættes til: er profilen en outlier i den givne population? Denne tilgang gør det muligt at konkludere at der ikke findes en relevant population i det tilgængelige reference materiale. Fx hvis en given profil bliver erklæret outlier i samtlige tilgængelige populationer konkluderes det at profilen stammer fra en endnu ikke undersøgt population (eller evt. har et mere kompliceret genetisk ophav – fx med forældre med vidt forskellige genogenetiske baggrund).

På kortet nedenfor ses lokationen for de populationer som er inkluderet i reference materialet. Farven af hvert punkt angiver om profilen er blevet erklæret som outlier (blå) eller ej (rød). Profilen er i dette tilfælde fra Grønland og konklusionen er derfor korrekt.

Lokation af populationerne. Farven indikerer beslutning omkring outlier (blå) eller ej (rød)

I plottet herunder vises profil hyppighederne for de forskellige populationer. Igen er det tydeligt at profilen er hyppigst forekommende i Grønland, $P(E\mid H_G) = 10^{-37}$ hvor de nærmeste populationer har hyppigheder omkring $10^{-46} - 10^{-50}$ . Altså er profilen omkring $10^{10}$ mere sandsynlig i Grønland i forhold til disse populationer.

Genotype sandsynligheder af den grønlandske profil. Punkterne er estimatet og linjer angiver usikkerheder.

Summen af de reciprokke primtal er uendelig.

Hilberts hotel, som tidligere flygtigt er blevet nævnt på denne blog, er en pædagogisk model til illustrering af begrebet uendelighed. Hotellet har (tælleligt) uendeligt mange værelser og kan derfor rumme (tælleligt) uendeligt mange gæster. Normalt, når man diskuterer Hilberts hotel, bekymrer man sig om, hvordan man får plads til flere gæster, hvis alle værelser er optagede. En anden bekymring kunne gå på, hvordan man dog får bespist alle disse gæster.

Her er en mulig løsning: Lav en kæmpe grydefuld suppe. Gæsterne kan nu efter tur tage suppe, dog må de højst tage halvdelen af grydens indhold. På den måde er der suppe til alle, omend første gæst nok får mere suppe end gæst nummer én milliard. Hvis vi i det følgende regner i enheden grydefuld suppe, så kan første gæst højst få 1/2, hvorefter gæst nummer to højst kan tage 1/4, gæst nummer tre højst 1/8 osv. Tager første gæst 1/2, er der 1/2 tilbage, tager anden gæst 1/4, er der 1/4 tilbage osv., så der efter den $n$ ’te gæst, som tager $\frac{1}{2^n}$ , er $\frac{1}{2^n}$ tilbage, og der vil således ikke være noget tilbage, når alle gæster har taget. Lægger vi disse tal sammen, får vi altså hele grydens indhold:

$1=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{16}+\frac{1}{32}+\dotsb$
eller, som den velopdragne matematiker ville skrive:

$\displaystyle \sum_{n=1}^\infty\frac{1}{2^n}=1$
Vi kan altså lægge uendeligt mange tal sammen og få noget endeligt. Det er klart, at dette kun kan lade sig gøre, fordi leddene i summen bliver mindre og mindre jo længere ud i summen, vi når. Det er dog ikke et tilstrækkeligt krav på leddene, hvis vi ønsker at en sum skal være endelig, som følgende eksempel illustrerer.

Antag, at første gæst har én kubikmeter bagage med, den næste en halv kubikmeter bagage, den tredje en tredjedel kubikmeter bagage og så fremdeles, således at den $n$ ’te gæst har $\frac{1}{n}$ kubikmeter bagage. Kan alle gæsternes bagage være i ét (endeligt) stort rum? Vi kan begynde med at se lidt på, hvor meget plads de første $2N$ gæsters bagage fylder, hvor $N$ er et eller andet (stort) tal. Kald det samlede antal kubikmeter for $S_{2N}$ , så har vi at:

$\displaystyle \begin{array}{rl}\displaystyle S_{2N}\!\!\!&=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\dotsb+\frac{1}{2N-1}+\frac{1}{2N}\\&=\frac{1}{2}+(\frac{1}{2}+\frac{1}{2})+(\frac{1}{3}+\frac{1}{4})+(\frac{1}{5}+\frac{1}{6})+\dotsb+(\frac{1}{2N-1}+\frac{1}{2N})\end{array}$
Bemærk, at $\frac{1}{2n-1}+\frac{1}{2n}>\frac{1}{2n}+\frac{1}{2n}=\frac{1}{n}$ , for $n=1, 2, 3, \dotsc$ . Vi får derfor følgende vurdering.

$\displaystyle \begin{array}{rl}S_{2N}\!\!\!&=\frac{1}{2}+(\frac{1}{2}+\frac{1}{2})+(\frac{1}{3}+\frac{1}{4})+(\frac{1}{5}+\frac{1}{6})+\dotsb+(\frac{1}{2N-1}+\frac{1}{2N})\\&>\frac{1}{2}+\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\dotsb+\frac{1}{N}=\frac{1}{2}+S_N,\end{array}$
hvor $S_N$ er det samlede antal kubikmeter for de første $N$ gæsters bagage. Vi har nu vist at

$S_{2N} >\frac{1}{2}+S_N$ ,

og kan konkludere, at al bagagen ikke kan være på endeligt megen plads: hver gang, vi fordobler antallet af gæster, vi tager bagagen fra, får vi brug for mere end en halv kubikmeter mere plads! Har vi 100 kubikmeter, løber vi altså helt sikkert tør for plads efter 200 fordoblinger af antallet af gæster, og har vi $K$ kubikmeter, løber vi tør efter $2K$ fordoblinger. Den førnævnte velopdragne matematiker ville skrive

$\displaystyle \sum_{n=1}^\infty\frac{1}{n}=\infty,$
til trods for, at $\frac{1}{n}$ også går mod $0$ , når $n$ går mod $\infty$ . Grunden til at $\sum_{n=1}^\infty\frac{1}{2^n}$ er endelig mens $\sum_{n=1}^\infty\frac{1}{n}$ er uendelig, er kort fortalt at $\frac{1}{2^n}$ går meget hurtigt mod $0$ mens $\frac{1}{n}$ går noget langsommere mod $0$ , når $n$ går mod $\infty$ . Tilsvarende: $2^n$ går hurtigere mod $\infty$ end $n$ går mod $\infty$ , når $n$ går mod $\infty$ .

Som Lisbeth har nævnt i et tidligere blogindlæg, så har vi siden Euklid vidst, at der findes uendeligt mange primtal. Ser vi på de første tal i følgerne af tal på formen $n$ og $2^n$ samt følgen af primtal,

$\begin{array}{ll}&1, 2, 3, 4, 5, 6, 7, 8, 9, 10, \dotsc\\&2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, \dotsc\\&2, 3, 5, 7, 11, 13, 17, 19, 23, 29,\dotsc\end{array}$
er det klart, at primtalsfølgen vokser noget hurtigere end følgen af naturlige tal, men også at den (i hvert fald i begyndelsen?) vokser meget langsommere end følgen af toerpotenser. Man kunne derfor spørge sig selv om, om summen $\sum_{i=1}^\infty\frac{1}{p_i}$ , hvor $p_i$ betegner det $i$ ’te primtal, er endelig eller ej? Vi vil i det følgende give et bevis for, at det sidste er tilfældet. Beviset er ret kort, hvis ellers man vil acceptere et par relativt simple resultater som bruges undervejs.

Først bemærker vi, at ethvert naturligt tal $n$ kan skrives entydigt på formen

$n=p_1^{m_1}p_2^{m_2}\dotsb p_n^{m_n}$ ,

hvor $p_i$ er det $i$ ’te primtal og $m_i$ er en potens mellem $0$ og $n$ , hvor vi husker, at $p^0=1$ uanset $p$ (i hvertfald så længe $p\ne0$ ). Produktet kunne også skrives $n=\prod_{i=1}^n p_i^{m_i}$ , hvor produkttegnet $\prod$ defineres ved $\prod_{i=1}^nq_i=q_1 q_2\dotsb q_n$ . Vi illustrerer med de første fire naturlige tal:

$\begin{array}{rl}1&=2^0\\2&=2^1\cdot 3^0\\3&=2^0\cdot 3^1\cdot 5^0\\4&=2^2\cdot 3^0\cdot 5^0\cdot 7^0,\end{array}$
osv. Betragt nu udtrykket

$\displaystyle \prod_{i=1}^N\sum_{j=0}^N p_i^j=(p_1^0+p_1^1+p_1^2+\dotsb+p_1^N)(p_2^0+p_2^1+\dotsb+p_2^N)\dotsb(p_N^0+p_N^1+\dotsb+p_N^N).$
Dette viser sig at være summen af alle tal på formen $p_1^{m_1}p_2^{m_2}\dotsb p_N^{m_N}$ , hvor $m_i$ er et tal mellem $0$ og $N$ , begge inkl. (over vej dette!). Dette udtryk er altså større end summen $\sum_{n=1}^N n$ , som blot er summen af alle tal mellem $1$ og $N$ (hvor leddene altså blot er nogle af tallene på formen $p_1^{m_1}p_2^{m_2}\dotsb p_N^{m_N}$ ). Præcis samme argument giver os, at

$\displaystyle\sum_{n=1}^N\frac{1}{n}\le \prod_{i=1}^N\sum_{j=0}^N \frac{1}{p_i^j}$
Ovenfor så vi, at hvis vi “lader $N$ gå mod $\infty$ ” i $\sum_{j=1}^N \frac{1}{2^j}$ , så får vi $1$ , eller:

$\displaystyle \sum_{j=0}^\infty \frac{1}{2^j}=2=\frac{1}{1-\frac{1}{2}}.$
(Husk, at $2^0=1$ , så summen giver $1+1=2$ , hvis vi tager $j=0$ med også). Man kan vise, at der generelt gælder, at

$\displaystyle \sum_{j=0}^\infty \frac{1}{p^j}=\frac{1}{1-\frac{1}{p}},$
hvis ellers $p>1$ . En sådan sum kaldes en geometrisk række og behandles bl.a. i dette indlæg. Prøv evt. selv at overveje tilfældet $p=3$ , hvor der er $\frac{1}{1-\frac{1}{3}}-1=\frac{1}{2}$ gryde suppe, og første gæst tager 1/3 gryde, dvs. 2/3 af grydens indhold, hvorefter der er $\frac{1}{2}-\frac{1}{3}=\frac{1}{6}$ tilbage, næste gæst tager 2/3 af grydens indhold, dvs. $\frac{2}{3}\cdot\frac{1}{6}=\frac{1}{9}=\frac{1}{3^2}$ osv. (Generelt kan man betragte en gryde, som til at begynde med er $\frac{1}{1-\frac{1}{p}}-1$ fyldt og hvor hver gæst tager $1-\frac{1}{p}$ af, hvad der er tilbage: det svarer til, at første gæst tager $\frac{1}{p}$ grydefuld, anden gæst tager $\frac{1}{p^2}$ osv. og efter uendeligt mange gæster er der intet tilbage). Vi ser nu, at

$\displaystyle \sum_{n=1}^N\frac{1}{n}\le \prod_{i=1}^N\sum_{j=0}^N \frac{1}{p_i^j}\le\prod_{i=1}^N\sum_{j=0}^\infty \frac{1}{p_i^j}=\prod_{i=1}^N \frac{1}{1-\frac{1}{p_i}}.$
Vi bemærker nu, at hvis $p\ge 2$ , så er $\frac{1}{1-\frac{1}{p}}<e^{\frac{2}{p}}$ (prøv evt. selv at bevise dette eller nøjes med at konstatere det på en grafisk lommeregner), og da alle primtal netop er større eller lig $2$ , så fås:

$\displaystyle \sum_{n=1}^N\frac{1}{n}\le\prod_{i=1}^N \frac{1}{1-\frac{1}{p_i}}<\prod_{i=1}^N e^{\frac{2}{p_i}}=e^{2\sum_{i=1}^N\frac{1}{p_i}},$
hvor vi gjorde brug af potensregnereglen $e^ae^b=e^{a+b}$ . Vi er nu ved vejs ende: Venstre side går mod $\infty$ når $N$ går mod $\infty$ , højre side er $e$ opløftet i $2$ gange summen af de første $N$ reciprokke primtal. Altså må summen af de reciprokke primtal også gå mod uendelig (tag evt. logaritmen på begge sider af ulighedstegnet og dividér med $2$ , hvis du ikke er overbevist — logaritmen er en voksende funktion, så uligheden bevares!).

Genetisk landkort – lineær algebra, statistik og forundringsparathed

Dette landkort viser ikke det, du tror (clickbait… )

Fra artiklen

Genes mirror geography within Europe
John Novembre, Toby Johnson, Katarzyna Bryc, Zoltán Kutalik, Adam R. Boyko, Adam Auton, Amit Indap, Karen S. King, Sven Bergmann, Matthew R. Nelson, Matthew Stephens & Carlos D. Bustamante
Nature 456, 98-101(6 November 2008)
doi:10.1038/nature07331

Overordnet viser kortet følgende: Afstand mellem genetisk information fra to personer – en del af DNA – er i en vis forstand den samme, som geografisk afstand mellem de to personers oprindelsessted.

Mere præcist er det lavet ved Principal Component Analysis (PCA) – så lad os se på det først.

Principal Component Analysis:

Mange har set “bedste rette linje” i gymnasierne og PCA er noget lignende, men alligevel ikke helt.

(Fra Wikipedia CC-by-4.0 )

Figuren viser datapunkter i planen, altså data med 2 koordinater. De to akser midt i billedet er fundet med PCA: Origo er i midtpunktet for data, den længste akse er den retning, hvor der er mest variation. Det giver et nyt koordinatsystem. Man mister, som man kan se, ikke meget information ved kun at kende koordinaterne langs den akse, der går langs den længste af de to vektorer, altså projicere vinkelret ind på den linje. Og det er pointen i PCA: Fra en sky af højdimensionalt data – mange koordinater – finder man de retninger, der bedst forklarer variationen i data. Er man heldig, m.a.o., er der passende struktur i data, skal der ikke så mange af de nye koordinater til.

Landkortet kommer fra 1000 personer, datapunkter. Man kender 200.000 genetiske markører. Der er altså som udgangspunkt 200.000 koordinater(!) og PCA har reduceret til 2 koordinater. Akserne er tegnet ind som PC1 og PC2.

Hvordan finder man så disse akser i dette nye koordinatsystem? Og hvordan ved man, hvilke koordinater, der er mest betydende? Til det bruger man lineær algebra. Konkret gør man som følger – med et eksempel:

Opstil data i en matrix:

$X=\left( \begin{array}{ccccccc}2&2&3&4&1&-3&-9\\3&1&3&3&4&-7&-7\\4&1&4&4&-1&-7&-5\end{array}\right)$ Jeg har 7 punkter med hver 3 koordinater; hver søjle er koordinaterne for et punkt. Jeg har valgt dem, så middelværdien af hver af koordinaterne er 0. Er den ikke det, skal man trække middelværdien fra. Så nu er Origo, (0,0,0), midt i min datasky. I eksemplet med DNA har de en 200.000 x 1000 matrix.

Fra matricen X udregnes først $XX^T$ , covariansmatricen. Det giver en 3×3 matrix

$XX^T=\left( \begin{array}{ccc} 124&117&103\\117&142&117\\103&117&124\end{array}\right)$

Kender man ikke matrix produkt, så tænk på det som en organiseret opstilling af alle de skalarprodukter, man kan lave med de tre rækker i X.

Det er et centralt resultat i lineær algebra, at der til sådan en symmetrisk matrix (der står det samme over og under diagonalen) hører tre egenvektorer og det viser sig at være de vektorer, vi leder efter til PCA. Her er det (sådan cirka)

$v_1= \left( \begin{array}{c} 1\\1,097\\1 \end{array}\right)$ , $v_2= \left(\begin{array}{c}-1\\0\\1\end{array}\right)$ , $v_3=\left(\begin{array}{c}1\\-1,823\\1\end{array}\right)$

Det er egenvektorer for $XX^T$ . De tilhørende egenværdier er (igen sådan cirka – I kan selv regne dem præcist ud, hvis I synes, det er vigtigt). $350, 21, 14$ . Den første værdi er, som man kan se, langt større end de andre. Altså $X X^Tv_1=350 v_1$

Det betyder, at langt det meste af variationen i data sker i retning langs $v_1$ . Man mister ikke megen information ved kun at se på datapunkternes projektion ind på den retning.

Her er PCA Explained Visually Man kan lege med data i 2 og 3 dimensioner og der er et eksempel på, hvordan madvaner og geografi hænger sammen (i Storbritannien).

Landkortet laves som følger:

Find en 200.000×200.000 matrix udfra den oprindelige 200.000 x1.000 matrix.
Udregn egenværdier og egenvektorer for denne.
Se på størrelsen af egenværdierne. Her er to af dem betydeligt større end de andre.
De to tilhørende egenvektorer PC1 og PC2 giver en plan i det 200.000 dimensionale rum. Landkortet viser projektionen af de 1000 datapunkter ind på denne plan. Man har derefter farvet datapunkterne efter personernes oprindelsesland. Og drejet det lidt, så det ligner et sædvanligt landkorts nord-syd og øst-vest orientering. De store farvede cirkler er middelværdier. Eksempelvis er den turkise, der står DK i, middelværdi for alle datapunkter fra Danmark.

Det illustrerer, at afstanden mellem de genetiske markører i meget høj grad kan forklares med geografisk afstand. Bemærk, at den Iberiske halvø (Spanien og Portugal) ligger lidt upræcist. Det skyldes, at afstanden ikke måles direkte på en globus. Det er en rejseruteafstand – den genetiske afstand afhænger af, hvor langt man tidligere typisk har rejst for at finde sin partner. De lille kort viser, at man i Schweiz har fundet partner blandt dem, der talte samme sprog.

Man kan også undersøge forholdet mellem geografiske og genetiske afstande på andre måder. Mikkel (fra vores eget institut) har undersøgt noget tilsvarende for Y-kromosomer (som kun mænd har), dog ikke vha. PCA men vha. en såkaldt modelbaseret klyngeanalyse. Her ses resultatet: