What is the probability of a chain of a given length in a random graph?

Question

Let $G$ be an undirected graph with $n$ nodes. An edge is randomly and independently drawn from each node to any of the other nodes. If some arbitrary node $a$ is chosen, what is the probability that it will be connected (in the sense that, if the edges $(A,B),(B,C)$ exist, $A$ is connected to $C$) to $k$ other nodes?

For example, in the case where $n = 3$, the probability that $a$ will be connected to $1$ or $2$ nodes is $0$, and the probability that $a$ will be connected to $3$ nodes is $1$. This is easily shown by enumerating the possible graphs:

$(A,B),(B,C),(C,A)$
$(A,B),(B,C),(C,B)$
$(A,B),(B,A),(C,B)$
$(A,B),(B,A),(C,B)$
$(A,C),(B,C),(C,A)$
$(A,C),(B,C),(C,B)$
$(A,C),(B,A),(C,B)$
$(A,C),(B,A),(C,A)$

Obviously, for $n$ of any real size, naive enumeration isn't a feasible approach. Is there a method of calculating the probability for larger $n$?

Answer 1

For our vertex $a$ to be connected to exactly $k$ other nodes, the following must happen: there is a subset of vertices, $V,$ where $|V|=k$, the induced subgraph on $V$ is connected, and there are no edges from $V':=V\cup\{a\}$ to $(V')^c$. For different sets $V$, these events are disjoint! Using this fact and symmetry, \begin{align*} P(a& \text{ is connected to }k\text{ other vertices}) \\&= \sum_{V: |V|=k} P(a \text{ is connected to }V, \text{no edges from }V'\text{ to }(V')^c) \\& = {n-1 \choose k} P(a \text{ is connected to }V_0, \text{no edges from }V_0'\text{ to }(V_0')^c), \end{align*} where $V_0$ is some fixed set of $k$ vertices.

There are multiple ways to bound this latter probability. For example, a necessary condition for this latter probability is that each vertex of $V_0'$ picks a vertex of $V_0'$ while every vertex of $(V_0')^c$ chooses a vertex of $(V_0')^c$. The probability of this event is $\frac{ k^{k+1} (n-k-2)^{n-k-1}}{(n-1)^n}$, because there are $k+1$ vertices in $V_0'$ which choose one of the other $k$ vertices of $V_0'$. Therefore, we have that $$ P(a \text{ is connected to }k\text{ other vertices}) \leq {n-1 \choose k}\frac{k^{k+1} (n-k-2)^{n-k-1}}{(n-1)^n}. $$ This is a relatively dirty bound because we do not take into the account the condition that the induced graph on $V_0'$ should be connected.

Answer 2

You didn't precise your probability space - I assume that for any two vertices x,y you have $P(xy \in E) = p$ and for different pairs the events are independent. Then the probability that the vertex has degree $k$ with $0 \le k \le n-1$ is the probability that a set of $k$ edges is in the graph and $n-1-k$ are not, so it's: $$ \binom{n-1}{k} p^k (1-p)^{n-1-k} $$