brevity is the soul of wit fast ig
FKG
FKG says if \(F,G\) are increasing functions of independent random variables \(X_1,\ldots, X_n\) then we have
\[ \mathop{\mathrm{\mathbb{E}}}[FG] \ge \mathop{\mathrm{\mathbb{E}}}[F]\mathop{\mathrm{\mathbb{E}}}[G]. \]
For instance, suppose that \(X_1,\ldots, X_n\) are whether edges exist in erdos renyi graph. And \(F\) was the indicator of “existence of a 4-clique” and \(G\) was the indicator of “graph is connected”. Then the inequality reads
“Probability of being connected and containing a 4-clique is larger than if you pretended like these were independent events.”
Or if \(F\) was “number of triangles in graph” then you have “expected number of triangles conditional on having a 4-clique is larger than expected number of triangles with no conditioning.”
This makes a lot of sense: positively correlated things should help each other out.
janson
Let \(R\) be a random subset of \([n]\) generated somehow. Let \(A_i\) be the event that \(S_i\subseteq R\). Let \(X = \sum_i \mathbb{1}_{A_i}\). Define \[ \Delta = \sum_{A\not\perp B} \mathop{\mathrm{\mathbb{E}}}[I_A I_B] \]
Then you get a tail bound \[ \Pr[X\le \mathop{\mathrm{\mathbb{E}}}X - t]\le \exp(\frac{-t^2}{2\Delta}). \]
prototypical example: analyze number of triangles in graph.
Example.
Let \(R\) be, you choose some edges (edros renyi graph). Index the \(\binom{n}{3}\) potential triangles in the graph. Define event \(A_i\) to be the event that all edges in the \(i\)-th triangle exist. Then \(\Delta = \Theta(p^3 n^3 + p^{5}\binom{n}{4}).\)
So you can say some nice things about the triangle counts in your graph.
Like this is pretty neat. Usually if you were just second-moment-methoding your probabiltiy bounds start kicking in at the same place, but they are way weaker.
martingales
After working with martingales for a bit on the pset I’m not sure I have a great intuition for them. But the vague idea that I have is, you wanna find some kind of invariant. Feels like hoping to transform your RV into at least a supermartingale / submartingale seems like a pretty general and reasonable thing to do. Probably do more examples to get a better sense for when it’s useful.