Respuesta :
Answer:
The birthday paradox :
How many people must there be in a room before there is a 50% chance that two of them were born on the same day of the year?
The answer is surprisingly few
The paradox is that it is in fact far fewer than the number of days in a year, or even half the number of days in a year
Explanation:
An analysis using indicator random variables
We use indicator random variables to provide a simple but approximate analysis of the birthday paradox
For each pair ( i, j ) of the ݇k people in the room, define the indicator random variable X ij, for
1 ≤ i ∠ j ≤ k , by
X ij = I {i and j have the same birthday}
= {1 i and j have the same birthday
0 otherwise
Once birthday bi for i is chosen, the probability that bj is chosen to be the same day is 1/n,
where n = 365
E [ Xij ] = Pr { i and j have the same birthday = 1/n
Let X be a random variable counting the number of pairs of individuals having the same birthday
k k
X = ∑ ∑ Xij
i = 1 j = i + 1
Taking expectations of both sides and applying linearity of expectation, we obtain:
Е [ X ] = Е [ k k ] k k
∑ ∑ Xij = ∑ ∑ Е [Xij ]
i = 1 j = i + 1 i = 1 j = i
= ( k ) 1 = k ( k - 1 )
2 n 2n
When k ( k - 1 ) ≥ 2 , the expected number of pairs of people with the same birthday is at least 1
Thus, if we have at least √ 2n + 1 individuals in a room, we can expect at least two to have the same birthday.
For n = 365, if k = 28, the expected number of pairs with the same birthday is
(28 · 27) / (2 · 365) ≈ 1.0356
With at least 28 people, we expect to find at least one matching pair of birthdays
Analysis done using only probabilities gives a different exact number of people, but same asymptotically:
Θ ( √n )
