Conditioning and Coupling G(n,p) With G(n,m)

Conditioning on the Number of Edges

The models $G(n,p)$ and $G(n,m)$ describe random graphs in different ways. In $G(n,p)$, each possible edge is selected independently, so the number of edges can vary. In $G(n,m)$, the number of edges is fixed and every graph with that many edges is equally likely. Conditioning connects the models exactly: once the edge count in $G(n,p)$ is specified, all graphs with that count have the same probability.

Throughout, the vertex set is $[n]=\{1,\ldots,n\}$, and the possible edges are the unordered pairs of distinct vertices. Write $N=\binom n2$ for the number of possible edges. In $G(n,p)$, each possible edge is included independently with probability $p$. In $G(n,m)$, a subset of exactly $m$ of the $N$ possible edges is chosen uniformly. Thus $0\le m\le N$. Unless stated otherwise, conditioning on the event of having $m$ edges is understood only when that event has positive probability.

Theorem: If $0<p<1$ and $0\le m\le N$, the distribution of $G(n,p)$ conditional on having exactly $m$ edges is $G(n,m)$.

Proof. Fix any particular graph $H$ on $[n]$ with exactly $m$ edges. In $G(n,p)$, the probability of obtaining $H$ is $p^m(1-p)^{N-m}$: its $m$ edges must be included and its other $N-m$ possible edges must be absent. This value is the same for every such $H$. There are $\binom Nm$ graphs with exactly $m$ edges, so the probability of the conditioning event is $\binom Nm p^m(1-p)^{N-m}>0$. Consequently, the conditional probability of any one such graph is $$ \frac{p^m(1-p)^{N-m}}{\binom Nm p^m(1-p)^{N-m}}=\frac{1}{\binom Nm}. $$ This is precisely the uniform distribution defining $G(n,m)$. $\square$

The restriction $0<p<1$ ensures that every edge count from $0$ to $N$ has positive probability. At $p=0$, conditioning is meaningful only for $m=0$; at $p=1$, it is meaningful only for $m=N$. In those cases the conditioned graph is the unique empty or complete graph, respectively.

Worked Example: A Conditional Distribution on Four Vertices

Take $n=4$, so the possible edge set is $\{12,13,14,23,24,34\}$ and $N=\binom42=6$. Let $p=1/3$ and condition on having $m=2$ edges. A particular graph, for example the graph with $V=\{1,2,3,4\}$ and $E=\{12,34\}$, has unconditioned probability $(1/3)^2(2/3)^4=16/729$. There are $\binom62=15$ two-edge graphs, so the probability of having exactly two edges is $15(16/729)=240/729=80/243$. The conditional probability of this particular graph is therefore $(16/729)/(80/243)=1/15$.

The same calculation applies to each of the other fourteen two-edge graphs, since each has two included edges and four absent edges. Check: the conditional probabilities sum to $15(1/15)=1$, as required, and each of the $\binom62=15$ eligible graphs receives equal probability.

A Shared Random Ordering

Conditioning identifies one fixed-edge model inside $G(n,p)$. A coupling gives a second useful connection. A coupling means constructing random objects together on one probability space so that each object has its required distribution. Here the construction uses one uniformly random ordering of all possible edges.

Construction: Choose a uniformly random permutation $e_1,e_2,\ldots,e_N$ of the possible edges. For each $m$, let $G_m$ have vertex set $[n]$ and edge set $\{e_1,\ldots,e_m\}$, with $G_0$ having no edges. Independently choose $M$ with binomial distribution $\operatorname{Bin}(N,p)$, and let $G_p$ have edge set $\{e_1,\ldots,e_M\}$.

For every fixed $m$, $G_m$ has distribution $G(n,m)$: each $m$-element edge set occupies the first $m$ places in exactly the same number of permutations. Also, $G_p$ has distribution $G(n,p)$. To see the latter directly, fix a graph $H$ with $k$ edges. The chance that $M=k$ is $\binom Nk p^k(1-p)^{N-k}$, and conditional on $M=k$ the chance that the first $k$ edges are exactly $E(H)$ is $1/\binom Nk$. Their product is $p^k(1-p)^{N-k}$, the probability of $H$ in the independent-edge model.

