In a town of $n$ inhabitants, a person tells a rumor to a second person, who in turn repeats it to a third person and so on. At each step the recipient of the rumor is chosen at random from the $n-1$ people available.

Find the probability that rumor will be told $n$ times without Returning to originator .

Note: I have posted this as i could not understand the solution given in other thread of same problem.

My Try:

Let the persons be $P_1$, $P_2$, $P_3$, $\cdots$$P_n$

Given that $P_1$ is the originator and he spreads Rumor to $P_2$.

$P_2$ spreads to $P_3$ and so on till $P_{n-1}$ spreads to $P_n$

Till now Rumor has been spread $n-1$ times.Now we require what is the probability that $n$th time Rumor will be spread so that $P_1$ wont hear the Rumor again.

Now total ways to spread the rumor $n$th time is:

$P_2$ can spread it in $n-3$ ways since he can spread to $P_4$, $P_5$...$P_n$.

$P_3$ can spread in $n-3$ ways since he can pass it to $P_1$, $P_5$, $P_6$...$P_n$

Like wise $P_4$ can spread in $n-3$ ways and so on

$P_n$ can spread in $n-2$ ways.

So denominator is $(n-3)(n-3)(n-3)\cdots (n-2)$

Now number of favorable cases is:

$P_2$ can spread it in $n-3$ ways.

$P_3$ can spread in $n-4$ ways

$P_4$ can spread in $n-4$ ways and so on

$P_n$ can spread in $n-3$ ways

hence Probability is

$$P(A)=\frac{(n-4)^{n-3}\times (n-3)^2}{(n-3)^{n-2} \times (n-2)}$$

Is my analysis wrong? please correct it if so ?

  • $\begingroup$ Where do you get that it can spread in $n-4$ or $n-3$ ways? As the problem is written, each person has $n-1$ people they can tell. One of these is the originator unless the teller is the originator. $\endgroup$ – Ross Millikan Nov 9 '17 at 17:07
  • $\begingroup$ Do you mean $P_1$ is not originator? $\endgroup$ – Umesh shankar Nov 9 '17 at 17:11
  • $\begingroup$ No, but when $P_2$ tells the rumor, there are $n-1$ people he can tell. One of them is $P_1$. The other $n-2$ are somebody else. When somebody else tells the rumor it is the same. They could tell $P_2$ again. $\endgroup$ – Ross Millikan Nov 9 '17 at 17:16

After the first step the chance the originator is told is $\frac 1{n-1}$. At the first step the originator cannot be told, so the chance the originator has not been told after $n$ steps is $\left(1-\frac 1{n-1}\right)^{n-1}$

  • $\begingroup$ After the first step the chance of Originator being told is $\frac{1}{n-1}$. I could not get it, Do you mean the probability that originator spreading the rumor is $\frac{1}{n-1}$ when he wishes to share the rumor first time $\endgroup$ – Umesh shankar Nov 9 '17 at 17:25
  • $\begingroup$ My doubt is if say $P_2$ told rumor to $P_3$, Then according to your answer $P_3$ is again telling Rumor to $P_2$. But practically its not correct right? I request you to please clarify on this $\endgroup$ – Umesh shankar Nov 10 '17 at 2:56
  • $\begingroup$ I don't require that $P_3$ tell $P_2$ but I permit it. We are told that each teller selects the recipient at random from all the other people. That includes the person who told him. It is the same for the first comment. At each step the recipient is chosen at random and the originator is one of $n-1$ people that you choose from. $\endgroup$ – Ross Millikan Nov 10 '17 at 3:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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