Syntymäpäivän paradoksi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 22. helmikuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Syntymäpäiväparadoksi on väite, jonka mukaan vähintään 23 hengen ryhmässä syntymäpäivien (päivän ja kuukauden) yhteensattumistodennäköisyys vähintään kahdelle henkilölle on yli 50 % . Esimerkiksi, jos luokassa on 23 tai enemmän oppilasta, on todennäköisempää, että luokkatovereiden parilla on syntymäpäivä samana päivänä, kuin että jokaisella on yksilöllinen syntymäpäivä [1] . Tätä ongelmaa pohti ensimmäisen kerran Richard Mises vuonna 1939 [2] [3] .

57 tai useammalla ihmisellä tällaisen yhteensattuman todennäköisyys ylittää 99 % , vaikka se saavuttaa 100 % Dirichlet-periaatteen (maalaisjärki) mukaan vain silloin, kun ryhmässä on vähintään 367 henkilöä (täsmälleen 1 enemmän kuin määrä päivien lukumäärä karkausvuodessa ; karkausvuodet huomioon ottaen ).

Tällainen väite saattaa tuntua epäselvältä, koska todennäköisyys, että kahden henkilön syntymäpäivät osuvat yhteen vuoden minkä tahansa päivän kanssa , kerrottuna ryhmän henkilömäärällä (23), antaa vain . Tämä päättely on virheellinen, koska mahdollisten parien määrä ylittää merkittävästi ryhmän henkilöiden määrän ( 253 > 23 ). Lausunto ei siis ole paradoksi tiukassa tieteellisessä mielessä: siinä ei ole loogista ristiriitaa, ja paradoksi piilee vain eroissa ihmisen intuitiivisen tilanteen havainnoinnin ja matemaattisen laskelman tulosten välillä. $({\tfrac {1}{365}}=0{,}27\,\%)$ ${\tfrac {1}{365}}\times 23=6{,}3\,\%$ $({\tfrac {23\times 22}{2}}=253)$

Intuitiivinen havainto

23 hengen ryhmässä todennäköisyys, että kahdella ihmisellä on sama syntymäpäivä, on niin suuri, koska otetaan huomioon todennäköisyys, että kahdella henkilöllä on sama syntymäpäivä. Tämä todennäköisyys määräytyy 23 ihmisen parien lukumäärän perusteella. Koska ihmisten järjestyksellä pareittain ei ole väliä, tällaisten parien kokonaismäärä on yhtä suuri kuin yhdistelmien lukumäärä 23 x 2, eli (23 × 22) / 2 = 253 paria .

Paradoksin muotoilussa puhumme minkä tahansa kahden ryhmän jäsenen syntymäpäivien yhteensattumisesta. Yksi yleinen väärinkäsitys on, että tämä tapaus sekoitetaan toiseen näennäisesti samankaltaiseen tapaukseen, jossa yksi henkilö valitaan ryhmästä ja arvioidaan todennäköisyys, että minkä tahansa ryhmän muiden jäsenten syntymäpäivä osuu valitun henkilön syntymäpäivään. Jälkimmäisessä tapauksessa osuman todennäköisyys on paljon pienempi.

Todennäköisyyslaskenta

On määritettävä todennäköisyys, että n henkilön ryhmässä vähintään kahdella heistä on sama syntymäpäivä.

Jakakoon syntymäpäivät tasaisesti , eli oletetaan, että:

vuodessa on 365 päivää (ei karkausvuosia );
ryhmässä ei ole ihmisiä, jotka ovat ilmeisesti syntyneet samana päivänä (esim. kaksoset );
syntyvyys ei riipu viikonpäivästä, vuodenajasta ja muista tekijöistä.

Todellisuudessa tämä ei ole täysin totta - erityisesti joissakin maissa sairaaloiden luonteen vuoksi lapsia syntyy enemmän tiettyinä viikonpäivinä. Epätasainen jakautuminen voi kuitenkin vain lisätä syntymäpäivien sattuman todennäköisyyttä, mutta ei vähentää: jos kaikki ihmiset syntyisivät vain 3 päivänä 365:stä, syntymäpäivien yhteensattumistodennäköisyys olisi erittäin korkea.