The construction makes the graphs nested: if $a\le b$, then every edge of $G_a$ is also an edge of $G_b$. A graph property $\mathcal A$ on the fixed vertex set $[n]$ is increasing if, whenever a graph has $\mathcal A$, adding edges while keeping the vertex set unchanged preserves $\mathcal A$. For example, “contains a triangle” is increasing; “has exactly three edges” is not.

Proposition: If $\mathcal A$ is increasing, then $\Pr(G(n,m)\text{ has }\mathcal A)$ is nondecreasing as $m$ increases from $0$ to $N$.

Proof. Fix $0\le a\le b\le N$ and use the shared ordering. If $G_a$ has $\mathcal A$, then $G_b$ has $\mathcal A$, because $E(G_a)\subseteq E(G_b)$ and $\mathcal A$ is increasing. Thus the event that $G_a$ has $\mathcal A$ is contained in the event that $G_b$ has $\mathcal A$, so its probability is no larger. Since $G_a$ and $G_b$ have distributions $G(n,a)$ and $G(n,b)$, the claimed monotonicity follows, including the endpoint cases $a=0$ or $b=N$. $\square$

Transferring Probability Bounds

In the coupling, $G_p=G_M$, where $M$ is independent of the random edge ordering. For an increasing property $\mathcal A$, if $M\ge m$ and $G_m$ has $\mathcal A$, then $G_M$ has $\mathcal A$. If $M\le m$ and $G_M$ has $\mathcal A$, then $G_m$ has $\mathcal A$. These containments give useful bounds.

Transfer bounds: For an increasing property $\mathcal A$, any $0\le m\le N$, and $M\sim\operatorname{Bin}(N,p)$, $$ \Pr(G(n,m)\text{ has }\mathcal A)\Pr(M\ge m) \le \Pr(G(n,p)\text{ has }\mathcal A) \le \Pr(G(n,m)\text{ has }\mathcal A)+\Pr(M>m). $$

Proof. Let $A_m$ be the event that $G_m$ has $\mathcal A$. The random variable $M$ is independent of the edge ordering, so $A_m$ and $\{M\ge m\}$ are independent. On their intersection, $G_M$ contains $G_m$, and hence has $\mathcal A$. Therefore $\Pr(G_M\text{ has }\mathcal A)\ge\Pr(A_m)\Pr(M\ge m)$, proving the lower bound.

For the upper bound, if $G_M$ has $\mathcal A$ and $M\le m$, then $G_m$ has $\mathcal A$, again by monotonicity. Thus the event that $G_M$ has $\mathcal A$ is contained in the union of $A_m$ and $\{M>m\}$. The probability of a union is at most the sum of the probabilities, giving the upper bound. The argument also applies at $m=0$ and $m=N$; the binomial tail probabilities automatically account for those endpoints. $\square$

These inequalities are useful when a property is easier to study at a fixed edge count. The binomial tail factors indicate how much of the $G(n,p)$ distribution lies on the relevant side of that count. The bounds are not claims that $G(n,p)$ always has more or fewer edges than $G(n,m)$; the random count $M$ may lie on either side of $m$.

Worked Example: A Path in $G(3,p)$

On $V=\{1,2,3\}$, the possible edges are $\{12,13,23\}$. Consider the increasing property $\mathcal A$ of containing a path with two edges. With $m=1$, none of the three one-edge graphs has this property. With $m=2$, the three possible edge sets are $\{12,13\}$, $\{12,23\}$, and $\{13,23\}$; each is a path on all three vertices. With $m=3$, the graph is a triangle and contains such a path as a subgraph. Thus the fixed-edge probabilities are $0,1,1$ for $m=1,2,3$.

Now set $p=2/5$. The number $M$ of edges has distribution $\operatorname{Bin}(3,2/5)$, and this property holds exactly when $M\ge2$. Therefore $\Pr(\mathcal A)=\binom32(2/5)^2(3/5)+(2/5)^3=36/125+8/125=44/125$. The coupling gives the same answer: the first two edges in any ordering form a path, so success occurs exactly when $M\ge2$.

