« Veckans fredagsfyra | Main | Google Frequent Searchers - nu då?! »

oktober 05, 2003

Sammanträffanden - anteckningar vid läsning av Diaconis och Mosteller 'Methods for Studying Coincidences'

[Om denna anteckning är svårläst på huvudsidan, försök då att läsa det som separat anteckning här]

Detta är en liten anteckning med anledning av papret Methods for Studying Coincidences av Persi Diaconis och Frederick Mosteller som jag lyckades få tag i tack vare en snäll person. Tack!

Studiet av coincidences (sammanträffanden) är relaterat till kognitiva illusioner som jag (egentligen) håller på att kolla in. Vi har dålig intuition om sammanträffanden, vilket födelsedagsproblemet visar: Födelsedagsproblemet säger att det krävs 23 personer för att det ska vara 50% chans att två av personerna i denna grupp har samma födelsedag. Förvånande? En vanlig intuition är att det krävs många fler personer.
Se nedan för refererenser om detta mycket berömda problem.

Här nedan går jag igenom ett av de intressantaste avsnitten i Diaconis och Mostellers paper, avsnittet "7.1 General-Purpose Models: Birthday Problems" (sid 857ff).

Mestadels består denna anteckning av citat från papret och en del R-kod. Statistik/data analys-paketet R finns att ladda ner på www.r-project.org.

I övrigt finns det andra mycket intressanta diskussioner i artikeln, t.ex.

The Standard Birthday Problem
Detta är standardversionen av födelsedagsproblemet.

Problem 1: The Standard Birthday Problem. Suppose N balls are dropped at random into c categories, N <= c. The chance of no match (no more than one ball) in any of the categories is

prod(1-i/c, i=1..N-1) (Expression 7.1)

... If c is large and N i small compared to c**(2/3), the following approximation is useful. The chance of no match is approximately

exp(-N**2/2*c) (Expression 7.2)

This follows easily from Expression (7.1), using the approximation

log_e(1-i/c) ~ -i/c

To have probability about p of least one match, equate (7.2) to 1-p and solve for N. This gives the approximations
N ~ 1.2 * sqrt(c) (Expression 7.3)
for a 50% chance of match and
N ~ 2.5 * sqrt(c)
for a 95% chance of match.
[...]

Thus, if c=365, N=22.9 or 23 for a 50% chance and about 48 for a 95% chance.

I R skriver man: 
> 1.2 * sqrt(365)
[1] 22.92597

> 2.5 * sqrt(365)
[1] 47.76243
Many Types of Categories
Följande problem är mycket intressant. Här räknar man (approximativt) ut hur stor sannolikheten är för att det finns sammanträffande där det finns flera attribut. I standardversionen av födelsedagsproblemet är det ju endast ett attribut (samma födelsedag). Här generaliseras alltså detta.

Problem 2: Many Types of Categories.
...
Suppose that a group of people meet and get to know each other. Various types of coincidences can occur. These include same birthday; same job; attended same school (in same years); born or grew up in same country, state or city; same first (last) name; spouses' (or parents') first names the same; and same hobby. What is the chance of a coincidence of some sort?
....
If the numbers of [independent] categories in the sets are c1, c2,...ck, we can compute the chance of no match in any of the categories and subtract from 1 as before. If k different sets of categories are being considered, the number of people needed to have an even chance of a match in some set is about

N ~ 1.2 * sqrt(1/ (1/c1 + 1/c2 + ... 1/ck)

The expression under the square root is the harmonic mean of the ci divided by k. If alla ci equal c, the number of people needed becomes 1.2*(c/k)^1/2 so that multiple categories allow coincidences with fewer people as would be expected. For a 95% chance of at least one match, the multiplier 1.2 is increased to 2.5 as in Expression 7.4.
...
As an illustration, consider three categories: c1 = 365 birthdays; c2= 1000 lottery tickets; c3 = 500 same theater tickets on different nights. It takes 16 people to have an even chance of a match here.

I R:

För en 50-50-chans för en match kräver alltså 16 personer: 
> 1.2 * sqrt(1/sum(1/c(365,1000,500))); round(.Last.value)
[1] 15.83929
[1] 16
Och för 95% chans till en match krävs 33 personer: 
>  2.5 * sqrt(1/sum(1/c(365,1000,500))); round(.Last.value)
[1] 32.99852
[1] 33
Multiple Events
Här studeras en match för k antal personer som ska ha samma attribut (t.ex. samma födelsedag).

Problem 3. Multiple Events. With many people in a group it becomes likelu to have triple matches or more. What is the least number of people required to ensure that the probabilit exceeds 1/2 that k or more of them have the same birthday? McKinney (1966) found, for k=3, that 88 people are required. For k=4, we require 187.
....
The number of people required to have the probability of p of k or more in the same category is approximately [...]
N*E**(-N/(c*k)) / (1 - N/(c*(k+1)))^(1/k) =
( c**(k-1) * k! * log_e(1/(1-p)) )**(1/k) (Expression 7.5]

....
[Example:]
A friend reports that she, her husband, and their daughter were all born on the 16th. Take c = 30 (as days in a month), k = 3, and p = 1/2. Formula (7.5) gives N ~ 18. Thus, among birthdays of 18 people, a triple match in day of the month has about a 50-50 chance.

R-kod:
Först lite förklaringar:
log är logaritmen med basen E.
Funktionen factorial() finns i paketet gregmisc och är definierad som 
factorial <- function(x) { gamma( 1 + x)}

Det kan även skrivas som prod(1:k), dvs 
>  c=30; k=3; p=1/2; (c**(k-1) * prod(1:k) * log(1/(1-p)) )**(1/k)
[1] 15.52648
men om man vill arbeta med vektorer, t.ex. testa för olika värden av k (t.ex. 1:10), blir det problem att ha ytterligare en vektor i prod(1:k) 

> c=30; k=3; p=1/2; (c**(k-1) * factorial(k) * log(1/(1-p)) )**(1/k)
[1] 15.52648
Trist! Jag förväntade mig värdet (ungefär) 18 här.
Jag pushar ovanstående diskussion och kollar in detta problem lite mer.

Funktionen qbirthday finns som standard i R som är följande (via hjälpen, ?qbirthday):
Computes approximate answers to a generalised ``birthday paradox'' problem. `pbirthday' computes the probability of a coincidence and `qbirthday' computes the number of observations needed to have a specified probability of coincidence.

Man refererar explicit och endast till Diaconis och Mostellers paper.
Är det fel i papret?
Med min formel får jag princip samma som följande: 
> qbirthday(prob=0.5, classes=30, coincident=3)
[1] 16
Jag jämför här min formel med qbirthday för olika k-värden, och avrundar sålunda till heltal. 
> c=30; k=1:10; p=1/2; round((c**(k-1) * factorial(k) * log(1/(1-p)) )**(1/k))
 [1]  1  6 16 26 37 48 59 71 82 93

> c=30; k=1:10; p=1/2; sapply(k, function(i) qbirthday(prob=p, classes=c, coincident=i)) 
[1]  1  6 16 26 37 48 59 71 82 93
De ser ut att vara identiska! Jag vet tyvärr inte varför våra värden skiljer sig mot papret.

Tyvärr hittade jag även följande problem: För stora värden av k (t.ex. 1000) är min formel dålig eftersom den ger Inf (infinity) i factorial(). Även om man i stället använder prod(1:k) blir det Inf. Efter lite undersökningar visar det sig att max-värdet för k är 170. Så qbirthday är att föredra i sådana fall. 
> c=30; k=1000; p=1/2; round((c**(k-1) * factorial(k) * log(1/(1-p)) )**(1/k))
[1] Inf
medan qbirthday inte har några problem med stora värden för k (t.ex. 1000): 
> c=30; k=1000; p=1/2; sapply(k, function(i) qbirthday(prob=p, classes=c, coincident=i)) 
[1] 11043
OK. Nu vet vi det.!

Så, tillbaka till huvudspåret.
För en simulering av födelsedagsproblemet med k = 3 resp. 4 får vi följande approximationer (jämför med svaren 88 resp 187 som nämns ovan). Vi jämför också med qbirthday för att kolla. 
>  c=365; k=3; p=1/2; (c**(k-1) * factorial(k) * log(1/(1-p)) )**(1/k)
[1] 82.13359

> qbirthday(prob=0.5, classes=365, coincident=3)
[1] 82

> c=365; k=4; p=1/2; (c**(k-1) * factorial(k) * log(1/(1-p)) )**(1/k)
[1] 168.6471

> qbirthday(prob=0.5, classes=365, coincident=4)
[1] 169
Dvs det krävs (approximativt enligt "vår" metod) 83 personer för att, med 50% chans, tre eller flera personer ska ha samma födelsedagar.

Almost Birthdays
Detta är vad författarna även kallar för multiple endpoints, dvs att två saker nästan matchar. Tillåter vi sådana nästan-matchningar (och ofta görs det utan någon uttrycklig gräns för var "nästan" slutar) blir sannolikheten hög för en träff.

Problem 4: Almost Birthdays.
...
How many people are needed to make it even odds that two have a birthday within a day.
...
A neat approximation for the minimum number of people required to get a 50-50 chance that two have a match within k, when c categories are considered [...] is approximately

N ~ 1.2 * sqrt(c/(2*k + 1) (Expression 7.6)

When c = 365 and k = 1, this approximation gives about 13 people (actually 13.2).

I R: 
> 1.2 * sqrt(365/(2*1 + 1))
[1] 13.23631
Om vi kollar denna approximering från 0 dagar till 20 får vi följande: 
> sapply(0:10, function(i) round(1.2 * sqrt(365/(i*1 + 1)),1))
 [1] 22.9 16.2 13.2 11.5 10.3  9.4  8.7  8.1  7.6  7.2  6.9
dvs det krävs ungefär 7 personer för att det ska vara 50% chans att två personer fyller år inom 10 dagars räckvidd.

Jag antar nu (men det står inte uttryckligen i papret) att detta gäller samma som tidigare, dvs vi multiplicerar med 2.5 för att få 95% chans till en match. Vi får då: 
> sapply(0:10, function(i) round(2.5 * sqrt(365/(i*1 + 1)),1))
 [1] 47.8 33.8 27.6 23.9 21.4 19.5 18.1 16.9 15.9 15.1 14.4
dvs med 15 personer är vi tämligen säkra (95%) att det finns två födelsedagar inom 10 dagars räckvidd.

The Law of Truly Large Numbers Slutligen avslutas med följande tänkvärda (och möjligen i efterhand självklara) citat:

The Law of Truly Large Numbers.
Succinctly put, the law of truly large numbers states: With a large enough sample, any outrageous thing is likely to happen. The point is that truly rare events, say events that occur only once in a million [as the mathematician Littlewoood (1953) required for an event to be surprising] are bound to be plentiful in a population of 250 million people. If a coincidence occurs to one person in a million each day, then we expect 250 occurences a day and close to 100000 such occurences a year.

Going from year to a lifetime and from the population of the United States to that of the world (5 billion at this writing), we can be absolutely sure that we will see incredibly remarkable events. When such events occur, they are often noted and recorded. If they happen to us or someone we know, it is hard to escape that spooly feeling.

Se även följande om födelsedagsproblemet
Birthday Problem
Coincident Birthdays
Coincidence
The Skeptic's Dictionary: law of truly large numbers (coincidences)

Relevanta tidigare blogganteckningar (och referenser):
Tankeillusioner och tankemisstag
Chance News (och sajt)
Att förutsäga framtiden i efterhand - hindsight bias/creeping determinism (läs även kommentarerna).


Uppdatering
Mer om simulering av sammanträffanden finns i Simulering av sammanträffanden - I.

Posted by hakank at oktober 5, 2003 09:39 EM Posted to Sammanträffanden | Statistik/data-analys