Lasketaan ensin todennäköisyys, että ihmisryhmässä kaikkien ihmisten syntymäpäivät ovat erilaiset. Jos , niin Dirichlet-periaatteen nojalla todennäköisyys on nolla. Jos , niin väittelemme seuraavasti. Otetaan satunnaisesti yksi henkilö ryhmästä ja muistetaan hänen syntymäpäivänsä. Sitten otetaan toinen henkilö satunnaisesti, kun taas todennäköisyys, että hänen syntymäpäivänsä ei ole sama kuin ensimmäisen henkilön syntymäpäivä, on yhtä suuri kuin . Ota sitten kolmas henkilö; todennäköisyys, että hänen syntymäpäivänsä ei ole sama kuin jommankumman syntymäpäivä kahdesta ensimmäisestä, on yhtä suuri kuin . Analogisesti väittelemällä saavutamme viimeisen henkilön, jonka todennäköisyys, että hänen syntymäpäivänsä ei täsmää kaikkiin edellisiin, on yhtä suuri kuin . Kun kaikki nämä todennäköisyydet kerrotaan, saadaan todennäköisyys, että kaikki ryhmän syntymäpäivät ovat erilaisia: ${\bar p}(n)$ $n$ $n > 365$ ${\bar p}(n)$ $n\leqslant 365$ $1-{\frac {1}{365}}$ $1-{\frac {2}{365}}$ $1-{\frac {n-1}{365}}$

{\bar p}(n)=

\left(1-{\frac {1}{365}}\right)\cdot \left(1-{\frac {2}{365}}\right)\cdot \ldots \cdot \left( 1-{\frac {n-1}{365}}\oikea)=

{365\cdot 364\cdot \ldots \cdot (365-n+1) \over 365^{n}}=

{365!  \over 365^{n}(365-n)!}.

Tällöin todennäköisyys, että vähintään kahdella henkilöllä n :stä on sama syntymäpäivä, on yhtä suuri

p(n)=1-{\bar p}(n).

Tämän funktion arvo ylittää 1/2 kohdassa , kun taas sattuman todennäköisyys on noin 50,73 % ja . Luettelo n arvoista ja niitä vastaavista todennäköisyyksistä on annettu seuraavassa taulukossa. $n = 23$ $p(22)\noin 47,57\%$

n	p ( n )
kymmenen	12 %
kaksikymmentä	41 %
kolmekymmentä	70 %
viisikymmentä	97 %
100	99,99996 %
200	99,99999999999999999999999999998 %
300	(1 − 7 × 10 −73 ) × 100 %
350	(1 − 3 × 10 −131 ) × 100 %
367	100 %

Tämä ongelma voidaan muotoilla uudelleen klassiseksi "sattumaongelmaksi". Päästää:

uurna sisältää palloja (tässä tapauksessa päivien lukumäärä vuodessa, oletetaan olevan 365 päivää); $M$ $M$
pallot numeroitu 1, 2, …, ; $M$
useita näytteitä tehdään n pallosta uurnasta (tässä tapauksessa n on ryhmän ihmisten lukumäärä);
vedetyt pallot palautetaan uurnaan jokaisen valinnan jälkeen;
näytteet katsotaan tilatuiksi, eli näytteitä ja niitä pidetään erilaisina. $\{ 1, 2, 4, 6 \}$ $\{ 4, 2, 6, 1 \}$

On laskettava tapahtuman todennäköisyys, jos otoksessa ei esiinny toistoja. Kaikki laskelmat ovat samat kuin edellä .

Vaihtoehtoinen menetelmä

Todennäköisyys, että n: n ryhmän kahdella ihmisellä on sama syntymäpäivä , voidaan laskea myös kombinatorisilla kaavoilla [4] . Kuvittele, että jokainen vuoden päivä on yksi kirjain aakkosissa ja aakkoset koostuvat 365 kirjaimesta. N: n ihmisen syntymäpäivä voidaan esittää merkkijonolla, joka koostuu n :stä tämän aakkoston kirjaimesta. Hartleyn kaavan mukaan mahdollisten rivien määrä on

