Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 4 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.