Hét -sterk voor sterke verandering vatbare- definitieve wiskundetopic van WCP-senpai

@Snakke schreef:Ik weet niet of dit topic nog openstaat voor suggesties, maar ik zou wel eens het verjaardagsparadox uitgelegd willen krijgen.
Aangezien er niet zolang geleden 3 personen jarig waren wil ik wel eens weten wat de kans is dat er over een jaar (als we veronderstellen dat het forum een even grote groei heeft) iemand is die als vierde op die dag jarig is.
Of met hoeveel leden het forum moet zijn zodat de kans 50% is dat er op elke dag twee mensen verjaren.

De verjaardagsparadox is in feite geen echte paradox. Er is namelijk geen tegenspraak tussen stellingen of axioma's die er aan ten grondslag liggen, noch is het een onoplosbaar probleem. Het wordt slechts een paradox genoemd omdat de resultaten ervan tegen de intuïtie ingaan. Tenminste, de intuïtie van iemand voor wie kansberekening geen tweede natuur is geworden. Intuïtie bij dieren, inclusief ons, is bedoeld om snel beslissingen te kunnen nemen bij gebrekkige informatie. Het is gericht op wat meestal resultaat boekt. Wanneer het echter aankomt op zaken die effectief berekend moeten worden is intuïtie vaak niet erg accuraat, of zelfs ronduit verkeerd. Dit is wat er voor zorgt dat mensen bij gokken almaar meer geld verliezen tegenover een partij die de kansen wel kent (zoals een casino) en er voor zorgt dat die in z'n voordeel zijn.

Bij de verjaardagsparadox bestaat die intuïtieve faux pas uit de inschatting dat in een groep mensen van bepaalde grootte er geen twee zitten met dezelfde verjaardag, of juist wel (minstens) twee met dezelfde verjaardag. Meer specifiek, voor getallen veel lager dan het aantal dagen in een jaar schatten de meeste mensen de kans op geen twee gedeelde verjaardagen veel te hoog in, en omgekeerd de kans op minstens twee gedeelde verjaardagen te laag. In wat volgt gaan we voor het gemak schrikkeljaren negeren, alsook de distributie van geboortedagen doorheen het kalenderjaar. Niet elke dag heeft namelijk dezelfde kans op geboortes, er zijn fluctuaties op basis van zaken als seizoenen, cultuur en verscheidene gebeurtenissen. We gaan er eenvoudigweg van uit dat voor een willekeurige dag de kans dat je daarop verjaart 1/365 is.

Stel dat je een kamer hebt met 20 willekeurig gekozen personen in. Wat is nu de kans dat elke persoon een unieke datum in het jaar heeft waarop deze verjaart? Dus, geen twee personen in de kamer met dezelfde verjaardag? Doorgaans wordt deze kans veel te hoog ingeschat. De redenering die mensen volgen is dat er 365 dagen in een jaar zijn, en slechts 20 personen in deze kamer. Er zijn maximaal 20 verschillende verjaardagen. Met 345 lege dagen moet de kans dat er twee dezelfde hebben toch wel aan de lage kant zijn?
In realiteit is de kans dat er geen twee personen in de kamer zijn met dezelfde verjaardag ongeveer 58,86% ofwel 0,5886 in decimale notatie (die we vanaf nu vaker gebruiken). De kans dat er minstens twee personen zijn met een dezelfde verjaardag is 41,14% ofwel 0,4114.
Voor 23 personen is de kans dat er geen twee dezelfde verjaardagen zijn reeds minder dan 1/2.
Bij 40 personen is de kans nog slechts 0,1088 (10,88%).

