# Figuring out the variance of the birthday paradox

Update to reflect what I think is the calculation for $$E[X_1\cdot X_2]$$

Given n people, if I want to estimate how many of them are likely to have an overlapping birthday with any other person, how do I calculate the variance? So far I have $$E[X]=n\cdot p$$ with $$n$$ as the number of people and $$p$$ the probability of any single person having an overlapping birthday

I think $$E[X_1\cdot X_2]$$ is as follows:

Using total probability+the fact that $$X_i$$ is an indicator variable: $$E[X_1\cdot X_2]=P_{X_1,X_2}(1)=P(X_1\cdot X_2 |X_1=1)+P(X_1\cdot X_2 |X_1=0)$$

Now again as $$X_i$$ is an indicator variable:

$$P(X_1\cdot X_2 |X_1=0)=0$$

Now from Bayes conditioning:

$$P(X_1\cdot X_2 |X_1=1)=P(X_1$$and$$X_2)\cdot P(X_2)$$

This is: $$P(X_1\cdot X_2 |X_1=1)\cdot (1-(\frac{364}{365})^n)$$

What I'm not sure about is whether: $$P(X_1$$and$$X_2)=(1-(\frac{363}{364})^{n-3}+ \frac{1}{365})$$

If I'm right:$$P(X_1\cdot X_2 |X_1=1)\cdot (1-(\frac{364}{365})^n)=(1-(\frac{363}{364})^{n-3}+ \frac{1}{365})\cdot (1-(\frac{364}{365})^n)=E[X_1\cdot X_2]$$

• It is probably $$V[X]=np(1-p)$$ – InterstellarProbe May 20 '19 at 17:58
• How did you reach that conclusion? – EliT May 20 '19 at 18:01
• Isn't there a connection $n$ and $p$? If you only count the birthdays of the $n$ people then $p=1-(364/365)^{n-1}$. – drhab May 20 '19 at 18:28
• Yes there is - However, how does that relate back to the variance? – EliT May 20 '19 at 18:33
• @InterstellarProbe Almost but not exactly. We are dealing with $X_1+\cdots+X_n$ where the $X_i$ have identical Bernoulli distribution. However the $X_i$ are not independent, and the distribution of $X_1+\cdots+X_n$ is not binomial. – drhab May 21 '19 at 9:52

For $$i=1,\dots,n$$ let $$X_i$$ take value $$1$$ if person $$i$$ shares his birthday with some of the other persons and let $$X_i$$ take value $$0$$ otherwise.

Then $$X=X_1+\cdots+X_n$$ is the number of persons that share their birthday with someone else of the persons.

For finding variance you can make use of the bilinearity of the covariance and of symmetry:$$\mathsf{Var}(X)=\mathsf{Cov}(X,X)=\sum_{i=1}^n\sum_{j=1}^n\mathsf{Cov}(X_i,X_j)=n\mathsf{Var}(X_1)+n(n-1)\mathsf{Cov}(X_1,X_2)$$

If $$p$$ is the probability of any singular person to share his birthday with someone else then $$\mathbb EX_1=P(X_1=1)=p=1-\left(\frac{364}{365}\right)^{n-1}$$Further we have:

$$\mathsf{Var}(X_1)=p(1-p)$$and: $$\mathsf{Cov}(X_1,X_2)=\mathbb EX_1X_2-\mathbb EX_1\mathbb EX_2=\mathbb EX_1X_2-p^2$$

So there is one thing left to find now which is: $$\mathbb EX_1X_2=P(X_1=1=X_2)$$

Can you find that yourself?

\begin{aligned}P\left(X_{1}=1=X_{2}\right) & =P\left(X_{1}=1\right)+P\left(X_{2}=1\right)+P\left(X_{1}=0=X_{2}\right)-1\\ & =2p-1+P\left(X_{1}=0=X_{2}\right)\\ & =2\left(1-\left(\frac{364}{365}\right)^{n}\right)-1+\frac{364}{365}\left(\frac{363}{365}\right)^{n-2}\\ & =1-2\left(\frac{364}{365}\right)^{n}+\frac{364}{365}\left(\frac{363}{365}\right)^{n-2} \end{aligned}
• Is it $(1-\frac{364}{365})\cdot (1-(\frac{363}{364})^{n-3}+\frac{1}{365})$? – EliT May 20 '19 at 18:56