n_{\text{total}}=365^{n}.

Mahdollisten merkkijonojen määrä , joissa kirjaimet eivät toistu ( sijoittelu 365 x n ) on

n_{\text{unique}}={\frac {365!}{(365-n)!}}.

Jos rivit valitaan satunnaisesti ( tasaisella jakautumisella ), on todennäköisyys valita rivi, jossa vähintään kaksi kirjainta täsmää.

p(n)=1-{\frac {n_{\teksti{ainutlaatuinen))}{n_{\teksti{yhteensä))))=1-{\frac {\frac {365!}{(365) -n)!}}{365^{n}}}

klo ja

n\leqslant 365

p(n)=1

osoitteessa .

n>365

Tällä tavalla,

{\frac {\left({\frac {365!}{(365-n)!}}\right)}{365^{n}}}={\frac {365\cdot 364\cdot 363 \cdots (365-n+1)}{365^{n}}}={}

{\frac {365}{365}}\cdot {\frac {364}{365}}\cdot {\frac {363}{365}}\cdots {\frac {365-n+1}{ 365}}={}

1\cdot \left(1-{\frac {1}{365}}\right)\cdot \left(1-{\frac {2}{365}}\right)\cdots \left(1 -{\frac {n-1}{365}}\oikea),

ja tämä lauseke vastaa yllä esitettyä lauseketta .

Myös mahdollisten rivien kokonaismäärä voidaan laskea käyttämällä kombinatoriikkakaavaa toistojen A (toistot)  n /365 = 365 n sijoittelujen lukumäärälle .

Arviot

Eksponentiaalinen funktio

Eksponentiaalisen funktion Taylor -sarjan laajennuksen käyttäminen

e^{x}=1+x+{\frac {x^{2}}{2!}}+\ldots ,

Yllä oleva lauseke voidaan arvioida seuraavasti : ${\bar p}(n)$

{\bar p}(n)\noin 1\cdot e^{{-1/365}}\cdot e^{{-2/365}}\cdots e^{{-(n-1)/365} }=

1 \cdot e^{ -( 1 + 2 + \ cdots + ( n - 1 ) )/365 } =

e^{ -\frac{ n(n-1) }{ 2 \cdot 365 } } .

Näin ollen:

p(n)=1-{\bar p}(n)\noin 1-e^{{-{\frac {n(n-1)}{2\cdot 365))))

Huomaa, että yksinkertaistettu approksimaatio

p(n)\noin 1-e^{{-{\frac {n^{2}}{2\cdot 365}}}},

kuten kaaviosta näkyy, se antaa silti riittävän tarkkuuden.

Tehdään vielä yksi likiarvo .

Todennäköisyys, että kahdella ihmisellä on sama syntymäpäivä, on 364/365. Ryhmässä ihmisiä , pariskuntia. Siksi todennäköisyys , jos nämä tapahtumat ovat riippumattomia , voidaan arvioida numerolla $n$ $C(n,2)={\frac {n(n-1)}{2}}$ ${\bar p}(n)$

\left({\frac {364}{365}}\oikea)^{{C(n,2)}}.

Siksi saamme likiarvon vaaditulle todennäköisyydelle p ( n ) :

p(n)\noin 1-\vasen({\frac {364}{365}}\oikea)^{{C(n,2))).

Poisson approksimaatio

Käyttämällä Poisson - approksimaatiota binomille , joka perustuu edelliseen likiarvoon , saamme hieman yli 50 % : $p(n)$

\operaattorinnimi{Poi} \left( \frac{ C(23,2) }{365} \right) = \operaattorinimi{Poi} \left( \frac{253}{365} \right) \noin \operaattorinimi{Poi }( 0{,} 693\, 2 );

\mathbb{P} \left( \{ X>0 \} \right) = 1 - \mathbb{P} \left( \{X=0\} \right) = 1 - e^{ -0{,} 693\,2 } = 1 - 0{,}499\,998 = 0{,}500\,002 .

Ihmisten lukumäärän laskeminen, jonka todennäköisyys on 50 %

