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).

  • 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$ – Peter Heinig Oct 7 '17 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$ – Peter Heinig Oct 7 '17 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$ – François G. Dorais Oct 7 '17 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$ – Peter Heinig Oct 8 '17 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$ – James Martin Oct 8 '17 at 9:39

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.

| cite | improve this answer | |
  • 1
    $\begingroup$ I don't understand this. The formula in display is much too small when, say, $p=1/2n$. $\endgroup$ – Ori Gurel-Gurevich Oct 8 '17 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$ – François G. Dorais Oct 8 '17 at 10:27
  • 1
    $\begingroup$ I've asked the implicit question in the last paragraph here: mathoverflow.net/q/282996 $\endgroup$ – François G. Dorais Oct 8 '17 at 16:20

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.)

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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