Hoe berekenen we dit nu? Bij kansberekening is een belangrijk principe dat wanneer we twee of meer mutueel exclusieve situaties hebben, de som van de kans op elke situatie 1 wordt (100%). Stel dat we een munt opwerpen. De twee uitkomsten zijn kop of munt. Als we aannemen dat beide 0,5 kans hebben zie je dat de som 0,5 is. Kop en munt zijn mutueel exclusief. Je zou ook kunnen stellen dat de kans dat het kop is en de kans dat het niet kop is 1 moet zijn. Wat als er een 1/1000 kans is dat de munt op z'n kant blijft staan? Dan wordt dat gewoon een derde situatie. De kans op kop/munt neemt lichtjes af, maar de som kop + munt + kant blijft 1.
Laten we n personen kiezen. Stel n = 1. De kans op een gedeelde verjaardag is 0, want er is maar 1 persoon. De kans op geen gedeelde verjaardag is dus 1.
Stel n = 2. De eerste persoon heeft een specifieke verjaardag. De kans dat de tweede persoon dezelfde verjaardag heeft is 1/365 (~= 0,0027 ofwel 0,27%), want er zijn 365 dagen om uit te kiezen maar slechts eentje komt overeen met die van de eerste persoon. De kans op geen gedeelde verjaardag is dus 1 - 1/365 (~= 0,9973 ofwel 99,73%).
Voor hogere waarden van 2 wordt het echter lastig. Voor n = 4 bijvoorbeeld moeten we berekenen wat de kans is dat er 2 personen dezelfde verjaardag hebben, de kans dat 3 personen dezelfde verjaardag hebben en de kans dat ze alle 4 dezelfde verjaardag hebben. De som van die kansen is die dat er minstens een gedeelde verjaardag is. Zelfs die deelproblemen worden lastig, omdat bijvoorbeeld van de 4 er 2 paren kunnen zijn met dezelfde verjaardag (bv. 2 op 10 februari en de 2 andere op 17 oktober). Als voor n personen de kans dat er x dezelfde verjaardag hebben wordt uitgedrukt als K(x), dan is de kans dat er minstens 2 met dezelfde verjaardag zijn gelijk aan K(2) + K(3) + ... + K(n).
Dat wordt een hoop rekenwerk. Gelukkig kunnen we beroep doen op de mutueel exclusieve situaties. Het is gemakkelijker om te berekenen wat de kans is dat niemand dezelfde verjaardag heeft. Dat is K(1). En we weten dat de som K(1) + K(2) + ... + K(n) gelijk moet zijn aan 1.
Dus:
1 = K(1) + K(2) + ... + K(n)
Als we willen weten wat K(2) + K(3) + ... + K(n) is (de kans om minstens 2 gedeelde verjaardagen) doen we gewoon
1 - K(1) = K(2) + K(3) + ... + K(n)

Hoe berekenen we wat de kans is dat niemand dezelfde verjaardag heeft? Als we n personen hebben...
Dan kiezen we de eerste persoon. Deze heeft een bepaalde verjaardag. De kans op geen gedeelde verjaardag is 1, ofwel 365/365.
We kiezen een tweede persoon. De kans dat deze niet dezelfde verjaardag heeft is 364/365. Er zijn namelijk 364 dagen te kiezen die niet samenvallen met de eerste.
We kiezen een derde persoon. De kans dat deze niet dezelfde verjaardag heeft is 363/365. Er zijn namelijk 363 dagen te kiezen die niet samenvallen met de eerste twee.
Enzovoort.
De kans dat we voor n personen geen gedeelde verjaardag hebben is de vermenigvuldiging van die reeks. Dus:
(365/365) * (354/365) * (363/365) * ... * ((365-n+1)/365)
Merk op dat vanaf n > 365 de kans effectief 0 is. Dit is het pigeonhole principe. Als je 20 duivenhokken hebt kan je er niet meer dan 20 duiven inpassen zonder er minstens 2 in hetzelfde hok te moeten steken.
De bovenstaande reeks kan worden uitgedrukt als:
(365!/(365-n)!) / (365^n)
! is de faculteitsoperator, ^ de machtsverheffing.

Spoiler:

k!/(k-n)! is een makkelijke manier om de vermenigvuldiging k * (k-1) * (k-2) * ... * (k-n) te berekenen of noteren. Dit is dus de 365 * 364 * ... * (365-n). De 365 tot de macht n zijn de delers van bovenstaande reeks die vermenigvuldig worden, voor n personen.

Als je wilt weten wat de kans is op minstens 2 personen met dezelfde verjaardag, doe je gewoon 1 min bovenstaande formule.

