7

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.

r_31415
  • 2,934
  • 2
    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 02 '10 at 02:51
  • Is the original person fixed, or do we take into account the (n+1) ways of picking this person? – user3180 Dec 02 '10 at 03: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. – r_31415 Dec 02 '10 at 03: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. – r_31415 Dec 02 '10 at 04:07
  • @Liberalkid: Since you and Yuval were very helpful, I'd be happy to upvote your comment if you add it as an answer. – r_31415 Dec 02 '10 at 05:47

2 Answers2

4

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.

Yuval Filmus
  • 57,157
  • 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. – r_31415 Dec 02 '10 at 05: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 02 '10 at 05: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. – r_31415 Dec 02 '10 at 07:22
0

all

I think that the question Yuval is responding is that the probability the rumor is told at least r times and not exactly r times. When I read the question, I thought it was exactly r times. If this is the correct interpretation, we would have this probability as

$$\dfrac{(n)_N (n-N)_N \times \cdots \times (n - (r-2))_N \times (n_N - (n - (r-1)N)_N)}{[(n)_N]^r},$$

which is different from the answer given in Feller's book.

In my view, another problematic interpretation is that, at each step, one of the people aware of the rumor chooses at random N people to tell the rumor. But, what we are doing above is selecting N people from n to tell the rumor, which is not the same thing as everyone how knows the rumor tells N others the rumor. I have no idea how to solve the latter.

Luis Ernesto Bueno Salasar
  • 1