Exercise 21, Ch. 2 from Feller's book
In a town a n+1 inhabitants, a person tells a rumor to a second person, who in turn repeats it to a third person, etc. At each step, the recipient of the rumor is chosen at random from the n people available. Find the probability that the rumor will be told r times without: a) returning to the originator, b) being repeated to any person. Do the same problem when at each step the rumor is told by one person to a gathering of N randomly chosen people. (The first question is the special case N=1).
The question is particularly answered here and here.
I solved cases where N=1, but do not understand solution with case a) for N people.
The solution is
$\displaystyle P={\left(1-\frac{N}{n}\right)}^{r-1}$ but I do not understand how it is deduced.
I will appreciate any help.
Best Answer
Let event $A_i,\; i=2,3,\ldots,r$ be the event that at the $i^{th}$ step the first person is excluded when $N$ people are chosen from $n$ people (the teller in each of these steps is not the first person).
For any step $i=2,3,\ldots,r$,
\begin{eqnarray*} P(A_i) &=& \dfrac{\text{#ways to choose $N$ people from $n-1$}}{\text{#ways to choose $N$ people from $n$}} \\ &&\\ &=& \binom{n-1}{N} \bigg/ \binom{n}{N} \\ && \\ &=& \dfrac{n-N}{n}. \end{eqnarray*}
Then, we require:
\begin{eqnarray*} P\left(\bigcap_{i=2}^r{A_i}\right) &=& \prod_{i=2}^r{P(A_i)} \\ &=& \left[\dfrac{n-N}{n}\right]^{r-1}. \end{eqnarray*}