Ilmaistaan n yllä olevasta kaavasta . Sitten p ( n ) sijaan korvaamme 50 % (0,5). Tuloksena saamme: ${\displaystyle p(n)=1-{\bar {p}}(n)\noin 1-e^{-{\frac {n(n-1)}{2\cdot 365))))$

n\noin {\frac {1}{2}}+{\sqrt {{\frac {1}{4}}-2\cdot 365\cdot \ln 0{,}5}}=22{ ,}9999.

On toinenkin tapa arvioida n 50 % :n todennäköisyydellä . Kuten edellä on todistettu :

{\bar {p}}(n)=1-p(n)=\prod _{k=1}^{n-1}\left(1-{\frac {k}{365}} \oikea).

Etsi pienin n jolle

p(n)>{\frac {1}{2))

tai mikä on sama,

{\bar {p}}(n)<{\frac {1}{2}}.

Käytetään yllä olevaa funktion approksimaatiota eksponentiaalisella funktiolla : ${\bar p}(n)$

{\bar {p}}_{\text{approx}}(n)=\prod _{k=1}^{n-1}e^{\frac {-k}{365}}= e^{\frac {-n(n-1)}{2\cdot 365)).

Korvaamalla sen sijaan lausekkeen , saamme ${\bar {p}}_{\text{approx}}(n)$ ${\bar p}(n)$ ${\bar {p}}(n)<{\frac {1}{2}}$

e^{\frac {-n(n-1)}{2\cdot 365}}<{\frac {1}{2}}.

Ratkaisemalla n , saamme

n^{2}-n>2\cdot 365\cdot \ln 2.

Täältä löydämme n ja pyöristetään ylöspäin kokonaislukuun :

n = 23 .

Syntynyt samana päivänä tietyn henkilön kanssa

Verrataan todennäköisyyttä p ( n ) todennäköisyyteen, että n henkilön ryhmässä jonkun ryhmään kuuluvan henkilön syntymäpäivä osuu jonkin ennalta valitun henkilön syntymäpäivään, joka ei kuulu ryhmään. Tämä todennäköisyys on

q(n)=1-\left({\frac {365-1}{365}}\oikea)^{n}.

Kun n = 23 korvataan , saadaan q ( n ) ≈ 6,12 % . Jotta todennäköisyys q ( n ) ylittää 50 % , ryhmän ihmisten lukumäärän on oltava vähintään 253 ( q (252) ≈ 49,91 % ; q (253) ≈ 50,05 % ). Tämä luku on yli puolet vuoden päivistä ( 365/2 = 182,5 ); tämä johtuu siitä, että muilla ryhmän jäsenillä voi olla sama syntymäpäivä, mikä pienentää todennäköisyyttä q ( n ) . Tarkemmin sanottuna tämä johtuu siitä, että kun yhteensattumien todennäköisyyksiä lasketaan yhteen, vähennämme joka kerta näiden tapahtumien yhteisen esiintymistodennäköisyyden, koska tapahtumat ovat yhteisiä ja niiden yhteisen esiintymistodennäköisyys otetaan huomioon summauksessa. kahdesti. P ( A + B ) = P ( A ) + P ( B ) − P ( AB ) ja niin edelleen jokaisen uuden termin lisäyksen yhteydessä.

Yleistykset

Diskreettien satunnaismuuttujien yhteensattuma

Kuvattu ongelma voidaan muotoilla yleisessä muodossa:

annetut satunnaisluvut;
satunnaisluvut jakautuvat tasaisesti välillä 1 - d ;
n on satunnaislukujen lukumäärä;
määrittää p ( n ; d ) - todennäköisyys , että vähintään kaksi annetuista luvuista täsmää.

Jos perustelet samalla tavalla kuin yllä , voit saada yleisiä ratkaisuja:

p(n;d)={\begin{cases}1-\prod _{{k=1}}^{{n-1}}\left(1-{k \over d}\right)&n\leq d\\1&n>d\end{cases}};

p(n;d)\noin 1-e^{{-(n(n-1))/2d}};

q(n;d)=1-\left({\frac {d-1}{d}}\right)^{n}.

Käänteinen ongelma:

