University:
Massachusetts Institute of Technology
Course:
18.226 | Probabilistic Method in Combinatorics
Academic year:

2020
Views:

77

Pages:

22
Author:

jadno4u4

4 Second moment method Previously, we used EX ≥ a to deduce P(X ≥ a) > 0. We also saw from Markov’s inequality that for X ≥ 0, if EX is very small, then X is small with high probability. Does EX being (very) large imply that X is large with high probability? No! X could be almost always small but EX could still be large due to outliers (rare large values of X). Often we want to show that some random variable is concentrated around its mean. This would then imply that outliers are unlikely. We will see many methods in this course on proving concentrations of random variables. We begin with the simplest method. It is the easiest to execute, requires the least hypotheses, but only produces weak (though often useful) concentration bounds. Second moment method: show that a random variable is concentrated near its mean by bounding its variance. Variance: Var[X] = E[(X − EX)2 ] = E[X 2 ] − E[X]2 Notation convention: mean µ, variance σ 2 , standard deviation σ. Theorem 4.0.1 (Chebyshev’s inequality). Let X be a random variable with mean µ and standard deviation σ. For any λ > 0 P(|X − µ| ≥ λσ) ≤ λ−2 . Proof. By Markov’s inequality, LHS = P(|X − µ|2 ≥ λ2 σ 2 ) ≤ E[(X − µ)2 ] 1 = 2. 2 2 λσ λ Remark 4.0.2. Concentration bounds that show small probability of deviating from the mean are called tail bounds (also: upper tail bounds for bounding P(X ≥ µ + a) and lower tail bounds for bounding P(X ≤ µ − a)). Chebyshev’s inequality gives tail bounds with polynomial decay. Later on we will see tools that give much better decay (usually exponential) provided additional assumptions on the random variable (e.g., independence). We can rewrite Chebyshev’s inequality as P(|X − EX| ≥ EX) ≤ Var X . 2 (EX)2 Corollary 4.0.3. If Var[X] = o(EX)2 then X ∼ EX whp. Remark 4.0.4. We are invoking asymptotics here (so we are actually considering a sequence Xn of random variables instead of a single one). The conclusion is equivalent to that for every > 0, one has |X − EX| ≤ EX with probability 1 − o(1) as n → ∞. Variance can be calculated from pairwise covariances. Recall the covariance Cov[X, Y ] := E[(X − EX)(Y − EY )] = E[XY ] − E[X]E[Y ]. So Var[X] = Cov[X, X]. Covariance is bilinear in X and Y , i.e., for constants a1 , . . . and b1 , . . . , one has " # X X X Cov ai X i , bj Y j = ai bj Cov[Xi , Yj ]. i j i,j Thus, given X = X1 + · · · + Xn (no assumptions on dependencies between the Xi ’s), we have X X X Var[X] = Cov[X, X] = Cov[Xi , Xj ] = Var[Xi ] + 2 Cov[Xi , Xj ] i,j∈[n] i∈[n] i 0 with probability 1 − o(1). Remark 4.1.4. Here is a slightly stronger inequality in the case of nonnegative random variables. It is a special case of the Paley–Zygmund inequality. I am showing it here because it is neat. It makes no difference for our applications whether we use the next lemma or the previous one. Lemma 4.1.5. For any random variable X ≥ 0, (EX)2 P(X > 0) ≥ . E[X 2 ] Proof. We have P(X > 0) = E[1X>0 ]. By the Cauchy–Schwarz inequality E[1X>0 ] E[X 2 ] ≥ (E[1X>0 X])2 = (EX)2 . Definition 4.1.6 (Graph properties). A graph property P is a subset of all graphs. We say that P is monotone (increasing) if whenever G ∈ P, then any graph obtained by adding edges to G also satisfies P. We say that P is non-trivial if for all sufficiently large n, there exists an n-vertex graph in P and an n-vertex graph not in P. Example 4.1.7. Examples of graph properties • Contains K4 ; i.e., P = {G : K4 ⊂ G} • Connected • Hamiltonian • 3-colorable (a monotone decreasing property) • Planar (monotone decreasing) • Contains a vertex of degree 1 (not monotone increasing or decreasing) Definition 4.1.8 (Threshold function). We say that rn is a threshold function for some graph property P if P(G(n, pn ) satisfies P) → ( 0 if pn /rn → 0, 1 if pn /rn → ∞. Remark 4.1.9. The above definition is most suitable for monotone increasing properties. For other types of properties one may need to adjust the definition appropriately. Remark 4.1.10. From the definition, we see that if rn and rn0 are both threshold functions, then they must be within a constant factor of each other. So it is fine to say “the threshold” of some property, with the understanding that we do not care about constant factors. Later on we will see that every monotone property has a threshold function. Theorem 4.1.11. A threshold function for containing a K3 is 1/n, i.e., ( lim P(K3 ⊂ G(n, pn )) = n→∞ 0 if pn n → 0 1 if pn n → ∞ Proof. Let X be the number of triangles in G(n, p). Then µ := EX = Let σ 2 = Var X. n 3 p3 ∼ n3 p3 /6. If p 1/n, then µ = o(1), so P(X ≥ 1) = o(1) by Markov, and hence X = 0 w.h.p. If p 1/n, then µ → ∞, and we saw earlier that σ µ, so whp X ∼ µ and thus X > 0 whp. Question 4.1.12. What is the threshold for containing a fixed H as a subgraph? The next calculation is similar in spirit to what we did earlier for triangles, but we would like to be more organized as there may be more interacting terms in the variance calculation. General setup. Suppose X = X1 + · · · + Xm where Xi is the indicator random variable for event Ai . Write i ∼ j if i 6= j and the pair of events (Ai , Aj ) are not independent. (For variance calculation, we are only considering pairwise dependence. Warning: later on when we study the Lovász Local Lemma, we will need a strong notion of a dependency graph.) If i 6= j and i 6∼ j then Cov[Xi , Xj ] = 0. Otherwise, Cov[Xi , Xj ] = E[Xi Xj ] − E[Xi ]E[Xj ] ≤ E[Xi Xj ] = P[Ai ∧ Aj ]. Thus Var X = X Cov[Xi , Xj ] ≤ EX + ∆ i,j where X ∆= P(Ai ∧ Aj ) (i,j):i∼j The earlier second moment results (Corollary 4.0.3) imply that If EX → ∞ and ∆ = o(EX)2 then and X ∼ EX and X > 0 whp. We have X P(Ai ∧ Aj ) = X i (i,j):i∼j P(Ai ) X P (Aj | Ai ) j:j∼i In many symmetric situations (e.g. our examples), the following quantity does not depend on i: X ∆∗ = P (Aj | Ai ) j:j∼i (or take ∆∗ to be the maximum such value ranging over all i). Then X ∆= P[Ai ]∆∗ = ∆∗ EX i Thus we have Lemma 4.1.13. If EX → ∞ and ∆∗ = o(EX), then X ∼ EX and X > 0 whp. Theorem 4.1.14. A threshold function for containing K4 is n−2/3 . Proof. Let X denote the number of copies of K4 in G(n, p). Then EX = n 4 p6 ∼ n4 p6 /24. If p n−2/3 then EX = o(1) so X = 0 whp Now suppose p n−2/3 , so EX → ∞. For each 4-vertex subset S, let AS be the event that S is a clique in G(n, p). For each fixed S, one has AS ∼ AS 0 if and only if |S ∩ S 0 | ≥ 2. • The number of S 0 that share exactly 2 vertices with S is 6 n2 = O(n2 ), and for each such S 0 one has P(AS 0 |AS ) = p5 (as there are 5 additional edges, no in the S-clique, that needs to appear clique to form the S 0 -clique). • The number of S 0 that share exactly 3 vertices with S is 4(n − 4) = O(n), and for each such S 0 one has P(AS 0 |AS ) = p3 . Summing over all above S 0 , we find Then X ∆∗ = P(AS 0 |AS ) . n2 p5 + np3 n4 p6 EX. S 0 :|S 0 ∩S|∈{2,3} Thus X > 0 whp by Lemma 4.1.13. For both K3 and K4 , we saw that any choice of p = pn with EX → ∞ one has X > 0 whp. Is this generally true? . We have EXH n5 p7 . Example 4.1.15 (First moment is not enough). Let H = If EX = o(1) then X = 0 whp. But what if EX → ∞, i.e., p n−5/7 ? We know that if n−5/7 p n−2/3 , then XK4 = 0 whp, so XH = 0 whp since K4 ⊂ H. On the other hand, if p n−2/3 , then whp can find K4 , and pick an arbitrary edge to extend to H (we’ll prove this). Thus the threshold for H = is actually n−2/3 , and not n−5/7 as one might have naively predicted from the first moment alone. Why didn’t EXH → ∞ give XH > 0 whp? In the calculation of ∆∗ , one of the terms is np (from two copies of H with a K4 -overlap), and np 6 n5 p7 EXH if p n−2/3 . Definition 4.1.16. Define the edge-vertex ratio of a graph H by ρ(H) = eH /vH . Define the maximum edge-vertex ratio of a subgraph of H: m(H) := max ρ(H 0 ). 0 H ⊂H . We have ρ(H) = 7/5 whereas ρ(K4 ) = 3/2 > 7/5. Example 4.1.17. Let H = It is not hard to check that m(H) = ρ(K4 ) = 3/2 as K4 is the subgraph of H with the maximum edge-vertex ratio. Theorem 4.1.18 (Bollobás 1981). Fix a graph H with vH vertices and eH edges. Then p = n−1/m(H) is a threshold function for containing H has a subgraph. Furthermore, if p n−1/m(H) , then the number XH of copies of H in G(n, p) satisfies, with probability 1 − o(1), n vH ! eH nvH peH XH ∼ EXH = p ∼ . vH aut(H) aut(H) Proof. Let H 0 be a subgraph of H achieving the maximum edge-vertex ratio, i.e., ρ(H 0 ) = m(H). If p n−1/m(H) , then EXH 0 nvH 0 peH 0 = o(1), so XH 0 = 0 whp, hence XH = 0 whp. Now suppose p n−1/m(H) . Let us count labeled copies of the subgraph H in G(n, p). Let J be a labeled copy of H in Kn , and let AJ denote the event that J appears in G(n, p). We have, for fixed J, X X 0 ∆∗ = P (AJ 0 | AJ ) = p|E(J )\E(J)| J 0 ∼J J 0 ∼J For any J 0 ∼ J, we have 0 0 n|V (J )\V (J)| p|E(J )\E(J)| n|V (J)| p|E(J)| since 0 0 0 p n−1/m(H) ≥ n−1/ρ(J∩J ) = n−|V (J)∩V (J )|/|E(J)∩E(J )| . It then follows, after consider all the possible ways that J 0 can overlap with J, that ∆∗ n|V (J)| p|E(J)| EXH . So Lemma 4.1.13 yields the result. 4.2 Existence of thresholds Question 4.2.1. Does every monotone graph property P have a threshold function? E.g., could it be the case that P(G(n, n−1/3 ) ∈ P), P(G(n, n−1/4 ) ∈ P) ∈ [0.1, 0.9] for all sufficiently large n? First, an even simpler question, why is it that if P is a nontrivial monotone property, then P(G(n, p) ∈ P) is an increasing function of p? This is intuitively obvious, but how to prove it? Let us give two (related) proofs of this basic fact. Both are quite instructive. More abstractly, this is not really about graphs, but rather about random subsets (for random graphs, we are taking random subgraphs of edges). Given a collection F of subsets of [n], we say that F is an upward closed set (or up-set) if whenever A ⊂ B and A ∈ F then B ∈ F. We say that an up-set F is nontrivial if ∅∈ / F and [n] ∈ F. Let [n]p denote the random subset of [n] obtained by including every element independently with probability p. Theorem 4.2.2. Let F a nontrivial up-set of [n]. Then p 7→ P([n]p ∈ F) is a strictly increasing function. The first proof is by coupling. Coupling is powerful probabilistic idea. Given two random variables X and Y with individually prescibed distributions, we “couple” them together by considering a single probabilistic process that generates both X and Y in a way that clarifies their relationship. More formally, we construct a joint distribution (X, Y ) whose marginals agree with those of X and Y . Proof 1. (By coupling) Let 0 ≤ p < q ≤ 1. Consider the following process to generate two random subsets of [n]: pick a uniform random vector (x1 , . . . , xn ) ∈ [0, 1]n . Let A = {i : xi ≤ p} and B = {i : xi ≤ q}. Then A has the same distribution as [n]p and B has the same distribution as [n]q . Furthermore, we see that A ∈ F implies B ∈ F. Thus P([n]p ∈ F) = P(A ∈ F) ≤ P(B ∈ F) = P([n]q ∈ F). To see that the inequality strict, we simply have to observe that with positive probability, one has A ∈ / F and B ∈ F (e.g., A = ∅ and B = [n]). The second proof is also uses coupling, but viewed somewhat differently. The idea is that we can obtain [n]p as the union of several independent [n]p0 for some smaller values of p0 . In other words, we are exposing the random subset in several rounds. Proof 2. (By two-round exposure) Let 0 ≤ p < q ≤ 1. Note that B = [n]q has the same distribution as the union of two independent A = [n]p and A0 = [n]p0 , where p0 is chosen to satisfy 1 − q = (1 − p)(1 − p0 ). Thus P(A ∈ F) ≤ P(A ∪ A0 ∈ F) = P(B ∈ F). Like earlier, to observe that the inequality is strict, one observes that with positive probability, one has A ∈ / F and A ∪ A0 ∈ F. The above technique (generalized from two round exposure to multiple round exposures) gives a nice proof of the following theorem (originally proved using the Kruskal–Katona theorem). Theorem 4.2.3 (Bollobás and Thomason 1987). Every nontrivial monotone graph property has a threshold function. Proof. Note that G(n, 1−(1−p)k ) has the same distribution has the union of k independent copies G1 , . . . , Gk of G(n, p). Furthermore, by the monotonicity of the property, if G1 ∪ · · · ∪ Gk ∈ / P, then G1 , . . . , Gk ∈ / P. By independence, P(G(n, 1 − (1 − p)k ) ∈ / P) = P(G1 ∪ · · · ∪ Gk ∈ / P) ≤ P(G1 ∈ / P) · · · P(Gk ∈ / P) To simplify notation, let us write fp = fp (n) = P(G(n, p) ∈ P). Since 1 − (1 − p)k ≤ kp (check by convexity), we have that for any monotone graph property P, any positive integer k ≤ 1/p, 1 − fkp ≤ 1 − f1−(1−p)k ≤ (1 − fp )k . (4.1) Fix any large enough n (so that set of n-vertex graphs satisfying the property P is a nontrival up-set). Since p 7→ fp (n) is a continuous strictly increasing function from 0 to 1 as p goes from 0 to 1 (in fact it is a polynomial in p for each fixed n), there is some “critical” pc = pc (n) with fpc (n) = 1/2. We claim that pc is a threshold function. Indeed, (4.1) implies, if p = p(n) pc (n), then, letting k = k(n) = bp/pc c → ∞, 1 − fp ≤ (1 − fpc )k = 2−k → 0 so fp → 1. Likewise, if p pc , then, letting k = bpc /pc → ∞, we have 1 = 1 − fpc ≤ (1 − fp )k , 2 and thus fp → 0 as n → ∞. Thus pc (n) is a threshold function for P. Remark 4.2.4. Note that, by definition, if p1 (n) and p2 (n) are both threshold functions for the same property, then cp1 (n) ≤ p2 (n) ≤ Cp2 (n) for some constants 0 < c < C. Last section we identified the threshold for the property of containing a fixed subgraph. Let us state the result (at least in the case of triangles, but similar results are known for every subgraph) a bit more precisely, where we use the fact that for a constant c > 0, the number of triangles in G(n, c/n) converges to a Poisson distribution with mean c3 /6 (this can be proved using the “method of moments” but we will not do it here). So   if cn → 0  0 c 3 n P G n, contains a triangle → 1 − e−c /6 if cn → c constant  n  1 if cn → ∞ What about other graph properties? It turns out that we can sometimes identity the transition very precisely. Example 4.2.5. Here are some more examples of threshold functions. The first two statements are in the original Erdős–Rényi (1959) paper on random graphs. The first is an easy (and instructive) exercise in the second moment method. • With p = log n + cn n P (G (n, p) has no isolated vertices) → • With p =    0 if cn → −∞ −e−c e   1 if cn → c if cn → ∞ log n + cn n P (G (n, p) is connected) →    0 −e−c e   1 if cn → −∞ if cn → c if cn → ∞ Coarse threshold Sharp threshold i o Pt Dpet P o S Igoe P Figure 4: Examples of coarse and sharp thresholds. The vertical axis is the probability that G(n, p) satisfies the property. In fact, a much stronger statement is true, connecting the above two examples: consider a process where one adds an random edges one at a time, then with probability 1−o(1), the graph becomes connected as soon as there are no more isolated vertices. • With p = log n + log log n + cn n P(G(n, p) has a Hamiltonian cycle) →    0 −e−c e   1 if cn → −∞ if cn → c if cn → ∞ Like earlier, it is true that with high probability, a random graph becomes Hamiltonian as soon as its minimum degree reaches 2. In the above examples, the probability that G(n, p) satisfies the property changes quickly and dramatically as p crosses the threshold (physical analogy: similar to how the structure of water changes dramatically as the temperature drops below freezing). For example, while for connectivity, while p = log n/n is a threshold function, we see that G(n, 0.99 log n/n) is whp not connected and G(n, 1.01 log n/n) is whp connected, unlike the situation for containing a triangle earlier. We call this the sharp threshold phenomenon. Definition 4.2.6 (Sharp thresholds). We say that rn is a sharp threshold for some graph property P if, for every δ > 0, ( P(G(n, pn ) satisfies P) → 0 if pn ≤ (1 − δ)rn , 1 if pn ≥ (1 − δ)rn . Equivalently, a graph property P exhibits a sharp threshold at rn if, for every > 0, for a given large n, as p increases from 0 to 1, the probability P(G(n, p) ∈ P) increases from to 1 − over a short window of width o(rn ) around rn . On the other hand, if this transition window has width Ω(rn ) for some > 0, then we say that it is a coarse threshold. See Figure 4. We saw coarse thresholds for the “local” property of containing some given subgraph, whereas we saw sharp thresholds for “global” properties such as connectivity. It turns out that this is a general phenomenon. Friedgut’s sharp threshold theorem (1999), a deep and important result, roughly says that: All monotone graph properties with a coarse threshold may be approximated by a local property. In other words, informally, if a monotone graph property P has a coarse threshold, then there is finite list of graph G1 , . . . , Gm such that P is “close to” the property of containing one of G1 , . . . , Gm as a subgraph. We need “close to” since the property could be “contains a triangle and has at least log n edges”, which is not exactly local but it is basically the same as “contains a triangle.” There is some subtlety here since we can allow very different properties depending on the value of n. E.g., P could be the set of all n-vertex graphs that contain a K3 if n is odd and K4 if n is even. Friedgut’s theorem tells us that if there is a threshold, then there is a partition N = N1 ∪ · · · ∪ Nk such that on each Ni , P is approximately the form described in the previous paragraph. In the last section, we derived that the property of containing some fixed H has threshold n−1/m(H) for some rational number m(H). It follows as a corollary of Friedgut’s theorem that every coarse threshold must have this form. Corollary 4.2.7 (of Friedgut’s sharp threshold theorem). Suppose r(n) is a coarse threshold function of some graph property. Then there is a partition of N = N1 ∪ · · · ∪ Nk and rationals α1 , . . . , αk > 0 such that r(n) n−αj for every n ∈ Nj . In particular, if (log n)/n is a threshold function of some monotone graph property (e.g., this is the case for connectivity), then we automatically know that it must be a sharp threshold, even without knowing anything else about the property. Likewise if the threshold has the form n−α for some irrational α. The exact statement of Friedgut’s theorem is more cumbersome. We refer those who are interested to Friedgut’s original 1999 paper and his later survey for details and applications. This topic is connected more generally to an area known as the analysis of boolean functions. Also, it is known that the transition window of every monotone graph property is (log n)−2+o(1) (Friedgut––Kalai (1996), Bourgain–Kalai (1997)). Curiously, tools such as Friedgut’s theorem sometimes allow us to prove the existence of a sharp threshold without being able to identify its exact location. For example, it is an important open problem to understand where exactly is the transition for a random graph to be k-colorable. Conjecture 4.2.8 (k-colorability threshold). For every k ≥ 3 there is some real constant dk > 0 such that for any constant d > 0, ( P(G(n, d/n) is k-colorable) → 1 if d < dk , 0 if d > dk . We do know that there exists a sharp threshold for k-colorability. Theorem 4.2.9 (Achlioptas and Friedgut 2000). For every k ≥ 3, there exists a function dk (n) such that for every > 0, and sequence d(n) > 0, d(n) P G n, n is k-colorable → ( 1 if d(n) < dk (n) − , 0 if d(n) > dk (n) + . On the other hand, it is not known whether limn→∞ dk (n) exists, which would imply Conjecture 4.2.8. Further bounds on dk (n) are known, e.g. the landmark paper of Achlioptas and Naor (2006) showing that for each fixed d > 0, whp χ(G(n, d/n) ∈ {kd , kd + 1} where kd = min{k ∈ N : 2k log k > d}. Also see the later work of Coja-Oghlan and Vilenchik (2013). 4.3 Clique number of a random graph The clique number ω(G) of a graph is the maximum number of vertices in a clique of G. Question 4.3.1. What is the clique number of G(n, 1/2)? Let X be the number of k-cliques of G(n, 1/2). We have n −(k2) f (k) := EX = 2 . k Theorem 4.3.2. Let k = k(n) satisfy f (k) → ∞. Then ω(G(n, 1/2)) ≥ k whp. Proof. For each k-element subset S of vertices, let AS be the event that S is a clique. Let P XS be the indicator random variable for AS . Let X = S∈([n]) XS denote the number of k k-cliques. For fixed k-set S, consider all k-set T with |S ∩ T | ≥ 2: ∗ ∆ = X T ∈([n] k ) 2≤|S∩T |≤k−1 k−1 X k n − k (2i )−(k2) P(AT |AS ) = 2 i k − i i=2 n −(k2) . EX = 2 k omitted It then follows from Lemma 4.1.13 that X > 0 (i.e., ω(G) ≥ k) whp. Theorem 4.3.3 (Bollobás–Erdős 1976 and Matula 1976). There exists a k = k(n) ∼ 2 log2 n such that ω(G(n, 1/2)) ∈ {k, k + 1} whp. Proof. (Sketch) For k ∼ 2 log2 n, n − k −k f (k + 1) = 2 = n−1+o(1) = o(1). f (k) k+1 So the value of f (k) drops rapidly for k ∼ 2 log2 n. Let k0 = k0 (n) be the value with f (k0 ) ≥ 1 > f (k0 + 1). If n is such that f (k0 ) → ∞ while f (k0 + 1) → 0 (it turns out that this is true for most integers n), and thus ω(G) = k0 whp. When f (k0 ) = O(1), we have f (k0 − 1) → ∞ and f (k0 + 1) → 0 so one has ω(G(n, 1/2)) ∈ {k0 − 1, k0 } whp. Remark 4.3.4. The result also implies the same about size of largest independent set in G(n, 1/2) (take complement). Also extends to constant p: ω(G(n, p)) ∼ 2 log1/(1−p) n whp. Since the chromatic number satisfies χ(G) ≥ n/α(G), we have χ(G(n, 1/2)) ≥ (1 + o(1)) n 2 log2 n whp. Later on, using more advanced methods, we will prove χ(G(n, 1/2)) ∼ n/(2 log2 n) whp (Bollobás 1987). Also, later, using martingale concentration, we know show that χ(G(n, p)) is tightly concentrated around its mean without a priori needing to know where the mean is located. 4.4 Hardy–Ramanujan theorem on the number of prime divisors Let ν(n) denote the number of primes p dividing n (do not count multiplicities). The next theorem says that “almost all” n have (1 + o(1)) log log n prime factors Theorem 4.4.1 (Hardy and Ramanujan 1917). For every > 0, there exists C such that all but -fraction of x ∈ [n] satisfy |ν(x) − log log n| ≤ C p log log n The original proof of Hardy and Ramanujan was quite involved. Here we show a “probabilistic” proof due to Turán (1934), which played a key role in the development of probabilistic methods in number theory. Proof. Choose x ∈ [n] uniformly at random. For prime p, let ( Xp = 1 if p|x, 0 otherwise. Set M = n1/10 , and (the sum is taken over primes p). X Xp X= p≤M We have ν(x)−10 ≤ X(x) ≤ ν(x) since x cannot have more than 10 prime factors > n1/10 . So it suffices to analyze X. Since exactly bn/pc positive integers ≤ n are divisible by p, we have bn/pc 1 EXp = = +O n p So EX = 1 n X 1 p≤M 1 +O = log log n + O(1) p n P Here we are applying Merten’s theorem from analytic number theory: p≤n 1/p = log log n + O(1) (the O(1) error term converges to the Meissel–Mertens constant). Next we compute the variance. The intuition is that distinct primes should be have independently. Indeed, if pq divides n, then Xp and Xq are independent. Then pq does not divide n, but n is large enough, then there is some small covariance contribution. (Contrast to the earlier calculations in random graphs, where there are very few nonzero covariance terms, but each can be more significant.) If p 6= q, then Xp Xq = 1 if and only if pq|x. Thus |Cov[Xp , Xq ]| = |E[Xp Xq ] − E[Xp ]E[Xq ]| bn/pqc bn/pc bn/qc − n n n 1 =O n = Thus X |Cov[Xp , Xq ]| . p6=q M2 . n−4/5 n Also, Var Xp = E[Xp ] − (EXp )2 = (1/p)(1 − 1/p) + O(1/n). Combining, we have Var X = X p≤M Var Xp + X Cov[Xp , Xq ] p6=q X1 = + O(1) = log log n + O(1) ∼ EX p p≤M Thus by Chebyshev, for every constant λ > 0 p P |X − log log n| ≥ λ log log n ≤ (Var X)2 1 = 2 + o(1). 2 λ (log log n) λ Finally, recall that |X − ν| ≤ 10, so same asymptotic bound holds with X replaced by ν. Theorem 4.4.2 (Erdős and Kac 1940). With x ∈ [n] uniformly chosen at random, ν(x) is asymptotically normal, i.e., for every λ ∈ R, Z ∞ ν(x) − log log n 1 2 √ lim Px∈[n] ≥λ = √ e−t /2 dt n→∞ log log n 2π λ P The intuition is that the number of prime divisors X = p Xp (from the previous proof) behaves like a sum of independent random variables, the central limit theorem should imply an asymptotic normal distribution. The original proof of Erdős and Kac verifies the above intuition using some more involved results in analytic number theory. Simpler proofs have been subsequently given, and we outline one below, which is based on computing the moments of the distribution. The idea of computing moments for this problem was first used by Delange (1953), who was apparently not aware of the Erdős–Kacs paper. Also see a more modern account by Granville and Soundararajan (2007). The following tool from probability theory allows us to verify asymptotic normality from convergence of moments. Theorem 4.4.3 (Method of moments). Let Xn be a sequence of real valued random variables such that for every positive integer k, limn→∞ E[Xnk ] equals to the k-th moment of the standard normal distribution. Then Xn converges in distribution to the standard normal, i.e., limn→∞ P(Xn ≤ a) = P(Z ≤ a) for every a ∈ R, where Z is a standard normal. Remark 4.4.4. The same conclusion holds for any probability distribution (other than normal) that is “determined by its moments,” i.e., there are no other distributions sharing the same moments. Many common distributions that arise in practice, e.g., the Poisson distribution, satisfy this property. There are various sufficient conditions for guaranteeing this moments property, e.g., Carleman’s condition tells us that any probability distribution whose moments do not increase too quickly is determined by its moments. Proof sketch of Erdős–Kacs Theorem 4.4.2. We compare higher moments of X = ν(x) with that of an idealized Y treating the prime divisors as truly random variables. Set M = n1/s(n) where s(n) → ∞ sufficiently slowly. As earlier, ν(x)−s(n) ≤ ν(x) ≤ v(x). P We construct a “model random variable” mimicking X. Let Y = p≤M Yp , where Yp ∼ Bernoulli(1/p) independently for all primes p ≤ M . We can compute: µ := EY ∼ EX ∼ log log n and σ 2 := Var Y ∼ Var X ∼ log log n. e = (X − µ)/σ and Ye = (Y − µ)/σ. Let X By the central limit theorem (e.g., the Lindeberg CLT), Ye → N (0, 1) in distribution. In particular, E[Ye k ] ∼ E[Z k ] (asymptotics as n → ∞) where Z is a standard normal. e and Ye . It suffices to show that for every fixed k, E[X e k ] ∼ E[Ye k ]. Let us compare X For every set of distinct primes p1 , . . . pr ≤ M , 1 n 1 1 E[Xp1 · · · Xpr − Yp1 · · · Ypr ] = − =O n p1 · · · pr p 1 · · · pr n e k in terms of the Xp ’s (no(1) terms), we get Comparing expansions of X e k − Ye k ] = n−1+o(1) = o(1). E[X e approach those of N (0, 1). The method of moments theorem from So the moments of X e is asymptotically normally distributed. probability then implies that X 4.5 Distinct sums Question 4.5.1. Let S be a k-element subset of positive integers such that all 2k subset sums of S. What is the minimum possible max S? E.g., S = {1, 2, 22 , . . . , 2k−1 } (the greedy choice). We begin with an easy pigeonhole argument. On the other hand, since all 2k sums are distinct and are at most k max S, we have 2k ≤ k max S, so max S ≥ 2k /k. Erdős offered $300 for a proof or disproof that max S & 2k . This remains an interesting open problem. Let us use the second moment to give a modest improvement on the earlier pigeonhole argument. The main idea here is that, by second moment, most of the subset sums lie within an O(σ)-interval, so that we can improve on the pigeonhole estimate ignoring outlier subset sums. Theorem 4.5.2. Let S be a k-element subset of positive integers such that all 2k subset √ sums of S. Then max S & 2k / k. Proof. Let S = {x1 , . . . , xk } and n = max S. Set X = 1 x1 + · · · + k xk where i ∈ {0, 1} are chosen uniformly at random independently. We have µ := EX = and σ 2 := Var X = By Chebyshev, x1 + · · · + xk 2 x21 + · · · + x2k n2 k ≤ . 4 4 √ 3 P(|X − µ| < n k) ≥ . 4 Since X takes distinct values for every (1 , . . . , k ) ∈ {0, 1}k , we have P(X = x) ≤ 2−k for all x, so we have the lower bound √ √ P(|X − µ| < n k) ≤ 2−k (2n k + 1). Putting them together, we get √ 3 2−k (2n k + 1) ≤ . 4 √ So n & 2k / k. Recently, this July, Dubroff–Fox–Xu gave another short proof of this result (with an improved error term O(1)) by applying Harper’s vertex-isoperimetric inequality on the cube (this is an example of “concentration of measure”, which we will explore more later this course). Here for the “n-dimensional boolean cube” we consider the graph on the vertex set {0, 1}n with an edge between every pair of n-tuples that differ in exactly one coordinate. Given A ⊆ {0, 1}n , let δA be the set of all vertices outside A that is adjacent to some vertex of A. k Theorem 4.5.3 (Harper 1966). Every A ⊂ {0, 1}k with |A| = 2k−1 has |∂A| ≥ bk/2c . Remark 4.5.4. Harper’s theorem, more generally, gives the precise value of minA⊂{0,1}n :|A|=m |∂A| for every (n, m). Basically, the minimum is achieved when A is a a Hamming ball (or, if m is not exactly the size of some Hamming ball, then take the first m elements of {0, 1}n when ordered lexicographically). Theorem 4.5.5 (Dubroff–Fox–Xu). If S is a set of k positive integers with distinct subset sums, then ! r k 2k 2 = max S ≥ + o(1) √ . bk/2c π k Remark 4.5.6. The above bound has the currently best known leading constant factor. Proof. Let S = {x1 , . . . , xk }. Let x1 + · · · + xk k A = (1 , . . . , k ) ∈ {0, 1} : 1 x1 + · · · + 1 xk < . 2 Note that due to the distinct sum hypothesis, one can never have x1 s1 + · · · + xn sn = (s1 + · · · + sn )/2. It thus follows by symmetry that |A| = 2k−1 . Note that every element of ∂A corresponds to some subset sum in the open interval x1 + · · · + xk x1 + · · · + xk , + max S 2 2 Since all subset sums are distinct, we must have max S ≥ |∂A| ≥ theorem (Theorem 4.5.3). 4.6 k bk/2c by Harper’s Weierstrass approximation theorem We finish off the chapter with an application to analysis. Weierstrass approximation theorem every continuous real function on an interval can be uniformly approximated by a polynomial. Theorem 4.6.1 (Weierstrass approximation theorem 1885). Let f : [0, 1] → R be a continuous function. Let > 0. Then there is a polynomial p(x) such that |p(x) − f (x)| ≤ for all x ∈ [0, 1]. Proof. (Bernstein 1912) The idea is to approximate f by a sum of polynomials look like “bumps”: n X Pn (x) = Ei (x)f (i/n) i=0 where Ej (x) chosen as some polynomials peaks at x = i/n and then decaysaway from x = i/n. To this end, set set n i Ei (x) = P(Bin(n, x) = i) = x (1 − x)n−i for 0 ≤ i ≤ n. i For each x ∈ [0, 1], the binomial distribution Bin(n, x) has mean nx and variance nx(1 − x) ≤ n. By Chebyshev’s inequality, X Ei (x) = P(|Bin(n, x) − nx| > n2/3 ) ≤ n−1/3 . i:|i−nx|>n2/3 Since [0, 1] is compact, f is uniformly continuous and bounded. By rescaling, assume that |f (x)| ≤ 1 for all x ∈ [0, 1]. Also there exists δ > 0 such that |f (x) − f (y)| ≤ /2 for all x, y ∈ [0, 1] with |x − y| ≤ δ. Take n > max{64−3 , δ −3 }. Then for every x ∈ [0, 1] (note that |Pn (x) − f (x)| ≤ n X Pn j=0 Ej (x) = 1), Ei (x)|f (i/n) − f (x)| i=0 ≤ X Ei (x)|f (i/n) − f (x)| + i:|i/n−x|n2/3 2Ei (x)

Second Moment Method

Related Documents

Recommended Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock