0
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Do you want exactly one neighbor to be red or just at least one neighbor? $\endgroup$ Jan 10, 2018 at 10:44
  • $\begingroup$ 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. $\endgroup$
    – drhab
    Jan 10, 2018 at 10:44
  • $\begingroup$ @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. $\endgroup$
    – Skillzore
    Jan 10, 2018 at 10:49
  • $\begingroup$ @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. $\endgroup$
    – Skillzore
    Jan 10, 2018 at 10:50
  • $\begingroup$ 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". $\endgroup$
    – drhab
    Jan 10, 2018 at 11:00

1 Answer 1

0
$\begingroup$

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".

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .