« Uppdatering 2 av Devil's Word | Main | Sistaminutenpåminnelse: Bloggaremiddag måndag 6 juni 14.00 Glorias Lounge Malmö »

juni 04, 2005

Lite om sammanträffanden och Ramseyteori (Ramsey theory)

En sak som jag tidigare tänkt skriva om i anslutning till sammanträffanden är Ramsey-teori, men det har inte blivit av tidigare. Här är en något bearbetad text som skrevs när jag höll på som mest kring detta (hösten 2003/våren 2004). Funderingarna aktualiserades genom uppdateringen av Devil's Word för en stund sedan.


Det började med en Skeptical Inquirer-artikel från 1998 Coincidences: Remarkable or Random? där Ramseyteorin nämns (min emfas):
Clearly, unspecified improbable coincidences occur daily to everyone, and these coincidences are most likely the result of randomness. If the data set is large enough, coincidences are sure to appear, as demonstrated with the first 100 decimal digits of p. The chance of tossing five straight heads is only 3 percent, but for 100 tosses the chance becomes 96 percent. Though applied in a different context, Ramsey theory (Scientific American, July 1990) states that "Every large set of numbers, points, or objects necessarily contains a highly regular pattern." It is not necessary to posit mysterious forces to explain coincidences.

Efter det har jag försökt hitta mer information om det finns mer direkt koppling mellan Ramseyteorin och studiet av sammanträffanden. Tyvärr är jag inte tillräckligt matematiskt insatt för att förstå finliren i de mer avancerade delarna av teorierna, och därför hänvisat i stort sett endast till populariserade skrifter (vilket ju är tillåtet för en PopSci-junkie, eller hur?).

Tyvärr har jag inte lyckats hitta den artikel som refereras i citatet ovan: Ramsey Theory av Ronald Graham och Joel Spencer. Scientific American, 1990, Juli-numret. 263 (1), sid 112-117. Har någon en elektronisk kopia till övers vore det önskvärt med en pek.

Not: Det finns andra "Ramseyteorier", bland annat i logisk analys och ekonomisk teori. Den Ramseyteori som är relevant för detta vidkommande är den matematiska, grafteoretiska. Intressant nog är det är samma Frank Ramsey som avses i alla.


Ramseyteoretikernas credo (eller en popularisering av denna) är "Complete disorder is impossible", dvs i varje samling av punkter finns det alltid någon struktur. En annan beskrivning är "studies the conditions under which order must appear" (min fetning). Båda dessa beskrivningar finns t.ex. i Wikipedia-artikeln Ramsey Theory.

Ramseys teori brukar presenteras genom att utgå från det s.k. party-problemet (se t.ex. Ivars Peterson Party Games) som frågar hur många personer det minst måste vara på en fest för att garantera att det ska finnas antingen tre eller flera personer som känner varandra eller tre eller flera personer som är obekanta.

Ett enklare exempel är följande: Tänk att vi har två par strumpor i en byrålåda, två par röda och två par blå. Hur många strumpor måste vi ta för att vara säkra på att få ett par av samma färg. Svar: tre strumpor.


Det intressanta här är att teorin säger att i en tillräcklig stor (matematisk) struktur kan man hitta vilken delstruktur som helst. Ett exempel som brukar nämnas är stjärnhimmeln och dess konstellationer: genom att rita linjer mellan de stjärnorna som syns på himmeln kan man i stort sett få fram vilken figur som helst. Detta är, så vitt jag vet, inte matematiskt bevisat, utan ska ses som ett exempel på vad Ramseyteorin säger.

Troligen är Ramseyteorin inte praktisk användbar för att räkna ut de faktiska värdena för så komplicerade sammanträffanden som "X och Y är födda på exakt samma dag och klockslag, deras föräldrar bodde grannar för länge sedan men flyttade till olika städer. X och Y gick på samma universitet trots att deras väg dit var helt olika. Vilket sammanträffande!" (Se snarare Sammanträffanden - anteckningar vid läsning av Diaconis och Mosteller 'Methods for Studying Coincidences' för detta.)

En annan sak är att vi nästan alltid pratar om dessa sammanträffanden i efterhand, dvs efter vi upptäckt dem. Statistiker och andra anser att detta är totalt förkastligt och vetenskapliga undersökningar som gör sådant fördöms starkt. Se Statistisk data snooping - att leta efter sammanträffanden för exempel på sådant.

