Probability for 2 vertices to lie in the same component of a random graph

Question

Consider $G(4,p)$ - the random graph on 4 vertices. What is the probability that vertex 1 and 2 lie in the same connected component?

So far, I have considered the event where 1 and 2 do not lie in the same component. Then vertex 1 must lie in a component of order 1, 2 or 3 that doesn't contain vertex 2. However, I am unsure about how to compute these probabilities. For 1 to be in a component if order 1, I think this has probability $(1-p)^3$.

Answer 1

For $p=1/2$, since there are a total of six edges in $K_4$, that means there are only $2^6=64$ possible labeled graphs, each of which is equally likely. You could write out the sample space and count.

When $p\ne 1/2$, you could determine a binomial probability for each possible graph and sum the probabilities of each of the graphs that satisfy your condition (as opposed to straight up counting them in the previous paragraph).

Admittedly, this is a naive approach, but it might give some insight on the general process.

Answer 2

Hint:

Let $X$ denote the number of edges that will be included.

Let $E$ be the event that vertex $1$ and $2$ lie in the same connected component.

Then $P\left(E\right)=\sum_{k=0}^{6}P\left(E\mid X=k\right)P\left(X=k\right)$

Here $X$ is binomially distributed with parameters $n=6$ and $p$ and it remains to find the conditional probabilities $P(E\mid X=k)$.

If $k\geq4$ then the graph is connected and if $k=0$ then the graph is totally disconnected so you can start with observing that $P(E\mid X=4)=P(E\mid X=5)=P(E\mid X=6)=1$ and $P(E\mid X=0)=0$. It remains to find $P(E\mid X=k)$ for $k=1,2,3$.

Answer 3

Let $E_{ij} = E_{ji}$ denote the event that the edge $\{i,j\}$ is added in the graph. The event "1 is connected to 2" is the disjoint union of the five following events:

• $E_{12}$, with probability $p$
• $\overline{E_{12}} \wedge E_{13} \wedge E_{32}$, with probability $ p^2(1-p)$
• $\overline{E_{12}} \wedge E_{13} \wedge \overline{E_{32}} \wedge E_{34} \wedge E_{42}$, with probability $p^3(1-p)^2$
• $\overline{E_{12}} \wedge \overline{E_{13}} \wedge E_{14} \wedge E_{42}$, with probability $p^2(1-p)^2$
• $\overline{E_{12}} \wedge \overline{E_{13}} \wedge E_{14} \wedge \overline{E_{42}} \wedge E_{43} \wedge E_{32}$, with probability $p^3(1-p)^3$

Therefore, the probability that vertex 1 and 2 lie in the same connected component is simply $$ p + p^2(1-p) + p^3(1-p)^2 + p^2(1-p)^2 + p^3(1-p)^3 $$