Erdős–Rényi $G(n,p)$ model, probability of given geodesic distance

Question

The $G(n,p)$ model describes a graph of $n$ nodes, where each pair of nodes are connected by an edge with an independent probability $p$.

Would like to confirm my solution to a couple of question:

1. If $p=\frac{1}{2}$, then show that as $n \rightarrow \infty$, the probability that nodes u and v, chosen uniformly at random, are at geodesic distance 2 tends to $\frac{1}{2}$.
2. If the mean degree $c>0$ is fixed so that $p(n)=\frac{c}{n-1}$, then show that for each $k \in \mathbb{N} $, that $Pr[d(u,v)=k] \rightarrow 0$ as $n \rightarrow \infty$. Where $d(u,v)$ denotes geodesic distance between $u,v$.

My attempt:

Given $u$ and $v$,

$Pr[d(u,v)=2] = Pr(\nexists \,a \,path\,of\,length\,1)\times Pr(\exists\,path\,of\,length\,2)$

$Pr(\nexists \,a \,path\,of\,length\,1) = \frac{1}{2}$

$Pr(\exists\,path\,of\,length\,2) = 1 - Pr(\nexists \,a \,path\,of\,length\,2)$

There are $n-2$ potential paths of length 2. Each doesn't exist with probability $1-(\frac{1}{2})^{2}=3/4$. So the probability that there are no paths of length 2 is $\frac{3}{4}^{n-2}$. So

$Pr(\exists\,path\,of\,length\,2) = 1-\frac{3}{4}^{n-2}$

And $Pr[d(u,v)=2] = \frac{1}{2}(1-\frac{3}{4}^{n-2}) \rightarrow 1/2 \, as \, n \rightarrow \infty$

Letting now $p=\frac{c}{n-1}$, the probability that $u,v$ have a path of length $k$ is

$p^{k}(n-2)\cdots(n-k) = \frac{c^{k}}{(n-1)^{k}}(n-2)\cdots(n-k) \rightarrow \frac{c^{k}}{n-1} \rightarrow 0$ as $n \rightarrow \infty$

Given that probability a path of length $k$ exists between $u,v$ tends to 0, the probability that $u,v$ are of distance $k$ also tends to 0.

Answer 1

Essentially correct, though there is a nitpick to be made.

For part 2, the expression $$p^k (n-2)(n-3) \dotsm (n-k)$$ does not represent the probability that there is a path from $u$ to $v$ of length $k$. Rather, it represents the expected number of such paths: there are $(n-2)(n-3)\dotsm (n-k)$ paths of length $k$ from $u$ to $v$ in the complete graph $K_n$, and each one is present in the graph $G(n,p)$ with probability $p^k$.

Now, the expected number of paths is always an upper bound on the probability that there's at least one path, by the simple inequality $$ \Pr[X\ge 1] = \sum_{i=1}^\infty \Pr[X=i] \le \sum_{i=1}^\infty i \cdot \Pr[X=i] = \mathbb E[X]. $$ So if you show that the expected number of paths goes to $0$ as $n \to \infty$, then the probability also approaches $0$ (by the squeeze theorem: the most useful theorem in the study of random graphs). So your approach is valid. But it's important to keep the distinction between probability and expectation straight in general.