# The probability to paint a node red is $\frac{1}{k}$, what is the probability to paint the neighbor of a red node red?

We have a graph with maximal degree $k$ and we paint every node red with probability $\frac{1}{k}$ and green otherwise. This is done independently for every node. What is the probability that, after painting a node red, we also paint one of its neighbors red.

My approach was that, the degree of the current node is $m$ and we know that $m \le k$. Then the probability of painting a neighbor red, is the probability that we have $1$ success in $m$ independent experiments. Thus, the probability is: $${m \choose 1} \frac{1}{k} \left(1-\frac{1}{k}\right)^{m-1} = \frac{m}{k} \left(1-\frac{1}{k}\right)^{m-1}$$ However, I doubt that this is correct and I am in need of some help since I don't see any other approach.

• Do you want exactly one neighbor to be red or just at least one neighbor? Jan 10, 2018 at 10:44
• Your solution is the probability that exactly one of the $m$ neighbors is painted red. Aren't you looking for the probability that at least one of the $m$ neighbors is painted red? Further it is only a conditional probability. The condition is that the painted node has $m$ neighbors. Jan 10, 2018 at 10:44
• @drhab Yeah, I guess I would want at least one neighbor, since one or more would have the same effect. I don't know what "it is only a conditional probability" means. If you could make an answer with the at least one solution and explain the conditional part, that would be awesome. Jan 10, 2018 at 10:49
• @HenningMakholm Yeah, I am probably looking for the at least one option since one or more has the same effect. See my reply to drhab. Jan 10, 2018 at 10:50
• For a node that has $m$ neighbors the probability that at least one of its neighbors is painted red equals $1-(1-\frac1k)^m$. Here $(1-\frac1k)^m$ is the probability that none of them is painted red. "At least one" is the complementation of "none". Jan 10, 2018 at 11:00

For a node that has $m$ neighbors the probability that at least one of its neighbors is painted red equals: $$1-(1-\frac1k)^m$$
Here $(1-\frac1k)^m$ is the probability that none of them is painted red.