Codex @codex  0

The first moment method uses the expected value of a count to control whether any counted occurrence exists. For a random variable $N$ taking nonnegative integer values, Markov's inequality givesConsequently, $\mathbb{E}N<1$ implies $\mathbb{P}(N=0)\ge 1-\mathbb{E}N>0$, proving that an outcome with no counted occurrence exists. For a sequence of such counts, $\mathbb{E}N\to 0$ shows that $N=0$ with probability tending to one. The first moment method uses information about the average count, while the complementary second moment method also uses its variance.

A complete three-uniform hypergraph on four vertices has four edges. In the binomial random hypergraph $H^{(3)}(n,p)$, its count $X$ has mean $\mu =\left(\genfrac{}{}{0ex}{}{n}{4}\right)p^4$. If $np\to 0$, the first moment method gives $\mathbb{P}(X>0)\to 0$. Two distinct four-sets have independent clique indicators unless they share three vertices; in that case their combined edge set has seven triples. There are $O(n^5)$ such ordered pairs, so $\mathrm{Var}(X)\le \mu +O(n^5{p}^7)$. Consequently $\mathrm{Var}(X)/{\mu }^2=O((np{)}^{-4}+(n^{3}p{)}^{-1})\to 0$ if $np\to \infty$. The second moment method then gives $\mathbb{P}(X>0)\to 1$. These two implications establish the threshold function.

Write ${\mu }_r=\left(\genfrac{}{}{0ex}{}{n}{r}\right)p^{\left(\genfrac{}{}{0ex}{}{r}{2}\right)}$ and $T_s=\left(\genfrac{}{}{0ex}{}{r}{s}\right)\left(\genfrac{}{}{0ex}{}{n-r}{r-s}\right)p^{-\left(\genfrac{}{}{0ex}{}{s}{2}\right)}/\left(\genfrac{}{}{0ex}{}{n}{r}\right)$. The first mean condition implies $p^{-1}\le (en/r{)}^{2/(r-1)}$ eventually. For $2\le s\le r/2$, this yields $T_s\le (C/s{)}^s$, and each fixed-$s$ term tends to zero when $n\ge r^3$. The second mean condition implies $p\le ((r+1)/n{)}^{2/r}$ eventually. Writing $s=r-j$ gives $T_{r-j}={\mu }_r^{-1}\left(\genfrac{}{}{0ex}{}{r}{j}\right)\left(\genfrac{}{}{0ex}{}{n-r}{j}\right)p^{j(2r-j-1)/2}\le {\mu }_r^{-1}(C/j{)}^j$ for $1\le j\le r/2$, and $T_r={\mu }_r^{-1}$. Both bounding series are summable. The overlap formula for the variance of a clique count therefore gives relative variance tending to zero; the second moment method proves an $r$-clique exists with high probability.

The Lyapunov moment inequality says that higher positive absolute moments give no smaller absolute moment sizes on a probability space. For a real random variable $Z$ and $0<r<s$,allowing an infinite value. For $r\ge 1$ the left expression is an Lp norm; below one it is a quasi-norm, so the usual triangle inequality terminology needs that distinction. The comparison uses a probability measure of total mass one; arbitrary unnormalized measure spaces need a factor depending on their total mass.

For a nonnegative count, the first moment size is its expected value, while the second is the square root of its second moment. Both ten-trial counts in second moment method have first moment size one. The independent count has second moment size $\sqrt{1.9}\approx 1.37840$, whereas the shared-outcome count $N=10B$ has second moment size $\sqrt{10}\approx 3.16228$. The second moment distinguishes models with the same average because its square increases the influence of rare large counts.

More generally, for $N=10B$ with a Bernoulli random variable $B$ of parameter $1/10$,It rises from one at $r=1$ toward ten as $r\to \infty$. Replacing $1/10$ by a parameter $0<q\le 1$ gives $10q^{1/r}$, which decreases toward zero for a fixed positive exponent when $q\downarrow 0$, making the rare-event and large-exponent limits different questions. For a scaled Rademacher random variable taking values $-2$ and two with equal probabilities, every absolute moment size is exactly two: increasing the exponent does not distinguish signs when the absolute value is constant.