Check: the count of successful graphs at $m=2$ is three out of the three possible two-edge sets, giving probability $3/3=1$; at $m=1$, it is zero out of three. The probabilities $0,1,1$ are nondecreasing, as the proposition requires.

Worked Example: Bounding the Probability of a Triangle

Take $V=\{1,2,3,4\}$, whose possible edge set is $\{12,13,14,23,24,34\}$, and let $\mathcal A$ be the increasing property of containing a triangle. In $G(4,3)$, there are $\binom63=20$ possible three-edge sets. Exactly four are triangles: $\{12,13,23\}$, $\{12,14,24\}$, $\{13,14,34\}$, and $\{23,24,34\}$. A three-edge graph contains a triangle only when its edge set is exactly one of these, so $\Pr_{G(4,3)}(\mathcal A)=4/20=1/5$.

Use $p=1/2$, for which $M\sim\operatorname{Bin}(6,1/2)$. Directly from the binomial probabilities, $\Pr(M\ge3)=(20+15+6+1)/64=42/64=21/32$, and $\Pr(M>3)=(15+6+1)/64=22/64=11/32$. The transfer bounds give $(1/5)(21/32)=21/160\le\Pr_{G(4,1/2)}(\mathcal A)\le1/5+11/32=87/160$.

For an independent check, each of the four triangle events occurs in eight of the $2^6=64$ graphs, giving $32$ event-graph incidences. Any pair of distinct triangles together require five edges, so each pair intersection contains $2$ graphs; there are $\binom42=6$ pairs, contributing $12$. Any three triangles together require all six edges, so each of the $\binom43=4$ triple intersections contains one graph; the intersection of all four also contains one graph. Inclusion-exclusion therefore gives $32-12+4-1=23$ graphs containing a triangle, and the probability is $23/64$. Substitution into the bounds gives $21/160\le23/64\le87/160$, confirming them.

A Common Conditioning Pitfall

Conditioning on the total edge count does not leave the individual edge indicators independent. For a concrete calculation, take $G(3,1/2)$ and condition on exactly one edge. The probability that edge $12$ is present and the total edge count is one is $(1/2)^3=1/8$: edge $12$ must be present and edges $13$ and $23$ absent. The probability of exactly one edge is $3(1/8)=3/8$. Hence $\Pr(12\text{ is present}\mid |E|=1)=(1/8)/(3/8)=1/3$, not $1/2$. Indeed, the conditioned graph is uniform among the three one-edge graphs, and the three edge indicators cannot vary independently when their sum is fixed.

The precise distinction is useful: conditioning gives a uniform distribution over graphs of a specified size, while the coupling compares graphs of different sizes by nested edge sets. For increasing properties, that nesting proves monotonicity and the transfer bounds; it does not imply that conditioning preserves independent edge choices.

Check Your Understanding

Use the conditional-distribution proof and the shared-ordering coupling to answer the following.

For $n=5$, $0<p<1$, and $m=4$, what is the conditional probability of any particular graph with four edges, given that $G(5,p)$ has four edges?
Why is conditioning on $m$ edges not meaningful in $G(n,0)$ when $m>0$?
Give an example of a graph property that is increasing and one that is not increasing.
For an increasing property $\mathcal A$, explain why $\Pr(G(n,m)\text{ has }\mathcal A)$ cannot decrease when $m$ is raised by one.
In the triangle example, identify which binomial tail appears in the lower transfer bound and why the event $M\ge3$ is required.

Conditioning and Coupling G(n,p) With G(n,m)

What You'll Learn

Conditioning on the Number of Edges

Worked Example: A Conditional Distribution on Four Vertices

A Shared Random Ordering

Transferring Probability Bounds

Worked Example: A Path in \(G(3,p)\)

Worked Example: Bounding the Probability of a Triangle

A Common Conditioning Pitfall

Check Your Understanding

Conditioning and Coupling G(n,p) With G(n,m)

What You'll Learn

Conditioning on the Number of Edges

Worked Example: A Conditional Distribution on Four Vertices

A Shared Random Ordering

Transferring Probability Bounds

Worked Example: A Path in \(G(3,p)\)

Worked Example: Bounding the Probability of a Triangle

A Common Conditioning Pitfall

Check Your Understanding

Previous

Next