Prove that the probability there exists at least 10 triangles in the random graph is greater in RG(p) than RG(q) if p > q

discrete mathematicsgraph theoryprobabilityrandom-graphs

I came across this question and I don't know where to begin:

Assume you have a random 100-vertex graph and define the probability of a graph G to be $p^{E(G)}(1-p)^{100 choose 2 – E(G)}$ where $E(G)$ is the number of edges and p is the parameter (the probability a given edge exists). Prove that the probability there exists at least 10 triangles in the random graph is greater in RG(p) then RG(q) if p > q

Does anyone have any suggestions on how to start?

Best Answer

This is a really good beginner question, and goes through one of the foremost notions in stochastic theory : that of stochastic domination. It avoids any large computation and provides a natural notion which is easy to prove via smart coupling.

$\underline{\mathit{Stochastic \ domination}}$

Definition : Suppose that $X,Y$ are real valued random variables. Then $X$ is said to (first order) stochastically dominate $Y$ if $P(X \geq t) \geq P(Y \geq t)$ for every real $t$.

This is not to be confused with $X \geq Y$ almost surely. It just means that for any $t$, it is likelier that $X$ is larger than $t$ than $Y$ is larger than $t$.

Now, if $G$ is picked as specified in the question, then one can talk about $T(p)$, the number of triangles present in $RG(p)$.

The claim is that $T(p)$ stochastically dominates $T(q)$. If this is true, then $P(T(p) \geq 10) \geq P(T(q) \geq 10)$, as desired.

$\underline{\mathit{A \ theorem\ for\ proving\ stochastic\ domination}}$

The most common method of proving stochastic domination is to create a coupling between the random variables in question. That is, provide a method of constructing random samples from both distributions, even if they may be dependent on each other.

To make this rigorous, we have the notion of coupling : given random variables $X$ and $Y$, we call a random variable $M = (M_1,M_2)$ a coupling of $X$ and $Y$ if the first marginal of $M$ i.e. $M_1$ has the same distribution as $X$, and $M_2$ has the same distribution as $Y$.

To give an example : take $X$ and $Y$ to be independent $Ber(\frac 12)$ random variables. We can couple them independently : let $M$ be the tuple consisting of two independent coin tosses, then the first and second marginal are $X$ and $Y$. But there's another coupling too : flip the first coin , call it $M_1$, and then set $M_2 = M_1$. Then both $M_1$ and $M_2$ are $Ber(\frac 12)$ but clearly dependent on each other. So couplings can occur in many ways.

A popular theorem in this regard is the following :

Let $X,Y$ be random variables. Suppose that we can find a coupling $(M_1,M_2)$ of $X$ and $Y$ such that $M_1 \geq M_2$ almost surely. Then , $X$ stochastically dominates $Y$.

I will leave the proof as an exercise for you to look up or to try yourself, it is pretty much from definition.

$\underline{\mathit{Coupling \ RG(p)\ and \ RG(q)}}$

So how do we couple these random graphs? We go edge-by-edge, a very popular coupling for graphs which are constructed edge-by-edge (so called Erdos-Renyi graphs). Each edge is present or not with probability $p$ for $RG(p)$ and $q$ for $RG(q)$.

Here's our coupling. Do the following for every pair of vertices in the graph :

  • Sample a $Z_p = Ber(p)$ random variable.

  • For a certain $r$, sample a $Z_r = Ber(r)$ random variable, independent of $Z_p$, such that $Z_q = Z_pZ_r$ has the distribution $Ber(q)$. I leave you to calculate $r$ in terms of $p$ and $q$. See that $r > 0$ if $p>q$.

  • Now, for $RG(q)$, set an edge between these vertices if $Z_q = 1$, and for $RG(p)$ set an edge between these vertices if $Z_p = 1$.

That's your coupling! Indeed, for $RG(q)$, each edge is in or not with probability $q$, and similarly for $RG(p)$.

$\underline{\mathit{Finishing \ the \ problem}}$

The nice thing about this construction is that if $Z_q = 1$ then $Z_p = 1$! Therefore , if there's an edge in a random graph of $RG(q)$ from the above construction, then there's an edge in the coupled random graph produced by $RG(p)$ as well!

In particular, $RG(q)$ is a subgraph of $RG(p)$ with probability $1$ under this construction, which of course implies that a triangle in $RG(q)$ remains a triangle in $RG(p)$. Thus, $T(p) \geq T(q)$ almost surely, and we may conclude from the theorem.

$\mathit{Corollaries \ and\ Conclusion}$

Note that the above construction doesn't just restrict itself to triangles : the occurrence of any kind of subgraph , be it a cycle of a particular length or a clique, has increased chance if the parameter increases. Therefore, we get a vast generalization of the statement you make, with little or no effort. Especially without having to go into algebraic expressions and compare them, which is cumbersome and tiring.

There are many uses of stochastic domination in graph theory, especially the edge-to-edge coupling. Stochastic domination is also used in stochastic optimal control theory to regulate random variables so that they behave in a streamlined fashion, allowing the prediction of monotone optimal policies. Last but not the least, stochastic domination is very important in percolation theory and the theory of random walks, since domination by a random variable with certain tail bounds implies that the same tail bounds carry over to the dominated random variable.