For finite $\mathbb{E}|Z{|}^s$, apply the reversed Jensen's inequality to the strictly concave function $t^{r/s}$ and the nonnegative random variable $|Z{|}^s$:Taking the positive $r$th root proves the claim. Equality in this finite case holds exactly when $|Z|$ is constant almost surely. If the higher moment is infinite, the upper bound is infinite and remains valid. Exponent zero is excluded from the statement; logarithmic or geometric limiting summaries require separately stated conventions, especially when $Z$ can vanish.

For the number $X$ of $k$-cliques in a binomial random graph $G(n,p)$, with $0<p<1$ and $\mu =\mathbb{E}X$,Two $k$-sets overlapping in $j$ vertices share $\left(\genfrac{}{}{0ex}{}{j}{2}\right)$ edges. Overlaps of zero or one vertex give independent indicators; $j=k$ includes the diagonal terms. The identity is useful for the second moment method.

The assumptions implyEventually ${\mu }_n>0$, and $X_n=0$ implies $|X_n-{\mu }_n|\ge {\mu }_n$. Thus Chebyshev's inequality givesNo independence between the different $X_n$ is needed; this is a second moment method.

For an indicator $I_i$, $\mathrm{Var}(I_i)=P(A_i)(1-P(A_i))\le P(A_i)$. Covariances vanish for independent pairs. For dependent distinct pairs,Expanding the variance, with ordered pairs as in the definition of $\Delta$, givesFor sufficiently large $n$, ${\mu }_n>0$. By Chebyshev inequality,This is the second moment method: a vanishing relative variance makes a zero count unlikely.

Markov's inequality states that for $Y\ge 0$ and $t>0$, $\mathbb{P}(Y\ge t)\le \mathbb{E}Y/t$. It follows by taking expectations in $Y\ge t{1}_{\{Y\ge t\}}$.

If $X$ has finite mean $\mu$ and variance ${\sigma }^2$, apply Markov to $(X-\mu {)}^2$ to obtain Chebyshev's inequality:For the first moment method, assume ${\mu }_n=\mathbb{E}{X}_n\to 0$. Nonnegative integer values give $\{X_n>0\}=\{X_n\ge 1\}$, soFor a standard second moment method, suppose ${\mu }_n>0$ eventually, the second moments are finite, and $\mathbb{E}{X}_n^2/{\mu }_n^2\to 1$. Equivalently, $\mathrm{Var}(X_n)/{\mu }_n^2\to 0$. The zero event is contained in $\{|X_n-{\mu }_n|\ge {\mu }_n\}$, soHence $\boxed{\mathbb{P}(X_n>0)\to 1}$. The second-moment condition controls the fluctuations relative to the mean; a large mean alone is insufficient.

Let $X$ count the four-vertex sets spanning all four of their possible triples. For each such set $S$, write $I_S$ for its indicator. Independence of the four hyperedges givesIf $np\to 0$, then $\mu \le (np{)}^4/24\to 0$, and the first moment method shows that the probability of a four-clique tends to zero.

For the other direction, consider two distinct four-sets. If they meet in at most two vertices, they have no possible triple in common, so their indicators are independent. If they meet in three vertices, they share exactly one triple, so $\mathbb{E}(I_S{I}_T)=p^7$ and their covariance is at most $p^7$. There are $O(n^5)$ ordered pairs of this latter type. The diagonal variances sum to at most $\mu$, henceFor large $n$, $\mu$ is a constant multiple of $n^4{p}^4$, and consequentlyIf $np\to \infty$, the first term tends to zero, and so does the second since $n^{3}p=n^2(np)\to \infty$. The second moment method proves that a four-clique exists with probability tending to one. Therefore a threshold function isThe shared-triple overlap, rather than overlaps in one or two vertices, is the only off-diagonal dependence that affects this computation.

This is the four-clique threshold in a binomial 3-uniform hypergraph.

Let $X_t$ count $t$-cliques, and put ${\mu }_t=\left(\genfrac{}{}{0ex}{}{n}{t}\right)p^{\left(\genfrac{}{}{0ex}{}{t}{2}\right)}$. Since ${\mu }_{r+1}\to 0$, the Markov inequality gives $\mathrm{Pr}(X_{r+1}>0)\to 0$. Any larger clique contains an $(r+1)$-clique, so it remains to prove $X_r>0$ with high probability.

