Average number of people required to find a pair with same birthday

Question

I have to find the expected number of people required to find a pair with same birthday. This is what I tried:

Assume that there are $M$ possible birthdays, then following the definition for expected number: $$E[X] = \sum_{x=2}^{x=M+1} xP[X = x] = \sum_{x=2}^{x=M+1} x \left[ \frac{M!(x-1)}{(M-x+1)! M^{x}} \right]$$

However, this is completely different from what is mentioned here as .

$$E[X]=1+\sum_{k=1}^{M} \frac{M!}{(M-k)! M^k}.$$

Are these expressions equivalent ? How to prove it ?

Answer 1

Consider $$ A = \sum_{x=2}^{M+1} \frac{M!x(x-1)}{(M-x+1)! M^{x}},\qquad B=\sum_{k=1}^{M} \frac{M!}{(M-k)! M^k}. $$ Then, using $x-1=M-(M-x+1)$ in the numerators of $A$, one gets $A=C-D$ with $$ C= \sum_{x=2}^{M+1} \frac{M!x}{(M-x+1)! M^{x-1}},\qquad D=\sum_{x=2}^{M}\frac{M!x}{(M-x)! M^{x}}. $$ Using $x=M+1-(M-x+1)$ in $C$ and $x=M-(M-x)$ in $D$, one gets $C=E-F$ and $D=G-H$ with $$ E= \sum_{x=2}^{M+1} \frac{(M+1)!}{(M-x+1)! M^{x-1}},\qquad F=\sum_{x=2}^{M} \frac{M!M}{(M-x)! M^{x}}, $$ and $$ G=\sum_{x=2}^{M}\frac{M!M}{(M-x)! M^{x}},\qquad H=\sum_{x=2}^{M-1}\frac{M!}{(M-x-1)! M^{x}}. $$ Using $x=k+1$ in $E$ yields $$ E=(M+1)B. $$ Adding the $x=1$ term in $F=G$ and using $x=k$ yields $$ F=G=M(B-1). $$ Using $x=k-1$ in $H$ yields $$ H=\sum_{k=3}^{M}\frac{M!M}{(M-k)! M^{k}}=M\left(B-1-\frac{M-1}M\right)=M(B-2)+1. $$ Thus, $$ A=E-F-G+H=(M+1)B-2M(B-1)+M(B-2)+1=1+B. $$

Answer 2

We can also get the second expression using linearity of expected value.

Let $X_i$ be the random variable which is $1$ if there was no pair among first $(i-1)$ persons having same birthday(which hence implies that $i$th person is needed) and $0$ otherwise.Then: $$X = \sum_{i=1}^{M+1} X_i$$ Using linearity of expected value:

$$E[X] = \sum_{i=1}^{M+1} E[X_i] = \sum_{i=1}^{M+1} \Pr[X_i = 1]$$ Now $\Pr[X_i = 1]$ will simply be equal to the probability the we have a sequence of $(i-1)$ distinct birthdays. $$\Pr[X_i = 1] = \frac{M!}{(M-i+1)!M^{i-1}}$$Substituting in the above expression, we get: $$E[X] = \sum_{i=1}^{M+1} \frac{M!}{(M-i+1)!M^{i-1}}$$ Using $k = i - 1$ and starting the sum from $i=1$ yields: $$E[X] = 1 + \sum_{k=1}^{M} \frac{M!}{(M-k)!M^k}$$ which is the required expression.

Answer 3

You can just use this formula for the expected value https://en.wikipedia.org/wiki/Expected_value#Formula_for_non-negative_random_variables

$$\operatorname{E}[X]=\sum _{k=1}^\infty \operatorname{P}(X\geq k).$$

In your case X is the random variable "first person to have a repeated birthday". We know that $$P(X\geq 1)=1$$ $$P(X\geq M+2)=0 $$ $$P(X\geq k+1)= \frac{M!}{(M-k)! M^k}$$ and we can easily deduce the wanted formula $$ E[X] = 1 + \sum_{k=1}^{M} \frac{M!}{(M-k)!M^k}. $$