ELE 600: Probability and Stochastic Processes 1. (25 points) In a room with n +1

Question

ELE 600: Probability and Stochastic Processes 1. (25 points) 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 recipient of the rumor is randomly chosen out of the n other people in the room. (a) Find the probability that in r tellings of the rumor, it has not come back (b) Find the probability that after the rumor has been told r times it has not (c) Find the probability that the rumor reaches the originator of the rumor (d) Find the expected number of steps for the rumor to reach the originator. to the originator of the rumor. reached any one person twice. in exactly r steps. 2. (25 points) Suppose we are given a random variable X, whose probability density function

Explanation / Answer

(a)

There are n+1 people, so another person can tell the rumour to remaining (n-1) persons.

In the first telling, the originator told the rumour randomly to any of n people with probaililty 1.

In the 2nd telling, another person will tell the rumour to remaining (n-1) person (excluding the originator and himself) out of n persons with probability (n-1) / n

Similarly, in rth telling, another person will tell the rumour to remaining (n-1) person (excluding the originator and himself) out of n persons with probability (n-1) / n

So, the probability that in r tellings, it has not come back to originator is

1 * [(n-1) / n] * [(n-1) / n] * ... (r-1) times

= [(n-1) / n]r-1

(b)

In the first telling, the originator told the rumour randomly to any of n people with probaililty 1.

In the 2nd telling, another person will tell the rumour to remaining (n-1) person (excluding the originator and himself) out of n persons with probability (n-1) / n

In the 3rd telling, another person will tell the rumour to remaining (n-2) person (excluding the originator and 2 more persons) out of n persons with probability (n-2) / n

Similarly, in rth telling, another person will tell the rumour to remaining (n-1) person (excluding the originator) out of n persons with probability (n- r + 1) / n

So, the probability that in r tellings, it has not come back to any person twice is

1 * [(n-1) / n] * [(n-2) / n] * ... [(n-r+1) / n]

= [(n-1)(n-2) ....(n-r+1) / nr-1]

(c)

In the first telling, the originator told the rumour randomly to any of n people with probaililty 1.

In the 2nd telling, another person will tell the rumour to remaining (n-1) person (excluding the originator and himself) out of n persons with probability (n-1) / n

Similarly, in (r-1)th telling, another person will tell the rumour to remaining (n-1) person (excluding the originator and himself) out of n persons with probability (n-1) / n

But, in rth telling, another person will tell the rumour to the originator out of n persons with probability 1 / n

So, the probability that in r tellings, it will come back to originator in the rth step is

1 * [(n-1) / n] * [(n-1) / n] * ... (r-2) times * [1/n]

= [(n-1)r-2 / nr-1]

(d)

If we exclude the first telling, the remaining tellings is a case of geometric experiment where the probability of success (rumor to reach originator) is (1/n) and the experiment is conducted for (r-1) trials till the rumour reaches the originator.

Mean of Geom(p) distribution is 1/p.

So, expected number of steps (exculding 1st telling) to reach the originator is 1/(1/n) = n.

Therefore, expected number of steps for rumour to reach the originator = n +1 steps

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.