{"id":3451,"date":"2010-04-12T10:37:38","date_gmt":"2010-04-12T18:37:38","guid":{"rendered":"http:\/\/algnotes.info\/b\/?p=3451"},"modified":"2026-09-30T09:16:33","modified_gmt":"2026-09-30T17:16:33","slug":"chernoff-proof","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/probabilistic-method\/chernoff-proof\/","title":{"rendered":"Chernoff bound proof"},"content":{"rendered":"<div class=\"latex-file\">\n<div class=\"latex-document\">\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<blockquote class=\"quote\"><p><center><em>The statement and proof of a typical Chernoff bound.<\/em><\/center><\/p><\/blockquote>\n<p> \u00a0\u00a0<!--more--><\/p>\n<p><div style=\"margin:0pt;padding:0pt;margin-bottom:12px\"><\/div>\n<\/p>\n<hr \/>\n<div class=\"expandable\" id=\"a0000000002\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for background material\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for background material\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/chernoff\">a gentle introduction to Chernoff bounds<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/probabilistic-method\">the Markov bound<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/details>\n<\/div>\n<hr \/>\n<\/p>\n<\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000003\">A Chernoff bound, and proof<\/h1>\n<div id=\"a0000000004\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma <\/b> (Chernoff bound\u00a0<span class=\"cite\">[<a href=\"#Chernoff52Measure\">1<\/a>, <a href=\"#Hoeffding63Probability\">2<\/a>]<\/span>).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>Let <script type=\"math\/tex;\">Y=\\sum _{t=1}^T y_t<\/script> be a sum of independent random variables, where each <script type=\"math\/tex;\">y_t<\/script> is in <script type=\"math\/tex;\">[0,1]<\/script> and <script type=\"math\/tex;\">T\\gt 0<\/script> is fixed. Let <script type=\"math\/tex;\">\\varepsilon , \\mu \\gt 0<\/script> with <script type=\"math\/tex;\">\\varepsilon \\le 1<\/script>. <\/p>\n<p>(a) If <script type=\"math\/tex;\">\\textrm{E}[y_{t}] \\le \\mu <\/script> for all <script type=\"math\/tex;\">t\\le T<\/script> then <script type=\"math\/tex;\">\\Pr [Y \\ge (1+\\varepsilon )\\mu T] \\, \\lt \\,  \\exp ({-\\varepsilon ^2}\\mu T\/3).<\/script> <\/p>\n<p>(b) If <script type=\"math\/tex;\">\\textrm{E}[y_{t}] \\ge \\mu <\/script> for all <script type=\"math\/tex;\">t\\le T<\/script> then <script type=\"math\/tex;\">\\Pr [Y \\le (1-\\varepsilon )\\mu T] \\, \\lt \\,  \\exp ({-\\varepsilon ^2}\\mu T\/2).<\/script> <\/p>\n<\/div><\/div>\n<div id=\"a0000000005\" class=\"latex-paragraph latex-proof\">\n<div class=\"latex-paragraph-heading\">  <b>Proof. <\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>Here is a proof for part (a). <\/p>\n<div id=\"eqn\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{eqn} \\Pr [ Y \\ge (1+\\varepsilon )\\mu T] ~ =~  \\Pr \\Big[ (1+\\varepsilon )^Y \\ge (1+\\varepsilon )^{(1+\\varepsilon )\\mu T}\\Big] ~ \\le ~  \\frac{\\textrm{E}[ (1+\\varepsilon )^Y ]}{(1+\\varepsilon )^{(1+\\varepsilon )\\mu T}}. \\end{equation}<\/script><\/div>\n<p> (The inequality above follows from <a href=\"http:\/\/algnotes.info\/on\/probabilistic-method\">the Markov bound<\/a>.) <\/p>\n<p>Next we bound the above expectation. The independence of the <script type=\"math\/tex;\">y_t<\/script>\u2019s implies <\/p>\n<div id=\"a0000000006\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\textrm{E}\\big[ (1+\\varepsilon )^Y \\big] ~ =~  \\prod _{t=1}^T \\textrm{E}[ (1+\\varepsilon )^{y_t} ] ~ \\le ~  \\prod _{t=1}^T \\textrm{E}[ 1+\\varepsilon y_t ] ~ \\le ~  \\prod _{t=1}^T 1+\\varepsilon \\mu ~ \\lt ~  e^{\\varepsilon \\mu T}.  <\/script><\/div>\n<p> (The second step uses the convexity of <script type=\"math\/tex;\">(1+\\varepsilon )^z<\/script> as a function of <script type=\"math\/tex;\">z<\/script>, specifically, <script type=\"math\/tex;\">(1+\\varepsilon )^z \\le 1+\\varepsilon z<\/script> for <script type=\"math\/tex;\">z\\in [0,1]<\/script>. The third step uses <script type=\"math\/tex;\">\\textrm{E}[y_t] \\le \\mu <\/script>. The fourth step uses <script type=\"math\/tex;\">1+z\\lt e^z<\/script> for <script type=\"math\/tex;\">z\\ne 0<\/script>.) <\/p>\n<p>The rest is algebra. Combining the above bound with (\\ref{eqn}), the probability in question is less than <\/p>\n<div id=\"a0000000007\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\frac{e^{\\varepsilon \\mu T}}{(1+\\varepsilon )^{(1+\\varepsilon )\\mu T}} ~ =~  \\Big( \\frac{e^{\\varepsilon }}{(1+\\varepsilon )^{1+\\varepsilon }} \\Big)^{\\mu T} ~ \\lt ~  \\exp (-\\varepsilon ^2 \\mu T\/3).  <\/script><\/div>\n<p> (The last inequality follows from <script type=\"math\/tex;\">e^{\\varepsilon }\/(1+\\varepsilon )^{(1+\\varepsilon )} \\lt \\exp ({-\\varepsilon ^2}\/3)<\/script> for <script type=\"math\/tex;\">\\varepsilon \\in (0,1]<\/script>.) <\/p>\n<p>The proof for part (b) is similar \u2014 change the sign of <script type=\"math\/tex;\">\\varepsilon <\/script> throughout, and use <script type=\"math\/tex;\">e^{\\varepsilon }\/{(1-\\varepsilon )}^{(1-\\varepsilon )} \\lt \\exp ({-\\varepsilon ^2}\/2)<\/script>. <\/p>\n<\/div>\n<div style=\"float:right;border:1px solid #444;width:0.45em;height:0.45em\">\u00a0<\/div>\n<div style=\"clear:both\">\u00a0<\/div>\n<\/p><\/div>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<div id=\"a0000000008\" class=\"my-theorem latex-paragraph latex-exercise\">\n<div class=\"latex-paragraph-heading\">   <b \"=\"&quot;\">Exercise.<\/b>   <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>Prove part (b) of the Chernoff bound. <\/p>\n<\/div><\/div>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b>Remark: the proof needs only first-order (linear) approximations.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> The particular inequalities used in the proof above are elegant and convenient, but other inequalities could be used just as well. For example, we could change the base of the exponent in the proof from <script type=\"math\/tex;\">1+\\varepsilon <\/script> to <script type=\"math\/tex;\">\\exp (\\varepsilon )<\/script> and then push the proof through using inequalities such as <script type=\"math\/tex;\">\\exp (\\varepsilon ) \\le 1+\\varepsilon + \\varepsilon ^2<\/script>. The proof will work with any inequalities in which the first-order terms (for small <script type=\"math\/tex;\">\\varepsilon <\/script>) are tight, although the resulting bound may have a smaller constant in the exponent. <\/p>\n<\/div><\/div>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b>Remark: upper bounds when <script type=\"math\/tex;\">\\varepsilon <\/script> is large.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Sometimes one wants an upper bound on the probability of a large upper deviation: <script type=\"math\/tex;\">\\Pr [Y \\ge \\lambda \\mu T]<\/script> where <script type=\"math\/tex;\">\\lambda <\/script> is larger than 2. The proof above for part (a) applies up to the last step, showing an upper bound of <script type=\"math\/tex;\">(e\/\\lambda )^\\lambda \/e = \\exp (-\\lambda \\ln \\lambda + \\lambda - 1)<\/script>. For example, if you throw <script type=\"math\/tex;\">n<\/script> balls in <script type=\"math\/tex;\">n<\/script> bins, taking <script type=\"math\/tex;\">\\lambda = c\\ln (n)\/\\ln \\ln n<\/script> for some <script type=\"math\/tex;\">c<\/script>, the event that a given bin has more than <script type=\"math\/tex;\">c\\ln (n)\/\\ln \\ln n<\/script> balls is less than <script type=\"math\/tex;\">n^{-\\Theta (c)}<\/script>. <\/p>\n<\/div><\/div>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b>Pessimistic estimators.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> When the time comes to apply <a href=\"http:\/\/algnotes.info\/on\/method-of-conditional-probabilities\">the method of conditional probabilities<\/a> to an existence proof that uses the Chernoff bound, you\u2019ll need a pessimistic estimator for the bound. <\/p>\n<div class=\"expandable\" id=\"a0000000009\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click here for pessimistic estimator\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click here for pessimistic estimator\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p>Consider first the bound on <script type=\"math\/tex;\">\\Pr [ Y \\ge (1+\\varepsilon )\\mu T]<\/script>. Considering the proof of Chernoff carefully, the proof bounds this probability by the expectation of <\/p>\n<div id=\"a0000000010\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\phi ~ =~  \\frac{(1+\\varepsilon )^Y}{(1+\\varepsilon )^{(1+\\varepsilon )\\mu \\, T}} ~ =~  \\prod _{t=1}^T \\frac{(1+\\varepsilon )^{y_t}}{(1+\\varepsilon )^{(1+\\varepsilon )\\mu }}.  <\/script><\/div>\n<p> The proof shows the expectation is less than <script type=\"math\/tex;\">\\exp (-\\varepsilon ^2 T\/ 3)<\/script>. <\/p>\n<p>We consider that case when, for each <script type=\"math\/tex;\">t \\le T<\/script>, we need a bound on the conditional probability of the event <script type=\"math\/tex;\">Y \\ge (1+\\varepsilon )\\mu <\/script> given <script type=\"math\/tex;\">y_1,y_2,\\ldots ,y_t<\/script>. Following the proof, this conditional probability is at most the conditional expectation of <script type=\"math\/tex;\">\\phi <\/script>. <\/p>\n<p>The rest is just calculation. We calculate the conditional expectation of <script type=\"math\/tex;\">\\phi <\/script>, given <script type=\"math\/tex;\">y_1,y_2,\\ldots ,y_t<\/script>. The first <script type=\"math\/tex;\">t<\/script> terms in the product defining <script type=\"math\/tex;\">\\phi <\/script> are determined, while the rest are still independent of each other and the conditioning. Thus, the conditional expectation of <script type=\"math\/tex;\">\\phi <\/script> is <\/p>\n<div id=\"eqn:pess\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{eqn:pess} \\textrm{E}[\\phi ~ |~ y_1,y_2,\\ldots ,y_t] ~ \\le ~  \\prod _{s=1}^t \\frac{(1+\\varepsilon )^{y_s}}{(1+\\varepsilon )^{(1+\\varepsilon )\\mu }} \\times \\prod _{s=t+1}^T \\frac{1+\\varepsilon \\mu }{(1+\\varepsilon )^{(1+\\varepsilon )\\mu }}. \\end{equation}<\/script><\/div>\n<p> Let <script type=\"math\/tex;\">\\psi _t<\/script> denote the value of the expression on the right-hand side of \\eqref{eqn:pess}. Then <script type=\"math\/tex;\">\\psi _t<\/script> is one appropriate pessimistic estimator for the conditional probability of the event <script type=\"math\/tex;\">Y\\ge (1+\\varepsilon )\\mu <\/script>, given <script type=\"math\/tex;\">y_1,\\ldots ,y_t<\/script>. <\/p>\n<p><b class=\"bf\">Many pessimistic estimators are possible.<\/b> Recall that the proof of the Chernoff bound uses a sequence of inequalities. Essentially, for each term, the proof uses <\/p>\n<div id=\"a0000000011\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\textrm{E}[(1+\\varepsilon )^{y_t}] ~ \\le ~  \\textrm{E}[1+\\varepsilon y_t] ~ \\le ~  1+\\varepsilon \\mu ~ \\le ~  \\exp (\\varepsilon \\mu ) ~ \\le ~  \\frac{(1+\\varepsilon )^{(1+\\varepsilon )\\mu }}{\\exp (\\varepsilon ^2\\mu \/3)}.  <\/script><\/div>\n<p> (The last step on the right is implicit in the last step of the proof.) <\/p>\n<p>Correspondingly, one can modify <script type=\"math\/tex;\">\\psi _t<\/script> to get other valid pessimistic estimators: <\/p>\n<ul class=\"itemize\">\n<li>\n<p>Each term <script type=\"math\/tex;\">(1+\\varepsilon )^{y_s}<\/script> could be replaced by <script type=\"math\/tex;\">1+\\varepsilon y_s<\/script>. <\/p>\n<\/li>\n<li>\n<p>Each term <script type=\"math\/tex;\">1+\\varepsilon \\mu <\/script> could be replaced by <script type=\"math\/tex;\">\\exp (\\varepsilon \\mu )<\/script>. <\/p>\n<\/li>\n<li>\n<p>Each term <script type=\"math\/tex;\">\\frac{e^{\\varepsilon \\mu }}{(1+\\varepsilon )^{(1+\\varepsilon )\\mu }}<\/script> could be replaced by <script type=\"math\/tex;\">\\exp (-\\varepsilon ^2\\mu \/3)<\/script>. <\/p>\n<\/li>\n<li>\n<p>etc\u2026<\/p>\n<\/li>\n<\/ul>\n<p> In a sense <script type=\"math\/tex;\">\\psi _t<\/script> as defined above is the \u201cleast pessimistic\u201d (smallest) estimator. In comparison, I think the \u201cmost pessimistic\u201d (largest) turns out to be <\/p>\n<div id=\"a0000000012\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\prod _{s=1}^t \\frac{1+\\varepsilon y_s}{1+\\varepsilon \\mu } \\times \\exp (-\\varepsilon ^2\\mu T\/3).  <\/script><\/div>\n<p> The various modifications described above give pessimistic estimators between <script type=\"math\/tex;\">\\psi _t<\/script> and the one above. <\/p>\n<p><b class=\"bf\">Lower tail bound.<\/b> Next consider the bound on <script type=\"math\/tex;\">\\Pr [Y \\le (1-\\varepsilon )\\mu T]<\/script>. Given <script type=\"math\/tex;\">y_1,y_2,\\ldots ,y_t<\/script>, the conditional probability of the event <script type=\"math\/tex;\">Y \\le (1-\\varepsilon )\\mu T<\/script> is at most the pessimistic estimator <\/p>\n<div id=\"a0000000013\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\psi _t ~ =~  \\prod _{s=1}^t \\frac{(1-\\varepsilon )^{y_s}}{(1-\\varepsilon )^{(1-\\varepsilon )\\mu }} \\times \\prod _{s=t+1}^T \\frac{1-\\varepsilon \\mu }{(1-\\varepsilon )^{(1-\\varepsilon )\\mu }}.  <\/script><\/div>\n<p> As discussed above, many modifications are possible. For example, <script type=\"math\/tex;\">(1-\\varepsilon )^{y_s}<\/script> could be replaced by <script type=\"math\/tex;\">1-\\varepsilon y_s<\/script>, and so on, to obtain a more convenient form for a given application. <\/p>\n<p><b class=\"bf\">Bounding the increase with each step.<\/b> Generally, the <script type=\"math\/tex;\">t<\/script>th step of an algorithm will determine <script type=\"math\/tex;\">y_t<\/script>. To make sure the algorithm\u2019s action in the <script type=\"math\/tex;\">t<\/script>th step keeps the overall pessimistic estimator from increasing, we\u2019ll need a bound on the value of <script type=\"math\/tex;\">\\phi _t<\/script> relative to <script type=\"math\/tex;\">\\phi _{t-1}<\/script>. We will almost always prefer a bound such as the following <\/p>\n<div id=\"a0000000014\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\phi _t~  \\le ~  \\frac{1+\\varepsilon y_t}{1+\\varepsilon \\mu } \\phi _{t-1},  <\/script><\/div>\n<p> which is <em>linear<\/em> in <script type=\"math\/tex;\">y_t<\/script>. Essentially the same bound works for all the variants of <script type=\"math\/tex;\">\\phi _t<\/script> described above. <\/p>\n<div id=\"a0000000015\" class=\"my-theorem latex-paragraph latex-example\">\n<div class=\"latex-paragraph-heading\">   <b>Example <\/b> (conditioned balls in bins).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Suppose that <script type=\"math\/tex;\">T<\/script> balls are thrown into <script type=\"math\/tex;\">n<\/script> bins. Let <script type=\"math\/tex;\">Y<\/script> be the number of balls landing in the first bin, so <script type=\"math\/tex;\">\\textrm{E}[Y] = T\/n<\/script>. According to the Chernoff bound, the probability that <script type=\"math\/tex;\">Y \\ge (1+\\varepsilon )T\/n<\/script> is less than <script type=\"math\/tex;\">\\exp (-\\varepsilon ^2T\/2n)<\/script>. Given that <script type=\"math\/tex;\">b<\/script> of the first <script type=\"math\/tex;\">t<\/script> balls thrown go into the first bin, the conditional probability is less than <script type=\"math\/tex;\">\\exp (-\\varepsilon ^2T\/2n) {(1+\\varepsilon )^{b}}\/{(1+\\varepsilon \/n)^{t}}.<\/script> <\/p>\n<\/div><\/div>\n<\/div>\n<\/details>\n<\/div>\n<\/div><\/div>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000016\">Related<\/h2>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/obliv\">Using randomized rounding to derive Lagrangian-relaxation algorithms<\/a> <\/p>\n<\/li>\n<li>\n<p>On Wikipedia: <a href=\"http:\/\/en.wikipedia.org\/wiki\/Chernoff_bound\">Chernoff bound<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Azuma%27s_inequality\">Azuma\u2019s inequality<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Binomial_distribution#Normal_approximation\">binomial distribution<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<div>\n<h1 id=\"bibliography\">Bibliography<\/h1>\n<table class=\"bibliography\" cellspacing=\"0\" cellpadding=\"2\">\n<tr>\n<td valign=\"top\">[<a name=\"Chernoff52Measure\">1<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;H+Chernoff&quot;+intitle:&quot;+A+measure+of+asymptotic+efficiency+for+tests+of+a+hypothesis+based+on+the+sum+of+observations&quot;\">H.\u00a0Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. <em>Annals of Math. Stat.<\/em>, 23:493\u2013509, 1952. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Hoeffding63Probability\">2<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;W+Hoeffding&quot;+intitle:&quot;+Probability+inequalities+for+sums+of+bounded+random+variables&quot;\">W.\u00a0Hoeffding. Probability inequalities for sums of bounded random variables. <em>American Statistical Journal<\/em>, pages 13\u201330, Mar. 1963. <\/a><\/td>\n<\/tr>\n<\/table><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>The statement and proof of a typical Chernoff bound. \u00a0\u00a0<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":901,"menu_order":6,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-3451","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/3451","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/comments?post=3451"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/3451\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/901"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=3451"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}