{"id":1464,"date":"2010-04-10T10:31:38","date_gmt":"2010-04-10T18:31:38","guid":{"rendered":"http:\/\/greedyalgs.com\/blog\/?p=1464"},"modified":"2026-09-30T09:16:36","modified_gmt":"2026-09-30T17:16:36","slug":"chernoff","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/probabilistic-method\/chernoff\/","title":{"rendered":"Chernoff bound"},"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>A brief introduction to Chernoff bounds.<\/em><\/center><\/p><\/blockquote>\n<p> If you\u2019re already familiar with Chernoff bounds, you may prefer to <a href=\"http:\/\/algnotes.info\/on\/chernoff-proof\">skip directly to the statement and proof of a typical Chernoff bound.<\/a> <\/p>\n<p>Chernoff bounds (a.k.a.\u00a0tail bounds, Hoeffding\/Azuma\/Talagrand inequalities, the method of bounded differences, etc.\u00a0<span class=\"cite\">[<a href=\"#Chernoff52Measure\">1<\/a>, <a href=\"#Hoeffding63Probability\">2<\/a>]<\/span>) are used to bound the probability that some function (typically a sum) of many \u201csmall\u201d random variables falls in the tail of its distribution (far from its expectation).<!--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\/probabilistic-method\">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\">The distribution of a sum of \u201csmall\u201d random variables<\/h1>\n<p><span style=\"float:right;margin:0.8em;margin-right:-0.5in;\"> <img decoding=\"async\" src=\"http:\/\/algnotes.info\/b\/wp-content\/uploads\/2013\/03\/img-00015.png\" alt=\"\\includegraphics[type=pdf,ext=.pdf,read=.pdf,width=3.75in]{shared\/graphics\/chernoff}\" style=\"width:3.75in\" class=\"zoooom\" \/> <\/span> <\/p>\n<p>Let <script type=\"math\/tex;\">Y<\/script> be a sum of many small random variables. For example, imagine that <script type=\"math\/tex;\">Y<\/script> is the number of heads in <script type=\"math\/tex;\">n<\/script> coin flips. The figure shows the typical distribution of such a sum around its expectation <script type=\"math\/tex;\">\\mu <\/script>. For <script type=\"math\/tex;\">\\varepsilon \\in (0,1)<\/script>, the sum has probability about <script type=\"math\/tex;\">e^{-\\varepsilon ^2\\mu }<\/script> of deviating from <script type=\"math\/tex;\">\\mu <\/script> by more than a factor of <script type=\"math\/tex;\">1+\\varepsilon <\/script> (that is, an additive deviation of <script type=\"math\/tex;\">\\varepsilon \\mu <\/script>). <\/p>\n<p>For example (taking any <script type=\"math\/tex;\">\\varepsilon =\\Theta (1\/\\sqrt\\mu )<\/script>) the sum has constant probability of deviating from <script type=\"math\/tex;\">\\mu <\/script> by an additive <script type=\"math\/tex;\">\\Theta (\\sqrt\\mu )<\/script>. <\/p>\n<p>Or (taking <script type=\"math\/tex;\">\\varepsilon =\\Theta (\\sqrt{\\log (n)\/\\mu })<\/script>), the sum has probability <script type=\"math\/tex;\">n^{-\\Theta (1)}<\/script> of deviating from <script type=\"math\/tex;\">\\mu <\/script> by more than <script type=\"math\/tex;\">\\Theta (\\sqrt{ \\mu \\log n})<\/script>. <\/p>\n<p>A typical Chernoff bound quantifies this behavior. It says that the event that <script type=\"math\/tex;\">Y<\/script> exceeds <script type=\"math\/tex;\">1+\\epsilon <\/script> times its expectation <script type=\"math\/tex;\">\\mu <\/script> is rare: it happens with probability at most <script type=\"math\/tex;\">e^{-\\mu \\epsilon ^2\/2}<\/script>. (A similar bound holds for <script type=\"math\/tex;\">\\Pr [ Y \\le (1-\\epsilon )\\mu ]<\/script>.) <\/p>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000004\">Example applications<\/h1>\n<p>Here are a couple of examples using a Chernoff bound. <\/p>\n<div id=\"a0000000005\" class=\"my-theorem latex-paragraph latex-example\">\n<div class=\"latex-paragraph-heading\">   <b>Example <\/b> (balls in bins \/ max bin).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Throw <script type=\"math\/tex;\">6 n\\ln n<\/script> balls randomly into <script type=\"math\/tex;\">n<\/script> bins. Let <script type=\"math\/tex;\">Y<\/script> be the number of balls thrown into a given bin. Then <script type=\"math\/tex;\">Y<\/script> is a sum of <script type=\"math\/tex;\">6 n\\ln n<\/script> independent random <script type=\"math\/tex;\">\\{ 0,1\\} <\/script>-variables: <\/p>\n<div id=\"a0000000006\" class=\"equation\"><script type=\"math\/tex; mode=display\"> Y=\\sum _{t} [\\text{ball } t \\text{ goes in the first bin}]. <\/script><\/div>\n<p> The expectation of <script type=\"math\/tex;\">Y<\/script> is <script type=\"math\/tex;\">6\\ln n<\/script>. By the Chernoff bound, for any <script type=\"math\/tex;\">\\varepsilon \\in (0,1)<\/script>, <\/p>\n<div id=\"a0000000007\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\renewcommand{\\mathspread }{\\, \\, \\, }\\Pr [Y \\ge (1+\\varepsilon )\\mu ] {\\, \\, \\, {<}\\, \\, \\, }\\exp (- \\varepsilon ^2\\textrm{E}[Y]\/3 ){\\, \\, \\, {=}\\, \\, \\, }1\/n^{2\\varepsilon ^2}.  <\/script><\/div>\n<p> Taking <script type=\"math\/tex;\">\\varepsilon = 1<\/script> gives <script type=\"math\/tex;\">\\Pr [Y \\ge 12\\ln n] {\\, \\, \\, {<}\\, \\, \\, }1\/n^2<\/script> \u2014 the probability that a given bin receives at least <script type=\"math\/tex;\">12\\ln n<\/script> balls is less than <script type=\"math\/tex;\">1\/n^2<\/script>. <\/p>\n<p>The <a href=\"http:\/\/algnotes.info\/on\/probabilistic-method\">naive union bound<\/a> implies that the probability that <em>any<\/em> of the <script type=\"math\/tex;\">n<\/script> bins has more than <script type=\"math\/tex;\">12\\ln n<\/script> balls is at most <script type=\"math\/tex;\">1\/n<\/script>. <\/p>\n<\/div><\/div>\n<div id=\"a0000000008\" class=\"my-theorem latex-paragraph latex-exercise\">\n<div class=\"latex-paragraph-heading\">   <b>Exercise <\/b> (more balls in bins).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Show that if <script type=\"math\/tex;\">n^2<\/script> balls are thrown, then the probability that any bin has more than <script type=\"math\/tex;\">n+O(\\sqrt{n\\ln n})<\/script> balls is at most <script type=\"math\/tex;\">1\/n<\/script>. <\/p>\n<\/div><\/div>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000009\">Expectations of exponentials<\/h1>\n<p> The proof of the Chernoff bound for a sum <script type=\"math\/tex;\">Y<\/script> works by reasoning about the expectation of <script type=\"math\/tex;\">(1+\\varepsilon )^{Y}<\/script>. Here is some intuition for this approach. (For the full proof, <a href=\"http:\/\/algnotes.info\/on\/chernoff-proof\">go here<\/a>.) <\/p>\n<p>Recall <a href=\"http:\/\/algnotes.info\/on\/probabilistic-method\">the humble Markov bound<\/a>: <em>for any non-negative random variable <script type=\"math\/tex;\">X<\/script>, the probability that <script type=\"math\/tex;\">X<\/script> exceeds <script type=\"math\/tex;\">c<\/script> is at most <script type=\"math\/tex;\">E[X]\/c<\/script><\/em>. This is useful but somewhat weak. Can we strengthen it by transforming <script type=\"math\/tex;\">X<\/script>? <\/p>\n<p>To take a concrete example, let <script type=\"math\/tex;\">X_t<\/script> be the number of heads in <script type=\"math\/tex;\">t<\/script> random coin flips. Consider <script type=\"math\/tex;\">\\textrm{E}[3^{X_t}]<\/script>. By direct calculation, <\/p>\n<div id=\"a0000000010\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\renewcommand{\\mathspread }{\\, \\, \\, }\\textrm{E}\\big[3^{X_{t+1}} \\big] {\\, \\, \\, {=}\\, \\, \\, }{\\textstyle \\frac{1}{2}} \\textrm{E}[3^{X_t}] + {\\textstyle \\frac{1}{2}} 3 \\cdot \\textrm{E}[3^{X_t}] {\\, \\, \\, {=}\\, \\, \\, }2\\cdot \\textrm{E}[3^{X_t}].  <\/script><\/div>\n<p> By induction, <script type=\"math\/tex;\">\\textrm{E}[3^{X_t}] = 2^t<\/script>. <\/p>\n<p>Does this give anything useful? Applying the Markov bound to <script type=\"math\/tex;\">3^{X_t}<\/script> gives <\/p>\n<div id=\"a0000000011\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\renewcommand{\\mathspread }{\\, \\, \\, }\\Pr [X_t \\ge c] {\\, \\, \\, {=}\\, \\, \\, }\\Pr [3^{X_t} \\ge 3^c] {\\, \\, \\, {\\le }\\, \\, \\, }\\frac{\\textrm{E}[3^{X_t}]}{3^{c}} {\\, \\, \\, {=}\\, \\, \\, }\\frac{2^t}{3^{c}} \\approx 2^{t - 1.58\\, c}.  <\/script><\/div>\n<p> For example, taking <script type=\"math\/tex;\">t=100<\/script> and <script type=\"math\/tex;\">c=70<\/script>, we can conclude that the probability of getting <script type=\"math\/tex;\">70<\/script> or more heads in <script type=\"math\/tex;\">100<\/script> flips is at most about 5\/10000. Choosing a base other than 3 may give a better bound. <\/p>\n<p>The proof of the Chernoff bound generalizes this idea, and optimizes the base of the exponent. Typically, in order to bound the probability of deviating by a <script type=\"math\/tex;\">1+\\varepsilon <\/script> factor from the mean, the best base for the exponent is something like <script type=\"math\/tex;\">1+\\varepsilon \\approx e^\\varepsilon <\/script>. To prove bounds on deviations below (as opposed to above) the mean, one uses a base less than 1. For most settings, these bounds are tight up to small constant factors in the exponent. <\/p>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000012\">Related<\/h2>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/chernoff-proof\">Full statement and proof of a typical Chernoff bound<\/a> <\/p>\n<\/li>\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><a href=\"http:\/\/en.wikipedia.org\/wiki\/Chernoff_bound\">Chernoff bound<\/a> (wikipedia) <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Azuma%27s_inequality\">Azuma\u2019s inequality<\/a> (wikipedia) <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Binomial_distribution#Normal_approximation\">Binomial distribution<\/a> (wikipedia) <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Normal_distribution\">Normal distribution<\/a> (wikipedia) <\/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>A brief introduction to Chernoff bounds. If you\u2019re already familiar with Chernoff bounds, you may prefer to skip directly to the statement and proof of a typical Chernoff bound. Chernoff bounds (a.k.a.\u00a0tail bounds, Hoeffding\/Azuma\/Talagrand inequalities, the method of bounded differences, etc.\u00a0[1, 2]) are used to bound the probability that some function (typically a sum) of [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":901,"menu_order":5,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1464","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/1464","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=1464"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/1464\/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=1464"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}