imported>Etone |
imported>Etone |
| Line 1: |
Line 1: |
| = Erdős–Rényi Random Graphs = | | *<font color="red" size=4>每道题目的解答都要有完整的解题过程。中英文不限。</font> |
| Consider a graph <math>G(V,E)</math> which is randomly generated as:
| | *<font color="red" size=5>这次作业只有一星期的时间。</font> |
| * <math>|V|=n</math>; | |
| * <math>\forall \{u,v\}\in{V\choose 2}</math>, <math>uv\in E</math> independently with probability <math>p</math>.
| |
|
| |
|
| Such graph is denoted as '''<math>G(n,p)</math>'''. This is called the '''Erdős–Rényi model''' or '''<math>G(n,p)</math> model''' for random graphs.
| | == Problem 1== |
| | Prove the following identity: |
| | *<math>\sum_{k=1}^n k{n\choose k}= n2^{n-1}</math>. |
|
| |
|
| Informally, the presence of every edge of <math>G(n,p)</math> is determined by an independent coin flipping (with probability of HEADs <math>p</math>).
| | (Hint: Use double counting.) |
|
| |
|
| ==Monotone properties == | | == Problem 2 == |
| A graph property is a predicate of graph which depends only on the structure of the graph.
| | Show that among any group of <math>n</math> people, where <math>n\ge 2</math>, there are at least two people who know exactly the same number of people in the group (assuming that "knowing" is a symmetric relation). |
| {{Theorem|Definition|
| |
| :Let <math>\mathcal{G}_n=2^{V\choose 2}</math>, where <math>|V|=n</math>, be the set of all possible graphs on <math>n</math> vertices. A '''graph property''' is a boolean function <math>P:\mathcal{G}_n\rightarrow\{0,1\}</math> which is invariant under permutation of vertices, i.e. <math>P(G)=P(H)</math> whenever <math>G</math> is isomorphic to <math>H</math>.
| |
| }}
| |
|
| |
|
| We are interested in the monotone properties, i.e., those properties that adding edges will not change a graph from having the property to not having the property.
| | == Problem 3 == |
| {{Theorem|Definition|
| | Let <math>S</math> be a subset of <math>\{1,2,\ldots,2n\}</math> such that <math>|S|>n</math>. Show that there exist <math>a,b\in S</math> such that <math>a</math> and <math>b</math> are coprime. |
| :A graph property <math>P</math> is '''monotone''' if for any <math>G\subseteq H</math>, both on <math>n</math> vertices, <math>G</math> having property <math>P</math> implies <math>H</math> having property <math>P</math>.
| |
| }}
| |
| By seeing the property as a function mapping a set of edges to a numerical value in <math>\{0,1\}</math>, a monotone property is just a monotonically increasing set function.
| |
|
| |
|
| Some examples of monotone graph properties:
| | == Problem 4 == |
| * Hamiltonian;
| | (Due to Karger) |
| * <math>k</math>-clique;
| |
| * contains a subgraph isomorphic to some <math>H</math>;
| |
| * non-planar;
| |
| * chromatic number <math>>k</math> (i.e., not <math>k</math>-colorable);
| |
| * girth <math><\ell</math>.
| |
| From the last two properties, you can see another reason that the Erdős theorem is unintuitive.
| |
|
| |
|
| Some examples of '''non-'''monotone graph properties:
| | Balls of 8 different colors are in 6 bins. There are 20 balls of each color. Prove that there must be a bin containing 2 pairs of balls from the two different colors of balls. |
| * Eulerian;
| |
| * contains an ''induced'' subgraph isomorphic to some <math>H</math>;
| |
|
| |
|
| For all monotone graph properties, we have the following theorem.
| | == Problem 5 == |
| {{Theorem|Theorem|
| | (Erdős-spencer 1974) |
| :Let <math>P</math> be a monotone graph property. Suppose <math>G_1=G(n,p_1)</math>, <math>G_2=G(n,p_2)</math>, and <math>0\le p_1\le p_2\le 1</math>. Then
| |
| ::<math>\Pr[P(G_1)]\le \Pr[P(G_2)]</math>.
| |
| }}
| |
| Although the statement in the theorem looks very natural, it is difficult to evaluate the probability that a random graph has some property. However, the theorem can be very easily proved by using the idea of [http://en.wikipedia.org/wiki/Coupling_(probability) coupling], a proof technique in probability theory which compare two unrelated random variables by forcing them to be related.
| |
| {{Proof|
| |
| For any <math>\{u,v\}\in{[n]\choose 2}</math>, let <math>X_{\{u,v\}}</math> be independently and uniformly distributed over the continuous interval <math>[0,1]</math>. Let <math>uv\in G_1</math> if and only if <math>X_{\{u,v\}}\in[0,p_1]</math> and let <math>uv\in G_2</math> if and only if <math>X_{\{u,v\}}\in[0,p_2]</math>.
| |
|
| |
|
| It is obvious that <math>G_1\sim G(n,p_1)\,</math> and <math>G_2\sim G(n,p_2)\,</math>. For any <math>\{u,v\}</math>, <math>uv\in G_1</math> means that <math>X_{\{u,v\}}\in[0,p_1]\subseteq [0,p_2]</math>, which implies that <math>uv\in G_2</math>. Thus, <math>G_1\subseteq G_2</math>.
| | Let <math>n</math> coins of weights 0 and 1 be given. We are also given a scale with which we may weigh any subset of the coins. Our goal is to determine the weights of coins (i.e. which coins are 0 and which are 1) with the minimal number of weighings. |
|
| |
|
| Since <math>P</math> is monotone, <math>P(G_1)=1</math> implies <math>P(G_2)</math>. Thus,
| | This problem can be formalized as follows: A collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math> is called '''determining''' if an arbitrary subset <math>T\subseteq[n]</math> can be uniquely determined by the cardinalities <math>|S_i\cap T|, 1\le i\le m</math>. |
| :<math>\Pr[P(G_1)=1]\le \Pr[P(G_2)=1]</math>.
| |
| }}
| |
|
| |
|
| == Threshold phenomenon ==
| | * Prove that if there is a determining collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math>, then there is a way to determine the weights of <math>n</math> coins with <math>m</math> weighings. |
| One of the most fascinating phenomenon of random graphs is that for so many natural graph properties, the random graph <math>G(n,p)</math> suddenly changes from almost always not having the property to almost always having the property as <math>p</math> grows in a very small range.
| | * Use pigeonhole principle to show that if a collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math> is determining, then it must hold that <math>m\ge \frac{n}{\log_2(n+1)}</math>. |
|
| |
|
| A monotone graph property <math>P</math> is said to have the '''threshold''' <math>p(n)</math> if
| | (This gives a lower bound for the number of weighings required to determine the weights of coins.) |
| * when <math>p\ll p(n)</math>, <math>\Pr[P(G(n,p))]=0</math> as <math>n\rightarrow\infty</math> (also called <math>G(n,p)</math> almost always does not have <math>P</math>); and
| |
| * when <math>p\gg p(n)</math>, <math>\Pr[P(G(n,p))]=1</math> as <math>n\rightarrow\infty</math> (also called <math>G(n,p)</math> almost always has <math>P</math>).
| |
| | |
| The classic method for proving the threshold is the so-called second moment method (Chebyshev's inequality).
| |
| === Threshold for 4-clique ===
| |
| {{Theorem|Theorem|
| |
| :The threshold for a random graph <math>G(n,p)</math> to contain a 4-clique is <math>p=n^{2/3}</math>.
| |
| }}
| |
| We formulate the problem as such.
| |
| For any <math>4</math>-subset of vertices <math>S\in{V\choose 4}</math>, let <math>X_S</math> be the indicator random variable such that
| |
| :<math>
| |
| X_S=
| |
| \begin{cases}
| |
| 1 & S\mbox{ is a clique},\\
| |
| 0 & \mbox{otherwise}.
| |
| \end{cases}
| |
| </math>
| |
| Let <math>X=\sum_{S\in{V\choose 4}}X_S</math> be the total number of 4-cliques in <math>G</math>.
| |
| | |
| It is sufficient to prove the following lemma.
| |
| {{Theorem|Lemma|
| |
| *If <math>p=o(n^{-2/3})</math>, then <math>\Pr[X\ge 1]\rightarrow 0</math> as <math>n\rightarrow\infty</math>.
| |
| *If <math>p=\omega(n^{-2/3})</math>, then <math>\Pr[X\ge 1]\rightarrow 1</math> as <math>n\rightarrow\infty</math>.
| |
| }}
| |
| {{Proof|
| |
| The first claim is proved by the first moment (expectation and Markov's inequality) and the second claim is proved by the second moment method (Chebyshev's inequality).
| |
| | |
| Every 4-clique has 6 edges, thus for any <math>S\in{V\choose 4}</math>,
| |
| :<math>\mathbf{E}[X_S]=\Pr[X_S=1]=p^6</math>.
| |
| By the linearity of expectation,
| |
| :<math>\mathbf{E}[X]=\sum_{S\in{V\choose 4}}\mathbf{E}[X_S]={n\choose 4}p^6</math>.
| |
| Applying Markov's inequality
| |
| :<math>\Pr[X\ge 1]\le \mathbf{E}[X]=O(n^4p^6)=o(1)</math>, if <math>p=o(n^{-2/3})</math>.
| |
| The first claim is proved.
| |
| | |
| To prove the second claim, it is equivalent to show that <math>\Pr[X=0]=o(1)</math> if <math>p=\omega(n^{-2/3})</math>. By the Chebyshev's inequality,
| |
| :<math>\Pr[X=0]\le\Pr[|X-\mathbf{E}[X]|\ge\mathbf{E}[X]]\le\frac{\mathbf{Var}[X]}{(\mathbf{E}[X])^2}</math>,
| |
| where the variance is computed as
| |
| :<math>\mathbf{Var}[X]=\mathbf{Var}\left[\sum_{S\in{V\choose 4}}X_S\right]=\sum_{S\in{V\choose 4}}\mathbf{Var}[X_S]+\sum_{S,T\in{V\choose 4}, S\neq T}\mathbf{Cov}(X_S,X_T)</math>.
| |
| For any <math>S\in{V\choose 4}</math>,
| |
| :<math>\mathbf{Var}[X_S]=\mathbf{E}[X_S^2]-\mathbf{E}[X_S]^2\le \mathbf{E}[X_S^2]=\mathbf{E}[X_S]=p^6</math>. Thus the first term of above formula is <math>\sum_{S\in{V\choose 4}}\mathbf{Var}[X_S]=O(n^4p^6)</math>.
| |
| | |
| We now compute the covariances. For any <math>S,T\in{V\choose 4}</math> that <math>S\neq T</math>:
| |
| * Case.1: <math>|S\cap T|\le 1</math>, so <math>S</math> and <math>T</math> do not share any edges. <math>X_S</math> and <math>X_T</math> are independent, thus <math>\mathbf{Cov}(X_S,X_T)=0</math>.
| |
| * Case.2: <math>|S\cap T|= 2</math>, so <math>S</math> and <math>T</math> share an edge. Since <math>|S\cup T|=6</math>, there are <math>{n\choose 6}=O(n^6)</math> pairs of such <math>S</math> and <math>T</math>.
| |
| ::<math>\mathbf{Cov}(X_S,X_T)=\mathbf{E}[X_SX_T]-\mathbf{E}[X_S]\mathbf{E}[X_T]\le\mathbf{E}[X_SX_T]=\Pr[X_S=1\wedge X_T=1]=p^{11}</math>
| |
| :since there are 11 edges in the union of two 4-cliques that share a common edge. The contribution of these pairs is <math>O(n^6p^{11})</math>.
| |
| * Case.2: <math>|S\cap T|= 3</math>, so <math>S</math> and <math>T</math> share a triangle. Since <math>|S\cup T|=5</math>, there are <math>{n\choose 5}=O(n^5)</math> pairs of such <math>S</math> and <math>T</math>. By the same argument,
| |
| ::<math>\mathbf{Cov}(X_S,X_T)\le\Pr[X_S=1\wedge X_T=1]=p^{9}</math>
| |
| :since there are 9 edges in the union of two 4-cliques that share a triangle. The contribution of these pairs is <math>O(n^5p^{9})</math>.
| |
| Putting all these together,
| |
| :<math>\mathbf{Var}[X]=O(n^4p^6+n^6p^{11}+n^5p^{9}).</math>
| |
| And
| |
| :<math>\Pr[X=0]\le\frac{\mathbf{Var}[X]}{(\mathbf{E}[X])^2}=O(n^{-4}p^{-6}+n^{-2}p^{-1}+n^{-3}p^{-3})</math>,
| |
| which is <math>o(1)</math> if <math>p=\omega(n^{-2/3})</math>. The second claim is also proved.
| |
| }}
| |
| | |
| === Threshold for balanced subgraphs ===
| |
| The above theorem can be generalized to any "balanced" subgraphs.
| |
| {{Theorem|Definition|
| |
| * The '''density''' of a graph <math>G(V,E)</math>, denoted <math>\rho(G)\,</math>, is defined as <math>\rho(G)=\frac{|E|}{|V|}</math>.
| |
| * A graph <math>G(V,E)</math> is '''balanced''' if <math>\rho(H)\le \rho(G)</math> for all subgraphs <math>H</math> of <math>G</math>.
| |
| }}
| |
| Cliques are balanced, because <math>\frac{{k\choose 2}}{k}\le \frac{{n\choose 2}}{n}</math> for any <math>k\le n</math>. The threshold for 4-clique is a direct corollary of the following general theorem.
| |
| | |
| {{Theorem|Theorem (Erdős–Rényi 1960)|
| |
| :Let <math>H</math> be a balanced graph with <math>k</math> vertices and <math>\ell</math> edges. The threshold for the property that a random graph <math>G(n,p)</math> contains a (not necessarily induced) subgraph isomorphic to <math>H</math> is <math>p=n^{-k/\ell}\,</math>.
| |
| }}
| |
| {{Prooftitle|Sketch of proof.|
| |
| For any <math>S\in{V\choose k}</math>, let <math>X_S</math> indicate whether <math>G_S</math> (the subgraph of <math>G</math> induced by <math>S</math>) contain a subgraph <math>H</math>. Then
| |
| :<math>p^{\ell}\le\mathbf{E}[X_S]\le k!p^{\ell}</math>, since there are at most <math>k!</math> ways to match the substructure.
| |
| Note that <math>k</math> does not depend on <math>n</math>. Thus, <math>\mathbf{E}[X_S]=\Theta(p^{\ell})</math>. Let <math>X=\sum_{S\in{V\choose k}}X_S</math> be the number of <math>H</math>-subgraphs.
| |
| :<math>\mathbf{E}[X]=\Theta(n^kp^{\ell})</math>.
| |
| | |
| By Markov's inequality, <math>\Pr[X\ge 1]\le \mathbf{E}[X]=\Theta(n^kp^{\ell})</math> which is <math>o(1)</math> when <math>p\ll n^{-\ell/k}</math>.
| |
| | |
| By Chebyshev's inequality, <math>\Pr[X=0]\le \frac{\mathbf{Var}[X]}{\mathbf{E}[X]^2}</math> where
| |
| :<math>\mathbf{Var}[X]=\sum_{S\in{V\choose k}}\mathbf{Var}[X_S]+\sum_{S\neq T}\mathbf{Cov}(X_S,X_T)</math>.
| |
| The first term <math>\sum_{S\in{V\choose k}}\mathbf{Var}[X_S]\le \sum_{S\in{V\choose k}}\mathbf{E}[X_S^2]= \sum_{S\in{V\choose k}}\mathbf{E}[X_S]=\mathbf{E}[X]=\Theta(n^kp^{\ell})</math>.
| |
| | |
| For the covariances, <math>\mathbf{Cov}(X_S,X_T)\neq 0</math> only if <math>|S\cap T|=i</math> for <math>2\le i\le k-1</math>. Note that <math>|S\cap T|=i</math> implies that <math>|S\cup T|=2k-i</math>. And for balanced <math>H</math>, the number of edges of interest in <math>S</math> and <math>T</math> is <math>2\ell-i\rho(H_{S\cap T})\ge 2\ell-i\rho(H)=2\ell-i\ell/k</math>. Thus, <math>\mathbf{Cov}(X_S,X_T)\le\mathbf{E}[X_SX_T]\le p^{2\ell-i\ell/k}</math>. And,
| |
| | |
| :<math>\sum_{S\neq T}\mathbf{Cov}(X_S,X_T)=\sum_{i=2}^{k-1}O(n^{2k-i}p^{2\ell-i\ell/k})</math>
| |
| Therefore, when <math>p\gg n^{-\ell/k}</math>,
| |
| :<math>
| |
| \Pr[X=0]\le \frac{\mathbf{Var}[X]}{\mathbf{E}[X]^2}\le \frac{\Theta(n^kp^{\ell})+\sum_{i=2}^{k-1}O(n^{2k-i}p^{2\ell-i\ell/k})}{\Theta(n^{2k}p^{2\ell})}=\Theta(n^{-k}p^{-\ell})+\sum_{i=2}^{k-1}O(n^{-i}p^{-i\ell/k})=o(1)</math>.
| |
| }}
| |
| | |
| | |
| =The Chernoff Bound=
| |
| | |
| Suppose that we have a fair coin. If we toss it once, then the outcome is completely unpredictable. But if we toss it, say for 1000 times, then the number of HEADs is very likely to be around 500. This striking phenomenon, illustrated in the right figure, is called the '''concentration'''. The Chernoff bound captures the concentration of independent trials.
| |
| | |
| [[File:Coinflip.png|border|450px|right]]
| |
| | |
| The Chernoff bound is also a tail bound for the sum of independent random variables which may give us ''exponentially'' sharp bounds.
| |
| | |
| Before proving the Chernoff bound, we should talk about the moment generating functions.
| |
| | |
| == Moment generating functions ==
| |
| The more we know about the moments of a random variable <math>X</math>, the more information we would have about <math>X</math>. There is a so-called '''moment generating function''', which "packs" all the information about the moments of <math>X</math> into one function.
| |
| | |
| {{Theorem
| |
| |Definition|
| |
| :The moment generating function of a random variable <math>X</math> is defined as <math>\mathbf{E}\left[\mathrm{e}^{\lambda X}\right]</math> where <math>\lambda</math> is the parameter of the function.
| |
| }}
| |
| | |
| By Taylor's expansion and the linearity of expectations,
| |
| :<math>\begin{align}
| |
| \mathbf{E}\left[\mathrm{e}^{\lambda X}\right]
| |
| &=
| |
| \mathbf{E}\left[\sum_{k=0}^\infty\frac{\lambda^k}{k!}X^k\right]\\
| |
| &=\sum_{k=0}^\infty\frac{\lambda^k}{k!}\mathbf{E}\left[X^k\right]
| |
| \end{align}</math>
| |
| | |
| The moment generating function <math>\mathbf{E}\left[\mathrm{e}^{\lambda X}\right]</math> is a function of <math>\lambda</math>.
| |
| | |
| == The Chernoff bound ==
| |
| The Chernoff bounds are exponentially sharp tail inequalities for the sum of independent trials.
| |
| The bounds are obtained by applying Markov's inequality to the moment generating function of the sum of independent trials, with some appropriate choice of the parameter <math>\lambda</math>.
| |
| {{Theorem
| |
| |Chernoff bound (the upper tail)|
| |
| :Let <math>X=\sum_{i=1}^n X_i</math>, where <math>X_1, X_2, \ldots, X_n</math> are independent Poisson trials. Let <math>\mu=\mathbf{E}[X]</math>.
| |
| :Then for any <math>\delta>0</math>,
| |
| ::<math>\Pr[X\ge (1+\delta)\mu]\le\left(\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\right)^{\mu}.</math>
| |
| }}
| |
| {{Proof| For any <math>\lambda>0</math>, <math>X\ge (1+\delta)\mu</math> is equivalent to that <math>e^{\lambda X}\ge e^{\lambda (1+\delta)\mu}</math>, thus
| |
| :<math>\begin{align}
| |
| \Pr[X\ge (1+\delta)\mu]
| |
| &=
| |
| \Pr\left[e^{\lambda X}\ge e^{\lambda (1+\delta)\mu}\right]\\
| |
| &\le
| |
| \frac{\mathbf{E}\left[e^{\lambda X}\right]}{e^{\lambda (1+\delta)\mu}},
| |
| \end{align}</math>
| |
| where the last step follows by Markov's inequality.
| |
| | |
| Computing the moment generating function <math>\mathbf{E}[e^{\lambda X}]</math>:
| |
| :<math>\begin{align}
| |
| \mathbf{E}\left[e^{\lambda X}\right]
| |
| &=
| |
| \mathbf{E}\left[e^{\lambda \sum_{i=1}^n X_i}\right]\\
| |
| &=
| |
| \mathbf{E}\left[\prod_{i=1}^n e^{\lambda X_i}\right]\\
| |
| &=
| |
| \prod_{i=1}^n \mathbf{E}\left[e^{\lambda X_i}\right].
| |
| & (\mbox{for independent random variables})
| |
| \end{align}</math>
| |
| | |
| Let <math>p_i=\Pr[X_i=1]</math> for <math>i=1,2,\ldots,n</math>. Then,
| |
| :<math>\mu=\mathbf{E}[X]=\mathbf{E}\left[\sum_{i=1}^n X_i\right]=\sum_{i=1}^n\mathbf{E}[X_i]=\sum_{i=1}^n p_i</math>.
| |
| | |
| We bound the moment generating function for each individual <math>X_i</math> as follows.
| |
| :<math>\begin{align}
| |
| \mathbf{E}\left[e^{\lambda X_i}\right]
| |
| &=
| |
| p_i\cdot e^{\lambda\cdot 1}+(1-p_i)\cdot e^{\lambda\cdot 0}\\
| |
| &=
| |
| 1+p_i(e^\lambda -1)\\
| |
| &\le
| |
| e^{p_i(e^\lambda-1)},
| |
| \end{align}</math>
| |
| where in the last step we apply the Taylor's expansion so that <math>e^y\ge 1+y</math> where <math>y=p_i(e^\lambda-1)\ge 0</math>. (By doing this, we can transform the product to the sum of <math>p_i</math>, which is <math>\mu</math>.)
| |
| | |
| Therefore,
| |
| :<math>\begin{align}
| |
| \mathbf{E}\left[e^{\lambda X}\right]
| |
| &=
| |
| \prod_{i=1}^n \mathbf{E}\left[e^{\lambda X_i}\right]\\
| |
| &\le
| |
| \prod_{i=1}^n e^{p_i(e^\lambda-1)}\\
| |
| &=
| |
| \exp\left(\sum_{i=1}^n p_i(e^{\lambda}-1)\right)\\
| |
| &=
| |
| e^{(e^\lambda-1)\mu}.
| |
| \end{align}</math>
| |
| Thus, we have shown that for any <math>\lambda>0</math>,
| |
| :<math>\begin{align}
| |
| \Pr[X\ge (1+\delta)\mu]
| |
| &\le
| |
| \frac{\mathbf{E}\left[e^{\lambda X}\right]}{e^{\lambda (1+\delta)\mu}}\\
| |
| &\le
| |
| \frac{e^{(e^\lambda-1)\mu}}{e^{\lambda (1+\delta)\mu}}\\
| |
| &=
| |
| \left(\frac{e^{(e^\lambda-1)}}{e^{\lambda (1+\delta)}}\right)^\mu
| |
| \end{align}</math>.
| |
| For any <math>\delta>0</math>, we can let <math>\lambda=\ln(1+\delta)>0</math> to get
| |
| :<math>\Pr[X\ge (1+\delta)\mu]\le\left(\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\right)^{\mu}.</math>
| |
| }}
| |
| | |
| The idea of the proof is actually quite clear: we apply Markov's inequality to <math>e^{\lambda X}</math> and for the rest, we just estimate the moment generating function <math>\mathbf{E}[e^{\lambda X}]</math>. To make the bound as tight as possible, we minimized the <math>\frac{e^{(e^\lambda-1)}}{e^{\lambda (1+\delta)}}</math> by setting <math>\lambda=\ln(1+\delta)</math>, which can be justified by taking derivatives of <math>\frac{e^{(e^\lambda-1)}}{e^{\lambda (1+\delta)}}</math>.
| |
| | |
| ----
| |
| | |
| We then proceed to the lower tail, the probability that the random variable deviates below the mean value:
| |
| | |
| {{Theorem
| |
| |Chernoff bound (the lower tail)|
| |
| :Let <math>X=\sum_{i=1}^n X_i</math>, where <math>X_1, X_2, \ldots, X_n</math> are independent Poisson trials. Let <math>\mu=\mathbf{E}[X]</math>.
| |
| :Then for any <math>0<\delta<1</math>,
| |
| ::<math>\Pr[X\le (1-\delta)\mu]\le\left(\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\right)^{\mu}.</math>
| |
| }}
| |
| {{Proof| For any <math>\lambda<0</math>, by the same analysis as in the upper tail version,
| |
| :<math>\begin{align}
| |
| \Pr[X\le (1-\delta)\mu]
| |
| &=
| |
| \Pr\left[e^{\lambda X}\ge e^{\lambda (1-\delta)\mu}\right]\\
| |
| &\le
| |
| \frac{\mathbf{E}\left[e^{\lambda X}\right]}{e^{\lambda (1-\delta)\mu}}\\
| |
| &\le
| |
| \left(\frac{e^{(e^\lambda-1)}}{e^{\lambda (1-\delta)}}\right)^\mu.
| |
| \end{align}</math>
| |
| For any <math>0<\delta<1</math>, we can let <math>\lambda=\ln(1-\delta)<0</math> to get
| |
| :<math>\Pr[X\ge (1-\delta)\mu]\le\left(\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\right)^{\mu}.</math>
| |
| }}
| |
| | |
| ----
| |
| | |
| Some useful special forms of the bounds can be derived directly from the above general forms of the bounds. We now know better why we say that the bounds are exponentially sharp.
| |
| | |
| {{Theorem
| |
| |Useful forms of the Chernoff bound|
| |
| :Let <math>X=\sum_{i=1}^n X_i</math>, where <math>X_1, X_2, \ldots, X_n</math> are independent Poisson trials. Let <math>\mu=\mathbf{E}[X]</math>. Then
| |
| :1. for <math>0<\delta\le 1</math>,
| |
| ::<math>\Pr[X\ge (1+\delta)\mu]<\exp\left(-\frac{\mu\delta^2}{3}\right);</math>
| |
| ::<math>\Pr[X\le (1-\delta)\mu]<\exp\left(-\frac{\mu\delta^2}{2}\right);</math>
| |
| :2. for <math>t\ge 2e\mu</math>,
| |
| ::<math>\Pr[X\ge t]\le 2^{-t}.</math>
| |
| }}
| |
| {{Proof| To obtain the bounds in (1), we need to show that for <math>0<\delta< 1</math>, <math>\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\le e^{-\delta^2/3}</math> and <math>\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\le e^{-\delta^2/2}</math>. We can verify both inequalities by standard analysis techniques.
| |
| | |
| To obtain the bound in (2), let <math>t=(1+\delta)\mu</math>. Then <math>\delta=t/\mu-1\ge 2e-1</math>. Hence,
| |
| :<math>\begin{align}
| |
| \Pr[X\ge(1+\delta)\mu]
| |
| &\le
| |
| \left(\frac{e^\delta}{(1+\delta)^{(1+\delta)}}\right)^\mu\\
| |
| &\le
| |
| \left(\frac{e}{1+\delta}\right)^{(1+\delta)\mu}\\
| |
| &\le
| |
| \left(\frac{e}{2e}\right)^t\\
| |
| &\le
| |
| 2^{-t}
| |
| \end{align}</math>
| |
| }}
| |
| | |
| = Balls into bins, revisited =
| |
| Throwing <math>m</math> balls uniformly and independently to <math>n</math> bins, what is the maximum load of all bins with high probability? In the last class, we gave an analysis of this problem by using a counting argument.
| |
| | |
| Now we give a more "advanced" analysis by using Chernoff bounds.
| |
| | |
| | |
| For any <math>i\in[n]</math> and <math>j\in[m]</math>, let <math>X_{ij}</math> be the indicator variable for the event that ball <math>j</math> is thrown to bin <math>i</math>. Obviously
| |
| :<math>\mathbf{E}[X_{ij}]=\Pr[\mbox{ball }j\mbox{ is thrown to bin }i]=\frac{1}{n}</math>
| |
| Let <math>Y_i=\sum_{j\in[m]}X_{ij}</math> be the load of bin <math>i</math>.
| |
| | |
| | |
| Then the expected load of bin <math>i</math> is
| |
| | |
| <math>(*)\qquad \mu=\mathbf{E}[Y_i]=\mathbf{E}\left[\sum_{j\in[m]}X_{ij}\right]=\sum_{j\in[m]}\mathbf{E}[X_{ij}]=m/n. </math>
| |
| | |
| For the case <math>m=n</math>, it holds that <math>\mu=1</math>
| |
| | |
| Note that <math>Y_i</math> is a sum of <math>m</math> mutually independent indicator variable. Applying Chernoff bound, for any particular bin <math>i\in[n]</math>,
| |
| :<math>
| |
| \Pr[Y_i>(1+\delta)\mu] \le \left(\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\right)^\mu.
| |
| </math>
| |
| | |
| == When <math>m=n</math> ==
| |
| | |
| When <math>m=n</math>, <math>\mu=1</math>. Write <math>c=1+\delta</math>. The above bound can be written as
| |
| :<math>
| |
| \Pr[Y_i>c] \le \frac{e^{c-1}}{c^c}.
| |
| </math>
| |
| | |
| Let <math>c=\frac{e\ln n}{\ln\ln n}</math>, we evaluate <math>\frac{e^{c-1}}{c^c}</math> by taking logarithm to its reciprocal.
| |
| :<math>
| |
| \begin{align}
| |
| \ln\left(\frac{c^c}{e^{c-1}}\right)
| |
| &=
| |
| c\ln c-c+1\\
| |
| &=
| |
| c(\ln c-1)+1\\
| |
| &=
| |
| \frac{e\ln n}{\ln\ln n}\left(\ln\ln n-\ln\ln\ln n\right)+1\\
| |
| &\ge
| |
| \frac{e\ln n}{\ln\ln n}\cdot\frac{2}{e}\ln\ln n+1\\
| |
| &\ge
| |
| 2\ln n.
| |
| \end{align}
| |
| </math>
| |
| Thus,
| |
| :<math>
| |
| \Pr\left[Y_i>\frac{e\ln n}{\ln\ln n}\right] \le \frac{1}{n^2}.
| |
| </math>
| |
| | |
| Applying the union bound, the probability that there exists a bin with load <math>>12\ln n</math> is
| |
| :<math>n\cdot \Pr\left[Y_1>\frac{e\ln n}{\ln\ln n}\right] \le \frac{1}{n}</math>.
| |
| Therefore, for <math>m=n</math>, with high probability, the maximum load is <math>O\left(\frac{e\ln n}{\ln\ln n}\right)</math>.
| |
| | |
| == For larger <math>m</math> ==
| |
| When <math>m\ge n\ln n</math>, then according to <math>(*)</math>, <math>\mu=\frac{m}{n}\ge \ln n</math>
| |
| | |
| We can apply an easier form of the Chernoff bounds,
| |
| :<math>
| |
| \Pr[Y_i\ge 2e\mu]\le 2^{-2e\mu}\le 2^{-2e\ln n}<\frac{1}{n^2}.
| |
| </math>
| |
| By the union bound, the probability that there exists a bin with load <math>\ge 2e\frac{m}{n}</math> is,
| |
| :<math>n\cdot \Pr\left[Y_1>2e\frac{m}{n}\right] = n\cdot \Pr\left[Y_1>2e\mu\right]\le \frac{1}{n}</math>.
| |
| Therefore, for <math>m\ge n\ln n</math>, with high probability, the maximum load is <math>O\left(\frac{m}{n}\right)</math>.
| |