Here is another question from the book of V. Rohatgi and A. Saleh. I would like to ask help again. Here it goes:
Consider a town with $N$ people. A person sends two letters to two separate people, each of whom is asked to repeat the procedure. Thus for each letter received, two letters are sent out to separate persons chosen at random (irrespective of what happened in the past). What is the probability that in the first $n$ stages the person who started the chain letter game will not receive a letter?
I am thinking of solving this through complementation, i.e. what I have so far is that for $n=1$, $$P\{\text{the person who started the chain letter game will receive a letter}\}=0$$ for $n=2$, $$P\{\text{the person who started the chain letter game will receive a letter from the 1st sender}\}$$ $$=P\{\text{the person who started the chain letter game will receive a letter from the 2nd sender}\}$$ $$=\frac{_{N-2}C_1}{_{N-1}C_2}$$ $$P\{\text{the person who started the chain letter game will receive letters from both 2nd senders}\}$$ $$=\left(\frac{_{N-2}C_1}{_{N-1}C_2}\right)^2$$ Then I would simply calculate the probability of the union of the elementary events, then continue for each $n$. Now, I find it too tedious and I am not so sure if this correct. Can anyone help please? Thanks.
Best Answer
Let stage $k=0$ denote the person who started the chain (say A) sending out the first two letters to two different people. I assume you are asking for the probability that after stage $k=n$, A does not receive a letter.
Further, as per the problem statements, even if a person receives $m>1$ letters in a stage or across stages, all that is taken care of is that each letter results in a pair of letters going out to two separate people, irrespective of whether they were recipients of other letters by the same sender.
In this situation, we worry only about how many such letter pairs are sent across stages $k=1,2, ...n$. This is $L = 2+4+... 2^n = 2(2^n-1)$.
Each time a letter is received, there are $(N-1)(N-2)$ ways to select two separate people to send a letter pair to. If A is not to be one of them, this choice reduces to $(N-2)(N-3)$. Hence the probability for A not receiving a letter at this time is
$p = \dfrac{(N-2)(N-3)}{(N-1)(N-2)} = \dfrac{N-3}{N-1}$.
As this event occurs independently $L$ times, the total probability is $p^L = \left( \dfrac{N-3}{N-1}\right)^{2(2^n-1)}$.