Laten we een plot bekijken van de kans op geen gedeelde verjaardagen in functie van n:
http://www.wolframalpha.com/input/?i=%28365!%2F%28365-n%29!%29%2F%28365^n%29%2C+n+in+[1%2C365]

Omgekeerd, een plot van de kans op minstens 2 gedeelde verjaardagen in functie van n:
http://www.wolframalpha.com/input/?i=1+-+%28365!%2F%28365-n%29!%29%2F%28365^n%29%2C+n+in+[1%2C365]

Het tegenintuïtieve volgt uit twee zaken. Ten eerste, de plots zijn niet lineair. Ten tweede, ze dalen respectievelijk stijgen pijlsnel bij reeds lage aantallen voor ze uitvlakken. Deze link zou een plot moeten tonen die inzoomt op een kleiner interval van 1 tot 40:
http://www.wolframalpha.com/input/?i=birthday+problem+20+people
Je kan overigens aan WolframAlpha vragen om het voor gelijk welk aantal mensen te berekenen.

Gerelateerd aan je vraag: we zijn nu bijna een jaar later en er zijn 298 geregistreerde leden. De kans dat er op een willekeurig gekozen dag geen enkel lid verjaart is 0,4415 (44,15%). Dit lijkt op zijn beurt misschien tegenintuïtief na het verjaardagsprobleem te hebben bekeken. De berekening hiervan laten als oefening aan de lezer over. En het precieze antwoord op je vraag laat ik over aan iemand die beter is in kansberekening dan ik...

Voor nog een interessant probleem dat zodanig onintuïtief lijkt dat veel mensen de oplossing zelfs niet willen aanvaarden, tot en met een kwade rant van een zekere Scott Smith, Ph.D. aan de universiteit van Florida, moet je zeker eens hier kijken: https://en.wikipedia.org/wiki/Monty_Hall_problem

Oh wow ik zie deze post nu pas. Dankje voor je uitgebreid antwoord Nekotaku!
Ik moet eerlijk toegeven dat ik tijdens het maken van mijn vorige post weinig afwist van kansrekenen. Nu een jaar later en een heel deel meer wiskunde achter de kiezen heb ik al een kleine inleiding gehad tot kansrekenen. Inclusief het befaamde verjaardags- en het driedeurenprobleem.

Ook wil ik mij excuseren voor zo een tamelijk gecompliceerde vraag te stellen, sorry WCP-senpai.
alsjeblieft laat de wiskundegoden me nu nog goed gezind zijn

Voor de oefening van de lezer: hey ik ben een lezer! En ik ben braaf geweest en heb mijn oefeningen mooi voorbereid!

Gevraagd is de kans dat op een willekeurige dag niemand verjaart. We lossen dit probleem op door in stappen te werken.
We nemen een willekeurige dag. (concreet voorbeeld: 25 juli)
De kans dat een lid niet op deze dag verjaart is 364/365 immers, er zijn 364 dagen verschillend van 25 juli.
Aangezien die kans voor elk persoon hetzelfde is, en constant blijft, zal voor de overige 297 de kans hetzelfde zijn, namelijk 364/365.
De kans dat niemand verjaart is dus: (364/365)*(364/365)*...*(364/365) [dus 298 termen]
of simpel geschreven: (364/365)^298 [met ^ de machtsverheffing]
Als we dit uitwerken krijgen we: 0,4415. De juiste oplossing dus!

Ik heb ook geprobeerd een makkelijkere versie van mijn vraag op te lossen, namelijk wat is de kans dat minstens 3 personen op dezelfde dag verjaren. Maar liep op beide pistes die ik had verzonnen tamelijk snel vast omdat ik niet de exacte kans dat er precies 2 leden op dezelfde dag verjaren kon berekenen. Zoals Nekotaku ook al zei.

Ook het driedeurenprobleem is wel algemeen bekend voor de wiskundige. Maar hier heb je een mooie variatie op het probleem die de mensen van de Maastricht Mathematical Modeling competion hebben bedacht!
https://project.dke.maastrichtuniversity.nl/mmm/mmm18/probl1.pdf
De oplossing zal je verbazen! Tenzij je niet geïnteresseerd bent in wiskunde. Dan is dit absoluut nerdig en saai.

