# Markov chain probability in a complete graph

I'm having a hard time understanding the following. Assuming we have a complete graph with $n$ vertices, where initially, one of those has an information. At this point, all we care about is that in each time $t$ a node that has the information chooses randomly one of it's neighboors and sends it the info, only if the receiver does not have it. We don't care how the sending is done. Let $x_t$ be a random variable representing the number of nodes that have the info at the time $t$. It is indicated that $x_t$ can be modeled by a homogeneous increasing Markov chain. So, if at $t$, if $k$ vertices have he info, then the probability of another vertex receiving the information (using population protocols), that is, to have $k+1$ vertices know it is $\frac{2k(n-k)}{n(n-1)}$. Can someone explain why this stands?

The link to the paper I got this from is this: https://drive.google.com/open?id=0B0RiUAwpE4vnTlFqWmRHdlRYSFp4aDlYcWE5dWxUdWg2ZDA4 and the transition graph of the chain is shown in Figure 2.

• I read this info at a paper named "Randomized broadcasting in wireless mobile sensor networks" by Abdallah, Kacem, Mosbah and Zemmari. The thing is, at the start of the algorithm, one node knows the information, and then it chooses one of its neighbours and sends it the information and so on. So, if x_t is the random variable representing the number of nodes knowing the info at the time t, then, the paper suggests that x_t can be modelled by a homogenous increasing Markov chain, with the probability I described above. – mandra Mar 12 '17 at 10:47
• OK. Please edit the question to incorporate all of this information in the question. Comments can disappear at any time, and we want questions to be self-contained, so people don't have to read the comments to understand what you are asking. Also, if you can provide a freely available link to a PDF of the paper, that might be helpful to some folks. – D.W. Mar 12 '17 at 14:54

The probability that you state is the probability that a random edge of the complete graph connects one of the $k$ nodes to one of the other $n-k$ nodes. This means that in your process, a random edge is chosen, and if exactly one vertex already knows the information, then the other vertex is made aware of it. Information spreads exactly when the chosen edge is of this form, which in your case happens with the probability you mention.

• Hey, thanks for replying. The graph is complete so every node connects to all the others. What I cannot understand is how this probability is formed :/ – mandra Mar 12 '17 at 15:08
• I'm afraid you'll have to work out the calculation yourself. It's not too difficult. – Yuval Filmus Mar 12 '17 at 15:12
• From what I've done so far, I understand that the $2/n(n-1)$ part of the formula is the probability of choosing one of the edges of the graph. But for the other part, I seem to be confused. Can you at least give me a lead? – mandra Mar 12 '17 at 15:15
• I gave you a lead in my answer. I suggest spending a few hours on this. – Yuval Filmus Mar 12 '17 at 15:21

So after putting a lot of thought into this and with the help of the previous comment, I managed to figure it out like this:

First of all, the graph has $\frac{n(n-1)}{2}$ edges, so the probability of a node knowning the info choosing one edge is $p=\frac{2}{n(n-1)}$. Now, we have $k$ such nodes so p is multiplied by $k$ and $n-k$ edges connecting that node to the remaining $n-k$ nodes who don't have the info and thus the probability is also multiplied by $n-k$, which gives the result.

Please correct me if I'm wrong

• Exactly. Each edge is equally likely to be chosen, and there are $k(n-k)$ "good" edges out of $n(n-1)/2$ edges in total. – David Richerby Mar 12 '17 at 21:42