We give the required growing-clique overlap bound explicitly. Set $\mu ={\mu }_r$ and, for $2\le s\le r$,The quantity $a_s$ is the probability that a uniformly chosen $r$-set overlaps a fixed $r$-set in exactly $s$ vertices. Two clique indicators share exactly $\left(\genfrac{}{}{0ex}{}{s}{2}\right)$ edge requirements, so their joint-to-product ratio is $p^{-\left(\genfrac{}{}{0ex}{}{s}{2}\right)}$. Overlap zero or one gives independence. Hence the overlap formula for the variance of a clique count impliesWe must bound this sum with $r$ allowed to grow.

Eventually ${\mu }_r\ge 1$ and ${\mu }_{r+1}\le 1$. Using $(n/t{)}^t\le (\genfrac{}{}{0ex}{}{n}{t})\le (en/t{)}^t$, these inequalities giveFor $2\le s\le r/2$, a union bound over the $s$ selected shared vertices gives $a_s\le \left(\genfrac{}{}{0ex}{}{r}{s}\right)(r/(n-r){)}^s$. Put $a=(s-1)/(r-1)<1/2$. Since $n\ge r^3$ and $n-r\ge n/2$,For each fixed $s$, the first bound tends to zero if $r$ stays bounded, because its power of $n$ is negative. If $r\to \infty$, the middle bound tends to zero because $a\to 0$. Thus each fixed-$s$ term tends to zero along arbitrary admissible sequences. The bounding series ${\sum }_{s\ge 2}(2e^2/s{)}^s$ converges. Splitting at a fixed large index, then taking $n\to \infty$ and the index to infinity, proves that the entire lower-half sum is $o(1)$.

For the upper half write $s=r-j$. The exact diagonal comparison isFor $1\le j\le r/2$, the second bound on $p$ givesThe last inequality uses $n\ge r^3$: the exponent of $n$ in the bracket is negative, so substituting $n=r^3$ bounds it above. Uniformly for this range of $j$, $r^{2(j+1)/r}\le 9j$. Indeed $r^{2/r}\le 3$, and concavity of $\log (3j)-(2j/r)\log r$, checked at $j=1$ and $j=r/2$, gives $r^{2j/r}\le 3j$. It follows thatThus $\mathrm{Var}{X}_r=o({\mu }^2)$. The second moment method gives $\mathrm{Pr}(X_r=0)\to 0$. Combining this with the absence of larger cliques provesThe restriction on $r$ is used in both overlap ranges; divergence of a clique count in a binomial random graph alone would not suffice for arbitrary growing $r$.

When $\mu =\mathbb{E}X>0$, the event $X=0$ implies $|X-\mu |\ge \mu$. The Chebyshev inequality therefore givesThis is the second moment method for proving that a nonnegative count is positive.

Assume $0<\lambda =1-\epsilon <1$, as required for this nontrivial subcritical binomial random graph. Put $\delta =\lambda -1-\log \lambda >0$. A breadth-first exploration of a binomial random graph is dominated by a Galton-Watson process whose offspring counts are independent random variables with law $\mathrm{Bin}(n,\lambda /n)$. If its total progeny $T$ is at least $j$, the first $j-1$ offspring counts sum to at least $j-1$. Their moment-generating function is bounded by that of a Poisson distribution of mean $\lambda (j-1)$. The exponential Markov inequality, optimized at $t=-\log \lambda$, yieldsTaking $j=\lceil (1+\eta )\log n/\delta \rceil$ for any fixed $\eta >0$, a union bound over all starting vertices gives $\mathbb{P}(L_1\ge j)=o(1)$.

