# Probability on spreading of rumors

A little help here. Exercise 21, Ch. 2 from Feller's book reads

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).

I already did a) and b) for the first description of the problem and a) for the case when the rumor is spreading through a gathering of $N$ people, however, my solution for b) in this second case is not correct.

I reasoned in the following way: In a first instance, $n$ people to receive the rumor, however, it's needed to spread such rumor through a group of $N$ people, therefore, there are $\displaystyle n \choose N$ ways to choose those gatherings. Once one of these people is chosen, he/she can choose from another gathering of $N$ people, taking care of not choosing someone who already know the rumor, which is, there are $\displaystyle n-1 \choose N$, and so on, until we reach the $r$ step in this process. Therefore, the probability I get is:

$$\frac{\displaystyle {n \choose N} {n-1 \choose N} {n-2 \choose N} ... {n-r+1 \choose N}}{\displaystyle {n \choose N}^{r}}$$

According to the book, the solution must be $\displaystyle \frac{(n)_{Nr}}{(n_{N})^{r}}$ (which is not equivalent to the first expression).

I will appreciate any help.

-
I think your error is in how you're decreasing. Note that you N people are told the rumor, so that means your total pool decreases from n to n-N and at each step you would decrease by n-iN. – JSchlather Dec 2 '10 at 2:51
Is the original person fixed, or do we take into account the (n+1) ways of picking this person? – user3180 Dec 2 '10 at 3:40
@Liberalkid: I hadn't understood the problem in such a way. Using your suggestion, I reach an expression similar to the correct answer, however, it's not correct. Maybe I'm counting something wrong, so I will keep trying. – Robert Smith Dec 2 '10 at 3:46
@user3971: Since the problem states that the rumor must not reach a person who already knows the rumor, the original person shouldn't be taken into account. – Robert Smith Dec 2 '10 at 4:07
@Liberalkid: Since you and Yuval were very helpful, I'd be happy to upvote your comment if you add it as an answer. – Robert Smith Dec 2 '10 at 5:47

Liberalkid is right. Using his suggestion, you get $$\frac{\binom{n}{N}\binom{n-N}{N}\cdots\binom{n-(r-1)N}{N}}{\binom{n}{N}^r} = \frac{n_N (n-N)_N \cdots (n-(r-1)N)_N}{(n_N)^r} = \frac{n_{Nr}}{(n_N)^r}.$$ In the first step you cancel $N!$ from each side $r$ times.
Right. I was cancelling terms too early, so I missed the opportunity to express it in terms of $n_{N}$. Thank you very much. By the way, why is the problem removing the gatherings from the available people each time? It doesn't seem very adequate in a real situation. – Robert Smith Dec 2 '10 at 5:43
On the contrary. Suppose you're collecting cards and you get $N$ out of $n$ cards each time. How long can you go without getting the same card twice? – Yuval Filmus Dec 2 '10 at 5:56
Oh, I just realized what was my misunderstanding. I read something like "Do the same problem when at each step the rumor is told to one person of a gathering of N randomly chosen people" instead of "... by one person to a gathering...". I thought that in the real case of having a population of $n$ people, they could choose one person from $N$ friends to spread the rumor. Then I was thinking that some of them could share friends. Next time I will read the problem 2 times. – Robert Smith Dec 2 '10 at 7:22