Pigeonhole – tai ne juodoji skylė studentui…

Spalio 14, Ketvirtadienis

„Anglono“ žodynas:
pigeonhole

1 uoksas/urvas uoloje, kuriame karvelis suka lizdą
2 dėžutė (prie sienos); (rašomojo stalo) skyrelis (dokumentams, korespondencijai)
3 (klasifikavimo) skyrelis
***
1 (iš)dėlioti (popierius) į stalčiukus/dėžutes
3 klasifikuoti, skirstyti;
***
Pigeonhole principle (Wikipedija)

A probabilistic generalization of the pigeonhole principle states that if n pigeons are randomly put into m pigeonholes with uniform probability 1/m, then at least one pigeonhole will hold more than one pigeon with probability
P(A)= 1 – (m(m − 1)(m − 2)…(m − n + 1))/m^n.

For n = 0 and for n = 1 (and m > 0), that probability is zero; in other words, if there is just one pigeon, there cannot be a conflict. For n > m (more pigeons than pigeonholes) it is one, in which case it coincides with the ordinary pigeonhole principle. But even if the number of pigeons does not exceed the number of pigeonholes (n ≤ m), due to the random nature of the assignment of pigeons to pigeonholes there is often a substantial chance that clashes will occur. For example, if 2 pigeons are randomly assigned to 4 pigeonholes, there is a 25% chance that at least one pigeonhole will hold more than one pigeon; for 5 pigeons and 10 holes, that probability is 69.76%; and for 10 pigeons and 20 holes it is about 93.45%. If the number of holes stays fixed, there is always a greater probability of a pair when you add more pigeons. This problem is treated at much greater length at birthday paradox.
*
A further probabilistic generalisation is that when a real-valued random variable X has a finite mean E(X), then the probability is nonzero that X is greater than or equal to E(X), and similarly the probability is nonzero that X is less than or equal to E(X). To see that this implies the standard pigeonhole principle, take any fixed arrangement of n pigeons into m holes and let X be the number of pigeons in a hole chosen uniformly at random. The mean of X is n/m, so if there are more pigeons than holes the mean is greater than one. Therefore, X is sometimes at least 2.
***
Kaip gaunama formulė?
Pastebėkime, kad sąlygoje yra frazė „bent vienas [narvelis, urvelis, stalčiukas…]“, todėl pritaikome priešingo įvykio tikimybės skaičiavimo formulę:
P(A) = 1 – P(neA).
„neA“ šiuo atveju yra įvykis, kad kiekvienas balandis patenka į tuščią narvelį. Kiekvienas iš m balandžių gali skristi į bet kurį iš n narvelių – taip gauname vardiklio formulę. Pirmasis balandis gali pasirinkti vieną iš m narvelių, antrasis – vieną iš (m-1) likusių tuščių narvelių ir t.t. – taip gauname skaitiklio formulę.
***
Labai tinka egzaminui, tiesa?
P.S. Rašoma ir Pigeon Hole

patiko(0)