Variant of the birthday problem

Question

I would like to ask help regarding an example given in the book of V. Rohatgi and A. Saleh. I think this is a variant of the birthday problem. Here it goes:

Consider a class of $r$ students. The birthdays of these $r$ students form a sample of size $r$ from the 365 days in the year. Next suppose that each of the $r$ students is asked for his or her birth date in order, with the instruction that as soon as a student hears his or her birth date the student is to raise a hand. Let us compute the probability that a hand is first raised when the $k^{th}$ ($k = 1, 2, $...$ , r$) student is asked his or her birth date. Let $p_k$ be the probability that the procedure terminates at the $k_{th}$ student. Then $$p_1 = 1-\left(\frac{364}{365}\right)^{r-1}$$ and $$p_k=\frac{_{365}P_{k-1}}{365^{k-1}}\left(1-\frac{k-1}{365}\right)^{r-k+1}\left[1-\left(\frac{365-k}{365-k+1}\right)^{r-k}\right], k=2,3,...,r$$

What I would like to ask then is how were these answers obtained? I think it would be better that someone help me in understanding the problem "concretely" since I actually cannot get the problem. Thanks.

Answer 1

Let $N=365$. A hand is first raised at time $k$ if:

• The birth dates of the $k$ first students are different.
• The birth date of each of the last $r-k$ students is not one of the $k-1$ birth dates of the $k-1$ first students.
• The birth date of at least one of the last $r-k$ students is also the birth date of student $k$.

Call $A_k$, $B_k$ and $C_k$ these three events. Then, $$ P[A_k]=\left(1-\frac1N\right)\left(1-\frac2N\right)\cdots\left(1-\frac{k-1}N\right). $$ Assuming $A_k$, $B_k$ happens if $r-k$ independent draws from a set of $N$ avoid $k-1$ values, thus $$ P[B_k\mid A_k]=\left(1-\frac{k-1}N\right)^{r-k}. $$ Assuming $A_k$ and $B_k$, $C_k$ does not happen if $r-k$ independent draws from a set of $N-k+1$ avoid $1$ value, thus $$ P[C_k^c\mid A_k,B_k]=\left(1-\frac{1}{N-k+1}\right)^{r-k}. $$ Finally, $$ p_k=P[A_k,B_k,C_k]=P[A_k]\cdot P[B_k\mid A_k]\cdot (1-P[C_k^c\mid A_k,B_k]). $$