Coupling in theorem for monotone increasing class of graphs

Question

I am looking at a proof of a theorem related to ER graphs. The result makes intuitive sense to me but the proof does not. It is an example of "coupling" which I think is where my understanding breaks down. The theorem is as follows

Suppose $\mathcal{P}$ is a monotone increasing class of graphs. Then for any $n\in \mathbb{N}$ and any $p,q$ with $0\leq p < q \leq 1$, we have $\mathbb{P}[G(n,p)\in \mathcal{P}]\leq\mathbb{P}[G(n,q)\in\mathcal{P}]$.

The idea is to sample two random graphs $G_{1}=([n],E_{1})$ and $G_{2}=([n],E_{2})$ such that $G_{2}\subset G_{1}$, $G_{1}$ is a realisation of $G(n,p)$ and $G_{2}$ is a realisation of $G(n,q)$. This is done by defining a uniform random variable $U_{e}$ for each $e\in E(K_{n})$, then defining $E_{1} = \{e\in E(K_{n}):U_{e} \leq q\}$ and $E_{2} = \{e\in E(K_{n}):U_{e} \leq p\}$.

I can see how each of these graphs is a sampling of $G(n,p)$ and $G(n,q)$ respectively however I don't see how this tells us that $\mathbb{P}[G(n,p)\in \mathcal{P}]\leq\mathbb{P}[G(n,q)\in\mathcal{P}]$. It seems like we've just created an artificial example since it is not the case that $G(n,p)\subset G(n,q)$ always. It also seems like these graphs are dependent on each other which I don't quite understand. What am I missing here?

Answer 1

All the things that concern you about how artificial and strange this example is, are true. But the thing that makes coupling work is that they're actually not concerning.

All we need to verify to get the conclusion we want is:

1. $\Pr[G_1 \in \mathcal P] = \Pr[G(n,p) \in \mathcal P]$. That is, the probability $G_1$ has the property we want is the same as the probability that any graph sampled from $G(n,p)$ has the property we want.
2. $\Pr[G_2 \in \mathcal P] = \Pr[G(n,q) \in \mathcal P]$. The same thing, but for $G_2$.
3. $\Pr[G_1 \in \mathcal P] \le \Pr[G_2 \in \mathcal P]$. Here, we're making a statement only about the joint distribution of $(G_1,G_2)$, not about $G(n,p)$ or $G(n,q)$ in general.

It's true that we've made $G_1$ and $G_2$ dependent in a weird way to make statement 3 work, and it wouldn't work for most joint distributions. But it's only a statement about one specific joint distribution, and that's all we need. By chaining these three statements together, we get $$\Pr[G(n,p) \in \mathcal P] = \Pr[G_1 \in \mathcal P] \le \Pr[G_2 \in \mathcal P] = \Pr[G(n,q) \in \mathcal P].$$

---

This is no different from other examples that seem much more reasonable, it's just that random graphs are a very strange random variable that's hard to think about.

But suppose Alice buys 3 lottery tickets, and Bob buys 2, for the same lottery. You want to argue that Alice has a greater chance of winning. The informal reasoning "for every chance that Bob has to win, Alice has a chance to win too, and then Alice has an extra chance on top of that" is exactly talking about a coupling between two distributions.

You could imagine a formal argument: "Imagine Alice bought lottery tickets numbered 1, 2, 3 to one lottery, and Bob bought lottery tickets numbered 1, 2 to a different lottery. But the two lotteries decide to pick the same winning number. Then Alice's probability of winning is clearly greater: if the winning number is 1 or 2, then both win, and if the winning number is 3, then only Alice wins."

And then someone might object: "But that isn't how Alice and Bob's joint distribution actually looks! In reality, they're buying tickets for the same lottery. There is literally zero chance that both of them will have the winning number."

And then the justification for what makes the coupling work is: "By considering the alternate situation in which Alice and Bob buy tickets for these two weirdly-matching lotteries, we've switched to a situation in which it's obvious that Alice has a greater chance of winning than Bob. But individually, Alice's winning changes haven't changed, and neither have Bob's. So the same inequality must hold in reality!"