One way of spreadingi nformation on a network uses a rumorsp

One way of spreadingi nformation on a network uses a rumor-spreading paradigm. Suppose that there are n hosts currently on the network. Initially, one host begins with a message. Each round, every host that has the message contacts another host chosen independently and uniformly at random from the other n - 1 hosts, and sends that host the message. We would like to know how many rounds are necessary before all hosts have received the message.  Explain how this problem can be viewed in terms of Markov chains?

Solution

It is always n-1 rounds

because initially 1 host will know and he will give message to second host by contacting him.so 2 hosts in one round or first round.next round second transmits a message to third and this goes on in successive rounds.

ex:

If 6 hosts are there,then 5 rounds are required.

markov chain is a  stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event.

veiwing in terms of markov chain

here the listening host will get a message only when the sending host sends a message which is a previous event.The same happens for each and every hosts in the network.