annettu p on todennäköisyys, että vähintään kaksi satunnaislukua täsmää;
tiedetään, että satunnaisluvut jakautuvat tasaisesti välillä 1 - d ;
find n ( p ; d ) — satunnaislukujen lukumäärä.

Ratkaisu:

n(p;d)\noin {\sqrt {2d\cdot \ln \left({1 \over 1-p}\right))).

Useita ihmisiä

Yllä esiteltiin syntymäpäiväparadoksi yhdelle "ihmistyypille". Ongelmaa voidaan yleistää ottamalla käyttöön useita "tyyppejä", esimerkiksi jakamalla ihmiset miehiin ( m ) ja naisiin ( n ). Lasketaan todennäköisyys, että vähintään yhdellä naisella ja yhdellä miehellä on sama syntymäpäivä (kahden naisen tai kahden miehen syntymäpäivien yhteensopivuutta ei oteta huomioon):

p_{0}=1-{\frac {1}{d^{{m+n))))\sum _{{i=1}}^{m}\sum _{{j=1}}^ {n}S_{2}(m,i)S_{2}(n,j)\prod _{{k=0}}^{{i+j-1}}(dk),

missä d \u003d 365 ja S 2 () ovat toisen tyyppisiä Stirling-lukuja . Mielenkiintoista on, että kysymykseen n + m :n arvosta tietyllä todennäköisyydellä ei ole yksiselitteistä vastausta. Esimerkiksi todennäköisyys 0,5 antaa sekä 16 miehen ja 16 naisen joukon että 43 miehen ja 6 naisen joukon.

Läheiset syntymäpäivät

Toinen syntymäpäiväparadoksin yleistys on ilmaista ongelma, kuinka monta ihmistä tarvitaan, jotta todennäköisyys kuulua sellaiseen ihmisryhmään, jonka syntymäpäivät eroavat enintään yhden päivän (tai kahdella, kolmella päivällä ja niin edelleen) ylittää 50 % . . Tätä ongelmaa ratkaistaessa käytetään inkluusio-poissulkemisperiaatetta . Tulos (jälleen olettaen, että syntymäpäivät jakautuvat tasaisesti ) on:

Suurin ero syntymäpäivissä, päivien lukumäärässä	Vaadittu henkilömäärä
yksi	23
2	neljätoista
3	yksitoista
neljä	9
5	kahdeksan
6	kahdeksan
7	7
kahdeksan	7

Todennäköisyys, että jopa 7 hengen ryhmässä heistä vähintään kahden syntymäpäivät eroavat enintään viikon verran, on siis yli 50 % .

Sovellus

Syntymäpäiväparadoksi pätee yleisesti hash-funktioihin : jos hash-funktio tuottaa N - bittisen arvon, niin satunnaisten syötteiden lukumäärä, joiden hash-koodit erittäin todennäköisesti törmäävät (eli eri syöttötiedoilla on samat hajakoodit). ) ei ole 2 N , vaan vain noin 2 N /2 . Tätä havaintoa hyödynnetään hyökkäyksessä kryptografisia hajautustoimintoja vastaan, jota kutsutaan syntymäpäivähyökkäykseksi .

N	Erilaisten ulostuloketjujen määrä (2 N )	Vähintään yhden törmäyksen todennäköisyys ( p )
N	Erilaisten ulostuloketjujen määrä (2 N )	10-18 _	10-15 _	10-12 _	10-9 _	10-6 _	0,1 %	yksi %	25 %	viisikymmentä %	75 %
32	4,3 × 109	2	2	2	2.9	93	2,9 × 10³	9,3 × 10³	5,0 × 10⁴	7,7 × 10⁴	1,1 × 10⁵
64	1,8 × 10 19	6.1	1,9 × 10²	6,1 × 10³	1,9 × 10⁵	6,1 × 10⁶	1,9 × 10⁸	6,1 × 10⁸	3,3 × 10⁹	5,1 × 10⁹	7,2 × 10⁹
128	3,4 × 10 38	2,6 × 10 10	8,2 × 10 11	2,6 × 10 13	8,2 × 10 14	2,6 × 10 16	8,3 × 10 17	2,6 × 10 18	1,4 × 10 19	2,2 × 10 19	3,1 × 10 19
256	1,2 × 10 77	4,8 × 10 29	1,5 × 10 31	4,8 × 10 32	1,5 × 10 34	4,8 × 10 35	1,5 × 10 37	4,8 × 10 37	2,6 × 10 38	4,0 × 10 38	5,7 × 10 38
384	3,9 × 10 115	8,9 × 10 48	2,8 × 10 50	8,9 × 1051	2,8 × 1053	8,9 × 1054	2,8 × 1056	8,9 × 1056	4,8 × 1057	7,4 × 1057	1,0 × 10 58
512	1,3 × 10154	1,6 × 10 68	5,2 × 10 69	1,6 × 10 71	5,2 × 1072	1,6 × 1074	5,2 × 1075	1,6 × 10 76	8,8 × 1076	1,4 × 10 77	1,9 × 10 77

