1

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.

Aditya Hase
  • 8,851
aLLex
  • 23

1 Answers1

0

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*}

Mick A
  • 10,208