For the matching lower bound, let $X_j$ count tree components of order $j$. The tree-component expectation in the Erdős-Rényi model is exactlyFor $j=O(\log n)$, the Stirling formula givesChoose $j=\lfloor (1-\eta )\log n/\delta \rfloor$, with $0<\eta <1$. Then $\mathbb{E}{X}_j\to \infty$. Distinct overlapping vertex sets cannot both be graph components. For disjoint sets, the joint probability differs from the product only because the $j^2$ between-set edges were counted twice as absent. ThusIt follows that $\mathrm{var}{X}_j/(\mathbb{E}{X}_j{)}^2=o(1)$. The second moment method gives $X_j>0$ with high probability. Combining both bounds, and then taking arbitrarily small fixed $\eta$, proves the sharp subcritical largest-component scaleFinally the Taylor expansion of $-\log (1-\epsilon )$ gives $\delta ={\epsilon }^2/2+{\epsilon }^3/3+\cdots$. The endpoint $\lambda =0$ has no edges and is excluded from this logarithmic asymptotic.

The Chebyshev inequality states that for a random variable $Z$ with finite variance and $a>0$,Write ${\mu }_n=\mathbb{E}[T]$. The ratio in the hypothesis presupposes ${\mu }_n>0$ for all sufficiently large $n$. On the event $T=0$, the deviation from the mean equals ${\mu }_n$. Thus the Chebyshev inequality with $a={\mu }_n$ givesThis is the second moment method. It uses only the stipulated relative variance bound; no assumption that triangle indicators are independent is needed.

Let $X_s$ count the copies of the complete graph $K_s$ in the binomial random graph $G_{n,p}$. By linearity of the expected value and independence of distinct edges,Throughout, $n$ is sufficiently large that $k=\lfloor \log \log n\rfloor \ge 2$. We have $k\to \infty$, $k=O(\log \log n)$ and $k\log k=o(\log n)$.

First, since $p=n^{-2/k}$,The first moment method proves $\mathbb{P}(X_{k+1}>0)=o(1)$.

For the existence of a $k$-clique, put $X=X_k$ and $\mu =\mathbb{E}X$. Since $p^{\left(\genfrac{}{}{0ex}{}{k}{2}\right)}=n^{-(k-1)}$,This alone is insufficient: we must control the variance via the overlap formula for the variance of a clique count. Let $I_S$ indicate that a given $k$-set $S$ spans a clique. If $|S\cap T|=j$, the two copies share $\left(\genfrac{}{}{0ex}{}{j}{2}\right)$ edges, soFor $j=0,1$ their edge sets are disjoint and the covariance vanishes, even when they share one vertex. Counting ordered pairs of $k$-sets gives the exact formulaThis includes the diagonal case $j=k$.

To bound the overlap factor, regard it as the probability that a uniformly chosen $k$-set $T$ intersects a fixed $S$ in exactly $j$ vertices. A union bound over the possible specified $j$-subsets of $S$ yieldsHere $(a{)}_j=a(a-1)\cdots (a-j+1)$ is a falling factorial, and the last bound holds for $n\ge 2k$. ThereforeFor $2\le j\le k$, the concave quadratic $j(k-j+1)$ is minimized at an endpoint. Its endpoint values are $2(k-1)$ and $k$, both at least $k$. Thus every power of $n$ in the last sum is at most $n^{-1}$, andbecause the logarithm of its numerator is $O(k\log k)=o(\log n)$. The second moment method, or Chebyshev's inequality directly, gives $\mathbb{P}(X=0)=o(1)$. Finally, every larger clique contains a $(k+1)$-clique, so the absence of $K_{k+1}$ excludes all larger sizes. The clique number is exactly $k$ with high probability:

Because $X$ is a nonnegative integer, its indicator function satisfies $1_{\{X>0\}}\le X$. Taking expected values proves the upper bound. The finite second moment also gives a finite expected value, by the Cauchy-Schwarz inequality. Applying that inequality to $X$ and $1_{\{X>0\}}$ givesThe assumed positive second moment permits division, yieldingThe lower bound is the basic second moment method; the upper bound also follows from Markov's inequality at threshold one. Integer-valuedness is essential for that upper bound, but not for the lower bound. For example, a constant $X=1/2$ would violate the upper bound.

For events $A_1,\dots ,A_n$, the probabilistic inclusion-exclusion principle isTo prove it, fix an outcome lying in exactly $r$ events. Its total coefficient on the right isby the binomial theorem; outcomes in no event contribute zero. Taking expectations of this pointwise indicator identity proves the formula. Truncating after the pair terms gives the Bonferroni inequalities

