The expected number of paths with length $k$ in Erdős–Rényi random graph

expected valuegraph theoryprobabilityrandom-graphs

Consider the Erdős–Rényi random graph. Suppose the graph has $n$ vertices, and two vertices are connected with probability $\lambda/n$,independently. Denote such graph as $G(n, \lambda/n)$.

Let $N_k$ be the number of paths that is self-avoiding (i.e. each vertex in the path is unique) in $G(n, \lambda/n)$ with length $k$ and $v_1, v_2 \in V(G)$. Then,
$$\mathbb{E}[N_k] = \sum_{\vec{\pi} \in \mathcal{P}_k(v_1,v_2)}\mathbb{P}(\vec{\pi} \subseteq G(n, \lambda/n)),$$
where $\vec{\pi}$ denotes a path, and $\vec{\pi} \in \mathcal{P}_k(v_1,v_2)$ if and only if the path that connects $v_1$ and $v_2$ has length $k$. The event $\{\vec{\pi} \subseteq G(n, \lambda/n)\}$ is an indicator function
$$\mathbb{1}\{\vec{\pi} \subseteq G(n, \lambda/n)\} =
\begin{cases}
1, & \text{if} \ \vec{\pi} \subseteq G(n, \lambda/n)\\
0, & \text{otherwise}.
\end{cases}
$$

Let $\pi_0 = v_1, \pi_1, \dotsc, \pi_k = v_2 \in V(\vec{\pi})$. Then $\pi_0$ forms an edge with $\pi_1$ with probability $\lambda/n$. Given that $(\pi_0, \pi_1) \in \vec{\pi}$, the probability of $\pi_1$ connecting with $\pi_2$ is also $\lambda/n$ due to independence. This means that
$$\mathbb{P}(\vec{\pi} \subseteq G(n, \lambda/n)) = \frac{\lambda^k}{n^k}.$$
Now, I am stuck with
$$\mathbb{E}[N_k] = \sum_{\vec{\pi} \in \mathcal{P}_k(v_1,v_2)}\frac{\lambda^k}{n^k}.$$

Are my reasonings correct? How can I compute $\mathbb{E}[N_k]$?

Best Answer

Let $\cal{C}_{k+1}$ be defined

  • $\cal{C}_{k+1}$ $=$ $\{$ordered subsets of $V$ with $k+1$ vertices$\}$.

Then, for each graph $G$, the number of paths with $k$ edges, is precisely the number of $C_{k+1} \in \cal{C}_{k+1}$ such that, writing $C_{k+1}=(u_1,u_2,\ldots, u_{k+1})$ [keep in mind that $C_{k+1}$ is ordered], there is an edge between $u_i$ and $u_{i+1}$ for every $i=1,2,\ldots, k$. So now, let $G$ be a graph drawn according to $\cal{G}(n,\lambda/n)$. Then, for each $C_{k+1} \in \cal{C}_{k+1}$, let $A(C_{k+1})$ be the event

  • $A(C_{k+1}) =$ $\{$writing $C_{k+1}=(u_1,u_2,\ldots, u_{k+1})$, there is an edge in $G$ between $u_i$ and $u_{i+1}$ for every $i=1,2,\ldots, k\}$.

Then the number $N_k$ of paths with $k$ edges in $G$ satisfies $$N_k \ = \ \sum_{C_{k+1} \in \cal{C}_{k+1}} I_{A(C_{k+1})},$$ and so by linearity of expectation: $$\mathbb{E}[N_k] \ = \ \sum_{C_{k+1} \in \cal{C}_{k+1}} {\bf{P}}[A(C_{k+1})].$$

However, because $G$ was drawn according to $\cal{G}(n,\frac{\lambda}{n})$, the equation $${\bf{P}}[A(C_{k+1})] \ = \ \Big(\frac{\lambda}{n}\Big)^k$$ holds for each $C_{k+1} \in \cal{C}_{k+1}$. Furthermore, so does the equation $$|\cal{C}_{k+1}| = {n \choose {k+1}} \times (k+1)!$$ Putting these latter three equations together yields $$\mathbb{E}[N_k] \ = \ \Big(\frac{\lambda}{n}\Big)^k \times {n \choose {k+1}} \times (k+1)!$$ So the RHS of this is the expected number of paths with $k$ edges.