1

Exercise 21 of chapter 2, section 10 of Feller's book "An Introduction to Probability Theory and Its Applications" read as follows:

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 book itself provide final answer (not the full solution) and for (a) the final answer is: $$\displaystyle{\left(1-\frac{N}{n}\right)}^{r-1}$$ for (b) part:

$$\frac{(n)_{Nr}}{({(n)_N})^r}$$

This particular question has been answered here, here and here. The first link answered the question for the special case N=1, the second link only addressed the (a) part of the question and the last one only (b) part. I have a problem reaching at the given answers of the book.


Before delving into the answers that have been provided in the above links, it is important to note that for me the question has not any ambiguity, but since some people in this community interpreted the question differently, it is good to bring up the two ways that the proposition "telling the rumor to a gathering of N people" has been interpreted. (i) telling all of the N people, (ii) telling one person among them. The (i) interpretation is natural to accept but at the second link above, the question is answered assuming the (ii) interpretation and the final answer of the book is reproduced (How do I know the answer assumed the (ii) interpretation? since it assumed after completing each step there are ${n-1 \choose N}$ favorable cases to calculate the probability, whereas assuming m person were presented to the rumor after a particular step, there are ${n-1 \choose N}^m$ favorable cases. Nevertheless It seems the (ii) interpretation is needed to arrive at the book's answer). The question at the third link above is asked assuming the (ii) interpretation, in which the original poster is corrected by respondents to take the (i) interpretation (again reproducing the book's answer) and that is the place that my problem arises. Here in the answer, Yuval (answering the (b) part) maintains that after N people have been chosen by the originator of the rumor, for every such case there exist ${n-N \choose N}$ cases, that this number should be multiplied to ${n \choose N}$. But I suppose after N people have been informed of the rumor, each one of them will tell a randomly chosen group of N people. So at the second step of propagation, assuming the rumor is not told twice to a same person, we should have $N^2$ new receiver of the rumor, hence: $${n \choose N}{{n-N \choose {\underbrace{N,N,...N}_{N\text{ times}}}{,n-N-{N^2}}}}$$ case for the rumor to propagate in two step and not encountering one person twice. I think two-step case is enough to show the difference between my approach and that of Yuval. So I find what Yuval has done there puzzling.
To summarize:
Interpretation (i) leads to book's given answer for (a) part but not to the (b) part. Interpretation (ii) neither lead to the given answer of the (a) part nor to the (b) part.
What am I missing here?
Thanks for your help.

Reza Hassani
  • 63
  • I don't see any ambiguity in the problem at all. For the first pass, you are to assume that the rumor is passed to a single individual (selected uniformly at random). Then, for the second pass, you are to assume that it is passed to a (uniformly selected) block of $N$ people. Of course the two answers must coincide if $N=1$. – lulu Jun 27 '23 at 11:16
  • 3
    It would be pointless to read it as saying that "first a block of $N$ is selected uniformly at random and then a single individual is selected uniformly at random from that block." With that reading, the selection of the $N$ would be irrelevant...in the end you are just selecting a single person uniformly at random so this would be the same as the first version. – lulu Jun 27 '23 at 11:17
  • @lulu yes. I, too, see that interpretation pointless. But assuming the natural interpretation, I don't know how should I arrive at book's given final answer. (The first "pointless" interpretation was raised up to explain other answers in this site) – Reza Hassani Jun 27 '23 at 13:02

1 Answers1

0

But I suppose after N people have been informed of the rumor, each one of them will tell a randomly chosen group of N people.

This is your mistaken assumption. Nowhere in the problem is it stated that every person in the group of $N$ goes on to tell their own group of $N$. If this were the case, the math would be far too complicated, and there would be no nice formula.

Here is description of the rumor-spreading process which leads to the answer of $(n)_{Nr}/((n)_N)^r$.

The first person selects a group of $N$ at random from the other $N$ people, and tells them all the rumor.

This group of $N$ people randomly selects one of themselves to be a leader.

Repeat this process $r-1$ additional times, with the selected leader being the person to tell the rumor to $N$ randomly selected other people.

To be fair, none of these details are specified, or obviously implied, by the way the problem is written.

Mike Earnest
  • 75,930