7
$\begingroup$

Consider the Erdős–Rényi model $G_{n,p}$ with corresponding probability measure $\mathbb{P}_{n,p}$. For any two vertices $x,y$, $\mathbb{P}_{n,p}[E_{x,y}]=p$, where $E_{x,y}$ is the event that there exists an edge between $x$ and $y$.

I need to estimate (especially bound from above) the following probability for two fixed vertices $x,y$ and $G \in G_{n,p}$:

$\begin{equation} \mathbb{P}_{n,p}[E_{x,y}|G \text{ is connected}] \end{equation}$

Supplement: $p=\frac{c}{n}$ for some constant $c >1$ (I forgot this in my first version).

$\endgroup$
7
  • 1
    $\begingroup$ Do you need a complete description for any given function $p\colon \omega\to(0,1)$ ? If $p$ is any function $p\colon \omega\to(0,1)$ such that $p\gg\frac{\log n}{n}$, then $\lim_{n\to\infty}\frac{\mathbb{P}_{n,p(n)}[E_{x,y}\mid\text{$G$ is connected}]}{p(n)} = 1$. If, however, you 'are' 'inside' 'the' 'phase-transition' for the connectedness, then giving a thorough answer would require a bit of work, I think. $\endgroup$ Oct 7, 2017 at 15:10
  • 1
    $\begingroup$ Without meaning to prescribe you anything, for known reasons the question would be most interesting if you stipulated that $p(n) = n^{-1} + n^{-\frac43}$. You probably shouldn't do this for the sake of asking a harder question; it might be that in your work you only need a 'regime' of functions $p\colon\omega\to(0,1)$ for which the question is trivial, by superficial calculations. My point is mainly that you should make you question more precise, by specifying which functions $p\colon \omega\to(0,1)$ you need; the effects of that range from 'trivial' to 'difficult' (I think). $\endgroup$ Oct 7, 2017 at 15:37
  • $\begingroup$ @PeterHeinig: The question is about any fixed $n$ and $p$. The OP doesn't seem to be (immediately) interested in limiting probabilities or asymptotic estimates. It seems to me that you are making the question much more difficult than it is. $\endgroup$ Oct 7, 2017 at 20:59
  • $\begingroup$ 'François G. Dorais' is right in saying that if one interprets this OP strictly logically, then it is asking about the stated probability with '$n$' and '$p$' being constants (in the model-theoretic sense of 'constant'). My comments are imputing intentions to the opening poster, but I thought I had made it abundantly clear that I was imputing intentions, and that I was pointing out to the opening poster that they should not adopt my suggested additional hypotheses merely for the sake of making it a hard question, rather should make the clarifications fit whatever actual intents they have. $\endgroup$ Oct 8, 2017 at 6:02
  • $\begingroup$ @FrançoisG.Dorais: I think you have it the wrong way around. Giving a useful answer to such a question "for any fixed $n$ and $p$" can typically be very hard. On the other hand, there are "regimes" of $n$ and $p$ (i.e. ways in which $p$ behaves as a function of $n$, as $n$ grows), where the answer can be more straightforward. It would certainly be useful if the OP could clarify whether they are interested in a particular regime. $\endgroup$ Oct 8, 2017 at 9:39

2 Answers 2

3
$\begingroup$

Let $E_{xy}$ be the event that $xy$ is an edge of $G$ and let $C$ be the event that $G$ is connected. By Bayes' Theorem, $$P(E_{xy} \mid C) = \frac{P(C \mid E_{xy})P(E_{xy})}{P(C)} = p\frac{P(C \mid E_{xy})}{P(C)}.$$ So the question amounts to estimating how much knowing that $G$ has an edge improves the probability of $G$ being connected.

The graph $G$ is connected precisely if it contains a spanning tree $T$. Furthermore, knowing that $xy$ is an edge of $G$, we may further require that $T$ contains the edge $xy$. So we have a crude upper bound $$P(C \mid E_{xy}) \leq \sum_{xy \in T} P(T \subseteq G \mid E_{xy}),$$ where $T$ ranges over all trees on the labeled vertex set $\{1,\ldots,n\}$. By Cayley's Formula, there are $n^{n-2}$ such $T$ and, since each such $T$ has exactly $n-1$ edges, there are $2n^{n-3}$ such trees that contain the edge $xy$. For each $T$ containing $xy$, $P(T \subseteq G \mid E_{xy}) = p^{n-2}$, so $$P(C \mid E_{xy}) \leq 2n^{n-3}p^{n-2},$$ or equivalently $$P(E_{xy} \mid C) \leq \frac{2n^{n-3}p^{n-1}}{P(C)}.$$ Clearly, this bound is only useful for small $p$. When $p$ is large, the trivial bound $$P(E_{xy} \mid C) \leq \frac{p}{P(C)}$$ is of greater use.

The classic paper Gilbert, E.N., Random graphs, Ann. Math. Stat. 30, 1141-1144 (1959). ZBL0168.40801, contains exact formulas for $P(C)$. Gilbert's method can also be used to compute $Q_n = P(C \mid E_{xy})$ using the recurrence $$1-Q_n = \sum_{k=2}^{n-1} \binom{n-2}{k-2}Q_k(1-p)^{k(n-k)}.$$ (The $k$th term is the conditional probability that the connected component containing $x,y$ has exactly $k$ elements.) Thus

$Q_{2} = 1$

$Q_{3} = -p^2 + 2 p$

$Q_{4} = -2 p^5 + 9 p^4 - 14 p^3 + 8 p^2$

$Q_{5} = 6 p^9 - 48 p^8 + 162 p^7 - 298 p^6 + 318 p^5 - 189 p^4 + 50 p^3$

I haven't tried to prove it but it seems that the bound $2n^{n-3}p^{n-2}$ from above is exactly the leading term of $Q_n$. At least this is the case for $n \leq 60$ by direct calculation.

$\endgroup$
3
  • 1
    $\begingroup$ I don't understand this. The formula in display is much too small when, say, $p=1/2n$. $\endgroup$ Oct 8, 2017 at 7:47
  • $\begingroup$ @OriGurel-Gurevich: Yes, I forgot to condition on connectedness. Thanks! I fixed it, but then I found a slightly better bound which is hopefully clearer. $\endgroup$ Oct 8, 2017 at 10:27
  • 1
    $\begingroup$ I've asked the implicit question in the last paragraph here: mathoverflow.net/q/282996 $\endgroup$ Oct 8, 2017 at 16:20
2
$\begingroup$

I agree strongly with Peter in the comments: if you're interested in $p \gg \frac{\log n}{n}$, then don't do any hard work, just show the answer is essentially $p$ since the graph is essentially always connected.

In particular, let $E$ be the event that the edge exists and $C$ the event that the graph is connected. By the law of total probability, \begin{align*} P(E|C)P(C) + P(E,\lnot C) &= p \end{align*} so \begin{align*} P(E|C) &= \frac{p - P(E,\lnot C)}{P(C)} \\ &\leq \frac{p}{1-o(1)} \end{align*} where a lot is known about bounds on the $o(1)$ (the probability the graph is disconnected).

(By the way, naturally, we immediately have $P(E|C) \geq p$. To prove it, $P(E|C) = p P(C|E)/P(C)$, and $P(C|E) \geq P(C)$ as guaranteed existence of $(x,y)$ can only raise the chance of connectedness.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.