Het was helemaal niet zo'n complexe vraag! Het spijt me wel dat ik er al die tijd niet op gereageerd heb, maar het ontsnapte m'n gedachten steeds weer. Gelukkig is Nekotaku zo vrij geweest je vraag beter te beantwoorden dan ik ooit zelf had kunnen doen.

Maar ik wil nog een aanvulling maken die je hopelijk kunt appreciëren. De probleemstelling van de verjaardagsparadox kunnen we immers verregaand veralgemenen; namelijk wat de kans is dat een willekeurige afbeelding van X naar Y injectief is.

Eerst wat definities en notaties:

In wat volgt zijn X en Y altijd eindig met |X| <= |Y|.

Definitie. Zij X en Y verzamelingen. Een afbeelding van X naar Y is een verzameling {(x,y) | x in X en y in Y zó dat er voor elke x er een (minstens één) y bestaat}. We noteren f : X -> Y.

Deze definitie vertelt je formeel wat een afbeelding precies is: deze verbindt met elke x een y (je kent wellicht het begrip functie: een afbeelding is een functie waarbij het domein samenvalt met de definitieverzameling).

Notatie. Zij f: X -> Y een afbeelding. We noteren met f^-1{y} de verzameling {x in X | f(x) = y}.

Definitie. Zij f : X -> Y een afbeelding. Een injectie of injectieve afbeelding is een afbeelding zó dat f^-1(y) een singleton is voor alle y in Y.

Notatie. Zij X en Y verzamelingen. We noteren met Y^X de verzamelingen van alle functies van X naar Y.

__________________________________________________________________________________________________________________

We maken eerst de volgende observaties die ons dadelijk zullen helpen.

Observatie. Zij X en Y verzamelingen. Dan is |Y^X| = |Y|^|X|.

Bewijs. Voor elke x in X zijn er precies |Y| keuzes om f(x) vast te leggen. Omdat we voor |X| elementen |Y| keuzes hebben, zijn er bijgevolg |Y|^|X| mogelijke afbeeldingen van X naar Y.

Observatie. Zij X en Y verzamelingen. Het aantal injectieve afbeeldingen van X naar Y is |Y| x ... x (|Y| - |X|).

Bewijs. Voor elke injectie is er voor elke keuze van x in X nu juist één y in Y mogelijk. Er zijn |Y| manieren om de keuze voor de eerste x vast te leggen. Door de keuze van de eerste x, zijn er juist |Y|-1 mogelijkheden om de tweede x vast te leggen. Per inductie volgt dus eenvoudig dat er juist |Y| x ... x (|Y| - |X|) manieren zijn om een injectie te construeren.

__________________________________________________________________________________________________________________

We zijn nu klaar om de volgende stelling te bewijzen:

Stelling. Zij X en Y verzamelingen. De kans dat een zekere f in Y^X injectief is, is gelijk aan (|Y| x ... x (|Y| - |X|) / (|Y|^|X|).

Bewijs. Kies willekeurig een afbeelding f in Y^X. Aangezien het kiezen van zo'n afbeelding een uniforme kansmaat induceert, is de kans dat f injectief is precies (|Y| x ... x (|Y| - |X|) / (|Y|^|X|).

Nu we dit achter de rug hebben, kan ik uitleggen hoe dit nu eigenlijk verband houdt met je oorspronkelijke vraag. We vragen ons dus af wat de kans is dat n mensen elk een verschillende verjaardag hebben. Dit betekent precies dat er ons gevraagd wordt wat de kans is dat een afbeelding van {1, ..., n} naar {1, ..., 365} een injectie is! Neko had voor ons al uitgerekend dat dit 365 * ... * (365 - n)/365^n moest zijn. En inderdaad, dit is exact wat je krijgt als je de formule gebruikt die we in de vorige stelling bekomen hebben.

We zien hier ook het belang in van de voorwaarde |X| <= |Y|. Als immers |X| > |Y|, bestaat er natuurlijk geen injectie!