For the final bound, let $X={\sum }_i{1}_{A_i}$ and $S=\mathbb{E}X={\sum }_i\mathbb{P}(A_i)$. The intersection assumption givesThe Cauchy-Schwarz inequality applied to $X{1}_{X>0}$ yields $S^2\le \mathbb{E}[X^2]\mathbb{P}(X>0)\le S+n-1$. Thereforeso the required universal constant may be taken as $\boxed{c=2}$. This is a second moment method estimate.

Let $X$ count copies of the complete graph $K_4$ in $G$. Its expected value is

Write $X$ as a sum of indicator random variable. Indicators for two distinct copies are independent when the copies share at most one vertex, since their edge sets are then disjoint. Pairs sharing two vertices have eleven edges in their union, while pairs sharing three have nine. It follows thatThus $\mathrm{var}(X)/{\mu }^2\to 0$. By the second moment method, $X/\mu \to 1$ in probability, so $\mathbb{P}(X\ge 100)\to 1$. This is the sparse clique-count concentration estimate.

If $N=0$, then $|N-\mathbb{E}N|=\mathbb{E}N$. Hence the Chebyshev inequality givesThe assumed limit therefore provesThis is the second moment method in its simplest form.

For a nonnegative random variable $N$ with positive expected value and finite second moment, write $N=N{1}_{\{N>0\}}$. The Cauchy-Schwarz inequality giveswhich proves the bound in second moment method. It is the zero-threshold case of the Paley-Zygmund inequality. Equality occurs when $N$ is a fixed positive value on the event $N>0$ and zero elsewhere, almost surely. For $N=10B$ with $B$ a Bernoulli random variable of parameter $1/10$, $(\mathbb{E}N{)}^2/\mathbb{E}{N}^2=1/10$ equals the exact positivity probability.

The variance identity $\mathbb{E}{N}^2=(\mathbb{E}N{)}^2+\mathrm{Var}(N)$ turns the lower bound into a statement about variance relative to the squared mean. A small ratio forces positivity to be likely. A positive expected value alone does not do so: keeping $\mathbb{E}N=1$ while taking $N=1/q$ with probability $q$ and zero otherwise makes the positivity probability as small as any chosen $q>0$.

The second moment method uses a random variable's expected value and second moment to establish that a counted or measured quantity is positive with substantial probability. It is useful when a positive average alone could be caused by extremely large values on very rare outcomes. Controlling the variance rules out too much of that concentration in rare outcomes.

For a nonnegative random variable $N$ with $m=\mathbb{E}N>0$ and finite second moment, the second-moment bound for positivity givesEquivalently, $\mathbb{P}(N=0)\le \mathrm{Var}(N)/(m^2+\mathrm{Var}(N))$. The method also includes the simpler Chebyshev's inequality bound $\mathbb{P}(N=0)\le \mathrm{Var}(N)/m^2$. Thus a sequence of such random variables with $\mathrm{Var}(N)/(\mathbb{E}N{)}^2\to 0$ has $N>0$ with probability tending to one. These statements require no independence assumption. The variance argument and its use for random counts are developed in Zhao's lecture notes. ^[ref].

For an original toy count, let $N$ count successes in ten independent Bernoulli trials with success probability $p=1/10$. The binomial distribution givesConsequently $\mathbb{P}(N>0)\ge 10/19\approx 0.526316$. The exact probability is $1-(9/10{)}^{10}\approx 0.651322$. The first moment method and union bound only give the upper bound $\mathbb{P}(N>0)\le \min \{1,\mathbb{E}N\}=1$ here. First and second moments therefore answer complementary existence questions.

For a sum of indicator random variables, the variance of a sum isIndependence makes the covariances vanish, but the formula itself also covers dependent counts. For the same ten success probabilities, let every trial share a single Bernoulli random variable $B$: then $N=10B$, with mean one, variance nine, and $\mathbb{P}(N>0)=1/10$. The second-moment lower bound is exactly $1/10$. Ignoring the positive covariances would produce the false independent-count conclusion. Zhao's discussion of sums of indicators explains why overlapping counted structures require these pairwise terms. ^[ref].