Ett exempel på att vi ofta kan hitta sådana strukturer är programmet Devil's Word som har beskrivits på lite olika ställen, t.ex. här och nyligen här.


Vad är då kopplingen mellan Ramseyteorin och teorier om sammanträffanden? Tyvärr har jag inte hittat så mycket mer än ovanstående, förutom kanske lite fler och andra exempel (se referenserna nedan). Jag har inte heller hittat någon specifik teori där man konkret exemplifierar med vår tro på övernaturliga sammanträffanden etc.

Slutsatsen bör ändå vara att eftersom det i varje (sammanträffande-)situation finns det någon form av struktur (dvs sammanträffande), bör vi därför vara försiktiga med att säga att en viss uppkommen struktur beror på något annat än slumpen. Förresten, det är ju inte ens slump utan en matematiskt nödvändigt att vissa typer att strukturer ska finnas där!

[Kan som kuriosa nämna att jag tidigare hade skrivit om Ramseyteori, sammanträffanden kopplat till komplexa/sociala nätverk, men det var lite väl flummigt så det togs bort.]


Litteratur som lästs
Här är några böcker som i alla fall har några relevanta sidor om sammanträffanden och Ramseyteori.

* Martin Gardner: Ramsey Theory. Artikeln finns t.ex. i Gardners samlings-samlingsvolym The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems som innehåller några fler kommentarer än originalartikeln.
* Ivars Peterson: Jungle in Randomness
* Deborah Bennett Randomness
* Ramsey och Ramseyteorin nämns på några sidor i två Erdös-biografierna: My brain is open < >, samt The Man Who Loved Only Numbers - The Story of Paul Erdos and the Search for Mathematical Truth. Se utdrag från den senare boken. (Jag nämnde f.ö. båda dessa böcker häromdagen i en kommentar.)
* John Allen Paulos: Upon a Number nämner Ramsey (sid 160ff) och sammanträffanden, dock inte så mycket kopplat till varandra.
* Bela Bollabas: Random Graphs (kapitlet "Ramsey Theory", som tyvärr inte gav speciellt mycket i frågan om sammanträffanden).

Några artiklar å nätet:
Ramsey theory
Ivars Peterson Rainbow Randomness
Ivars Peterson Deep in the Jungles
Craig Merow The Odd Couple (de udda figuerna är Paul Erdös och Ronald Graham)
Van der Waerden's theorem

Posted by hakank at juni 4, 2005 09:49 EM Posted to Sammanträffanden

Comments

"...conditions under which order must appear"
Hur står sig detta i förhållande till entropins andra lag?
I ett slutet system ökar entropin (graden av oordning).

Kanske enklast exemplifierat med att en droppe bläck i ett vattenglas kommer att blandas ut i vattnet, så att uppdelningen bläck/vatten försvinner. Är det då den nya utspädda bläckfärgen som är mönstret / ordningen?

Posted by: HÃ¥kan (hakke) [TypeKey Profile Page] at juni 5, 2005 02:51 FM

En kul grej som hänger ihop med detta är att man har gjort försök där man ber personer skriva en mängd slumpmässiga tal. Vad man har funnit då är att dessa "slumpmässiga" tal inte alls är slumpmässiga, utan att de ofta saknar de osannolika mönstren. Tänk dig själv, skulle du kunna skriva 1 1 1 1 1 1 1 1 1 1 om du blev ombedd att skriva 10 slumpvisa tal? :)

Posted by: kalle at juni 5, 2005 08:09 EM

Hakke: Missade din kommentar tidigare. Intressant fråga, och jag har just nu inget intressant svar att ge. Får fundera lite.


Kalle: Ja, vi har ofta dålig intuition om vad som är slumpmässigt och inte slumpmässigt.

Lite av detta har jag faktiskt skrivit om i kategorierna "Kognitiva illusioner": http://www.hakank.org/webblogg/archives/cat_kognitiva_illusioner.html, speciellt forskningen av Tversky, Kahneman och deras kolleger. Och även nämnt det i Sammanträffanden: http://www.hakank.org/webblogg/archives/cat_sammantraeffanden.html .


För att svara på din fråga: Nej, det skulle skulle kännas "onaturligt" att skriva denna sekvens. Likväl är sekvensen lika sannolik som någon annan fördefinierad sekvens av 10 tal, t.ex. 6, 9, 1, 5, 10, 5, 5, 3, 1, 7 (som mitt statistikprogram just genererade).

Posted by: hakank [TypeKey Profile Page] at juni 5, 2005 08:35 EM