Valkoiset solut osoittavat ryhmän ihmisten määrän, jolla törmäys tapahtuu tietyllä todennäköisyydellä (paradoksin mukaisesti tulosketjujen lukumäärä on 365).

Samankaltaisella matemaattisella laitteistolla arvioidaan järvissä elävien kalojen populaatiokokoa . Menetelmää kutsutaan "capture-recapture" ("catch - catch again"). Itse asiassa, jos jokainen pyydetty kala merkitään ja vapautetaan, merkityn kalan pyyntitodennäköisyys kasvaa epälineaarisesti (yllä olevan kaavion mukaisesti) yritysten lukumäärän kasvaessa. Populaation koko voidaan karkeasti arvioida niiden yritysten lukumäärän neliönä, jotka on tehty ennen kuin ensimmäinen merkitty kala saadaan kiinni.

Ongelman ratkaisu yleisesti ottaen löytää sovelluksen monilla matematiikan aloilla , esimerkiksi ei-deterministisissa faktorointialgoritmeissa . Joten yksi yksinkertaisimmista Pollardin ρ-menetelmän selityksistä on samanlainen kuin syntymäpäiväparadoksin selitys: riittää, että on suunnilleen satunnaisia lukuja välillä 0 - , missä ovat alkulukuja, jotta ainakin yhdelle lukuparista, jolla on suurella todennäköisyydellä on , joka on luvun n jakaja . $\sqrt{p}$ $n=pq$ $p<q$ $\gcd \left(|xy|,n\right)>1$

Käänteiset ongelmat

Etsitään pienin luku n , jonka todennäköisyys p ( n ) on suurempi kuin annettu luku p .

Suurimman luvun n löytäminen siten, että todennäköisyys p ( n ) on pienempi kuin annettu luku p .

Yllä olevan kaavan avulla saamme:

n(p;365)\noin {\sqrt {2\cdot 365\cdot \ln \left({1 \over 1-p}\right))).

s	n	n ↓	p ( n ↓)	n ↑	p ( n ↑)
0,01	0,14178√365 = 2,70864	2	0,00274	3	0,00820
0,05	0,32029√365 = 6,11916	6	0,04046	7	0,05624
0.1	0,45904√365 = 8,77002	kahdeksan	0,07434	9	0,09462
0.2	0,66805√365 = 12,76302	12	0,16702	13	0,19441
0.3	0,84460√365 = 16,13607	16	0,28360	17	0,31501
0.5	1,17741√365 = 22,49439	22	0,47570	23	0,50730
0.7	1,55176√365 = 29,64625	29	0,68097	kolmekymmentä	0,70632
0.8	1,79412√365 = 34,27666	34	0,79532	35	0,81438
0.9	2,14597√365 = 40,99862	40	0,89123	41	0,90315
0,95	2,44775√365 = 46,76414	46	0,94825	47	0,95477
0,99	3,03485√365 = 57,98081	57	0,99012	58	0,99166

Paras sijoitus

Olkoon huoneessa n - 1 henkilöä, ja heidän syntymäpäivänsä ovat erilaisia. Olkoon g ( n ) todennäköisyys, että sisään tulleen henkilön syntymäpäivä on sama kuin jonkun huoneessa olevan henkilön syntymäpäivä. On löydettävä n: n arvo, jolla funktion g ( n ) arvo on suurin.

