# Probability that the distance from some source vertex to any other vertex is at most exactly $l$ in a random graph?

Given a random (undirected and unweighted) graph $G$ on $n$ vertices where each of the edges has equal and independent probability $p$ of existing (see Erdős–Rényi model). Fix some vertex $u\in G$ and call it the source. I am interested in the probability that our random graph has the following property: we can start at the source and go to any other vertex in the graph in at most exactly $l$ edges, i.e., there is at least some vertex $v\in G$ such that the shortest distance between $u$ and $v$ is $l$ and there is no vertex $v'\in G$ such that the shortest distnace between $u$ and $v'$ is more than $l$.

Distance $d$ between $u\in G$ and $v\in G$ is measured by the number of edges between $u$ and $v$ along a shortest path.

• Is there a particular range of $p$ and $\ell$ that you are interested in? Also, do you care mostly about "w.h.p." results or do you care about $p$ and $\ell$ so that this probability tends to zero and you want to find out exactly how quickly? – D Poole Aug 11 '14 at 21:39
• The answer to this question might give me an insight into a proof that I'm working on. The range of $p$ that I would like to test is up to 1024, so I would like for the answer to give at least approximately good results in that range, i.e., something that only works at $\infty$ would be useless to me. The range of $l$ should be from 1 to $p-1$, i.e., all possible $l$ values. I do not care for how quickly the probability tends to 0 with changing $p$ and $l$. – nick.bourbaki Aug 11 '14 at 22:06

It seems to me that you want an exact expression for this probability. Here is one such formula albeit it does not have a nice closed form. Fix some vertex $u$ in $G(n,p)$. Let's define $d(u) = \max_v d(u,v)$, where $d(u,v)$ is the distance between $u$ and $v$. So you are interested in $P(d(u) \leq \ell)$ for any $\ell \in [1,n-1]$.

Let $$A_\ell:=\{(k_1, ..., k_\ell): k_i \geq 0, k_1+...+k_\ell = n-1, \text{ if }k_i=0, \text{ then } k_{i+1}=...=k_{\ell}=0\},$$ and $k_0:=1$.

Then $$P(d(u) \leq \ell) = \sum_{(k_1,...k_\ell)\in A_{\ell}} {n-1 \choose k_1, k_2, ..., k_\ell} \prod_{i=1}^{\ell} \left( 1 - \left( 1- p\right)^{k_{i-1}}\right)^{k_i} (1-p)^{(1+k_1+...+k_{i-2})k_i},$$ with the understanding that the last factor is defined to be 1 for $i=1$.

Why? Run a breadth-first search starting from $u$. Let $\mathcal{L}_1, ..., \mathcal{L}_{n-1}$ be the (random) set of vertices found at each level; formally $\mathcal{L}_i:=\{v \in G(n,p): d(u,v)=i\}$. Suppose that $L_1,...,L_{n-1}$ is a partition of $[n]\setminus \{u\}$ so that if $|L_j|=0,$ then $|L_{j+1}|=...=|L_{n-1}|=0$. So $$P((\mathcal{L}_1,...,\mathcal{L}_{n-1})=(L_1,...,L_{n-1}))= \prod_{i=1}^{n-1} \left( 1 - \left(1-p\right)^{|L_{i-1}|}\right)^{|L_i|}(1-p)^{(1+k_1+...+k_{i-2})k_i}.$$ This is because we need every vertex of $L_{i}$ to be adjacent to at least one vertex of $L_{i-1}$ and NOT adjacent to any vertex of $L_0, ..., L_{i-2}$. To finish off the proof, the events $\vec{\mathcal{L}} = \vec{L}$ and $\vec{\mathcal{L}}=\vec{L}'$ are disjoint if $\vec{L} \neq \vec{L}'$. Adding over all possible such sequences yields the formula above.

EDIT: I forgot the $(1-p)^{(1+...+k_{i-2})k_i}$ term in the original post.

• While it will take me a little bit of time to traverse and really understand your answer, I wanted to say that I appreciate you writing it out! I just realized that I said something a little bit wrong in my question and actually meant that I was interested in $P(d(u) = l))$. Nevertheless, I think I should be able to arrive at that answer by understanding your answer. – nick.bourbaki Aug 13 '14 at 20:20
• To get $P(d(u)=\ell)$, instead of summing over $A_\ell$, sum over $(k_1, ..., k_\ell)$ with $k_i >0$ and $k_1+...+k_\ell=n-1$. This forces there to be vertices at distance $\ell$ from $u$. – D Poole Aug 14 '14 at 13:41
• In both cases, I think the condition should be $k_1 + \ldots + k_l \leq n - 1$ because if it's "$=$", then you're assuming that the graph is connected. Do you agree? – nick.bourbaki Aug 14 '14 at 16:10
• If the graph is not connected, then all other vertices can not be reached within $\ell$ edges. You need the graph to be connected for how the problem is worded. – D Poole Aug 15 '14 at 4:40
• I agree. Okay, so I understand your answer fully, but the numbers don't seem to add up correctly when I try $n=4, p=0.5$. I expect $P(d(u)=1)+P(d(u)=2)+P(d(u)=3) = 1$, but I get $2/16, 15/16,$ and $2/16$, respectfully... – nick.bourbaki Aug 15 '14 at 18:08