2

In a room with $n+1$ people, a person tells a rumor to another person, who in turn repeats it to a third person, and the process continues. at each step the receipt of the rumor is randomly chosen out of the n other people in the room.

a). Find the probability that the rumor reaches the originator of the rumor in exactly $r$ steps.

b). Find the expected number of steps for the rumor to reach the originator.

I answered the part a as following: $p(\text{the originator})= (n-1/n)^{r-1}$.

I have no idea about the part b. Can anyone help me out about the solutions and explain the concept?

What kind of materials that I need to study with because my professor never covers these materials in the class. Thank you very much.

Deepsea234
  • 57
  • I think this problem is more like passing a gift (throwing a frisby). If you know how to do part $a$, then part $b$ is just averaging over all possibilities of $r$. – Zhuoran He Nov 02 '17 at 20:27
  • It looks like a Markov Chain, to me. So, calculate the probability that we return to the original state in $r$ steps and the expected number of steps to return to the original state. – learning Nov 02 '17 at 20:29
  • 2
    Simpler than that. It's a geometric distribution. No matter whose hand the gift is in, so long as it's not in the originator's hand, we call him "someone else". – Zhuoran He Nov 02 '17 at 20:31
  • Ah OK, that makes sense. It does look like it can be solved correctly using Markov Chains, too. – learning Nov 02 '17 at 20:31
  • Your answer to $a$ is not correct. There is a typo that the first $n$ should be $1$, but also the rumor cannot reach the originator in one step. Do you require that the $r^{th}$ step be the first time the originator is told the rumor or just the originator is told on step $r$? That will change the answer. – Ross Millikan Nov 02 '17 at 20:32

2 Answers2

2

For each step, the probability to pass the rumor to the originator is $1/n$ while the probability to pass the rumor to someone else is $(n-1)/n$. Assuming $r=2$ corresponds to the case that the first person repeats it to the originator, then for there to be r steps, simply multiply the corresponding probabilities, $$P(r)=\left({n-1\over n}\right)^{r-2}{1\over n}$$ With this you can calculate $E[R] =n+1$. You may have a different definition for $r$.

Dean
  • 1,370
  • Thank you very much for your help. Would you explain how you got E(r) =n+1. When I applied the formula sum of r*p(r), I can not simplify it at all. Thanks again. – Deepsea234 Nov 03 '17 at 00:20
  • I think there are n+1 people in the room, the base case is the originator, then there are n people left. Assuming r=4, P(base case)=1, P(rumor goes back to the originator)=1/n, for the other three steps, the probability is (n-1)/n. Therefore, P(r)=(n-1/n)^(r-1)*(1/n). How did you get power of r-2? Thanks – Deepsea234 Nov 03 '17 at 00:36
  • @Deepsea234 this probability comes from the fact that each person can talk to $n$ other people, of which $1$ is the originator. So the probability they miss the originator is $\frac{n-1}n$, and the probability they eventually tell the originator is $\frac1n$. The indices come from the fact that the originator speaks first, so tells someone else with probability $1$. Then they miss the originator $r-2$ times (so have spoken $r-1$ times in total), and then on the $r^{\text{th}}$ turn, they return to the originator. – John Doe Nov 03 '17 at 00:48
  • Rather than do the sum by hand, I asked "wolfram online" to calculate the sum of $r \cdot P(r)$ over all $r$ and it returned $n+1$. – Dean Nov 04 '17 at 01:25
1

HINT:

Let $X$ denote the random variable representing the number of steps it takes for the rumour to reach the originator.

$$\Bbb E[X]=\sum_{r=1}^\infty r\cdot\Bbb P(X=r)$$

EDIT: Requested by OP to expand on this

As stated in the other answer, $$P(X=r)=\left(\frac{n-1}n\right)^{r-2}\frac1n$$ for $r\ge2$. Thus $$\begin{align}E[X]&=\sum_{r=2}^\infty\frac1n\left(\frac{n-1}n\right)^{r-2}\cdot r\\ &=\frac1n\sum_{r=2}^\infty\left[\frac{d}{dx}\left(x^{r-1}\right)-x^{r-2}\right]\end{align}$$ where $x=\frac{n-1}n$. $$\begin{align}nE[X]&=\frac{d}{dx}\left[\sum_{r=1}^\infty x^{r}\right]-\sum_{r=0}^\infty x^r\\ &=\frac d{dx}\left(\frac{x}{1-x}\right)-\frac1{1-x}\\ &=\frac{1}{1-x}+\frac{x}{(1-x)^2}-\frac1{1-x}\\ &=\frac{\frac{n-1}n}{\left(\frac1n\right)^2}\\ &=n(n-1)\end{align}$$

Thus we conclude that $$\bbox[5px,border:2px solid red]{E[X]=n-1}$$

John Doe
  • 14,545
  • Thanks for the hint. I know the formula, but thought about it was not right because I can not simplify r*p(r). – Deepsea234 Nov 02 '17 at 23:56
  • @Deepsea234 I have edited my comment to include this calculation. It is quite common to try and express that kind of expression with a derivative, as shown. – John Doe Nov 03 '17 at 00:41
  • Thanks a lot. I applied the ideas that you explained to me for part a, but I still got different answer. I got P(r)=(n-1/n)^(r-1)*(1/n). Could you check it and explain it further? I greatly appreciate it. – Deepsea234 Nov 03 '17 at 01:01
  • @Deepsea234 Intuitively, $P(X=1)=0$, since the originator cannot whisper to themselves. Also, $P(X=2)=\frac1n$, since this is the probability of the person the originator has whispered to whispering back to the originator. Now substituting this into what you got, $r=2$ gives $$P(X=r)=\frac{n-1}n\frac1n\ne\frac1n$$ so your formula is not correct. if you change the power to $r-2$ rather than $r-1$, it fits the intuitive explanation much better. – John Doe Nov 03 '17 at 01:09
  • Thanks a lot for your explanation. – Deepsea234 Nov 03 '17 at 01:40