Ratkaisu on lausekkeen maksimiarvon löytäminen

p ( n ) -p ( n - 1) .

Käyttämällä yllä olevaa kaavaa p ( n ) : lle saadaan n = 20 .

Keskimääräinen henkilömäärä

Pohditaanpa toista ongelmaa. Kuinka monta ihmistä keskimäärin tarvitaan, että vähintään kahdella heistä on sama syntymäpäivä?

Tämä ongelma liittyi hajautusalgoritmeihin , ja Donald Knuth tutki sitä . Osoittautuu, että meitä kiinnostavalla satunnaismuuttujalla on matemaattinen odotusarvo

\overline {n}\,=\,1+Q(M),

missä

Q(M)=\sum _{{k=1}}^{{M}}{\frac {M!}{(Mk)!M^{k}}}.

Toiminto

Q(M)\,=\,1+{\frac {M-1}{M}}+{\frac {(M-1)(M-2)}{M^{2}}}+\cdots +{\frac {(M-1)(M-2)\cdots 1}{M^{{M-1))))

tutkija Ramanujan . Hän sai myös seuraavan asymptoottisen laajennuksen tälle funktiolle :

Q(M)\sim {\sqrt {{\frac {\pi M}{2))))-{\frac {1}{3}}+{\frac {1}{12}}{\sqrt { {\frac {\pi }{2M)))-{\frac {4}{135M))+\cdots .

Kun M = 365 , keskimääräinen ihmisten lukumäärä on

{\overline {n}}\,=\,1+Q(M)\noin 24.61658.

Tämä luku on hieman suurempi kuin niiden ihmisten määrä, jotka tarjoavat 50 % :n mahdollisuuden . Yllättäen vaadittu henkilömäärä on M + 1 = 366 (365 henkilön syntymäpäivät voidaan jakaa jokaiselle vuoden 365 päivälle ilman päällekkäisyyttä), vaikka keskimäärin tarvitaan vain 25.

Katso myös

Muistiinpanot

↑ Mazur, 2017 , s. 116.
↑ Mazur, 2017 , s. 119.
↑ Mironkin V. O., Chukhno A. B. Yhdestä "syntymäpäivien" paradoksien yleistyksestä . Haettu 30. maaliskuuta 2020. Arkistoitu alkuperäisestä 9. heinäkuuta 2020. (määrätön)
↑ Mazur, 2017 , s. 117.

Kirjallisuus

Kemeny J. , Snell J., Thompson J. Introduction to Finite Mathematics = Introduction to Finite Mathematics. - Ulkomaisen kirjallisuuden kustantamo, 1963. - 488 s.
Kozlov MV Todennäköisyysteorian elementit esimerkeissä ja tehtävissä. - Moskovan valtionyliopisto, 1990 . — ISBN 5-211-00312-8 .
Mazur, Joseph. Syntymäpäiväongelma // Onnenpeli. Matematiikka ja sattuman mytologia. - Alpina tietokirjallisuus, 2017. - S. 116-123. — 292 s. - ISBN 978-5-91671-636-8 .
Sekey G. Paradokseja todennäköisyysteoriassa ja matemaattisissa tilastoissa. - RHD, 2003 . — ISBN 5-93972-150-8 .
Shiryaev A. N. Todennäköisyys-1. - MTsNMO, 2007 . - ISBN 978-5-94057-036-3 .
Goldberg S. Suora hyökkäys syntymäpäiväongelmaan // Mathematical Mathematics Magazine. – toukokuu 1976 . — Iss. 49 . - s. 130-132 .

Mosteller F. Syntymäpäiväongelman ymmärtäminen // Matematiikan opettaja. – toukokuuta 1962 . - s . 322-325 . _

Linkit

Todennäköisyysteorian paradoksit .
PGP-algoritmien vertaileva katsaus. "Syntymäpäivien" paradoksi ja kryptografian turvallisuus .
Eurobirthdays 2012 (englanniksi) . Käytännön esimerkki.