{"id":7215,"date":"2013-12-16T11:20:53","date_gmt":"2013-12-16T19:20:53","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=7215"},"modified":"2026-09-30T09:16:06","modified_gmt":"2026-09-30T17:16:06","slug":"basic-bounds","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/probabilistic-method\/basic-bounds\/","title":{"rendered":"basic bounds"},"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>Existence proofs, the naive union bound, linearity of expectation, Markov bound.<\/em><\/center><\/p><\/blockquote>\n<p><!--more--><\/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=\"a0000000002\">Basic bounds<\/h1>\n<p> Here is the basic principle underlying the probabilistic method: <\/p>\n<div id=\"a0000000003\" class=\"my-theorem latex-paragraph latex-Thm\">\n<div class=\"latex-paragraph-heading\">   <b>Theorem 1<\/b> (existence).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Fix any random experiment. Let <script type=\"math\/tex;\">X<\/script> be any random variable and let <script type=\"math\/tex;\">\\mu =\\textrm{E}[X]<\/script>. Then there exists at least one outcome where <script type=\"math\/tex;\">X \\ge \\mu <\/script> (and at least one where <script type=\"math\/tex;\">X \\le \\mu <\/script>). <\/p>\n<\/div><\/div>\n<p>Here are three simple but fundamental bounds: <\/p>\n<div id=\"a0000000004\" class=\"my-theorem latex-paragraph latex-Thm\">\n<div class=\"latex-paragraph-heading\">   <b>Theorem 2<\/b> (naive union bound).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> For any two random events <script type=\"math\/tex;\">A<\/script> and <script type=\"math\/tex;\">B<\/script>,\u00a0\u00a0 <\/p>\n<div id=\"a0000000005\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\Pr [A\\text{ or } B] ~ \\le ~  \\Pr [A] + \\Pr [B]. <\/script><\/div>\n<p> For any <script type=\"math\/tex;\">n<\/script> random events <script type=\"math\/tex;\">A_1,A_2,\\ldots ,A_n<\/script>, <\/p>\n<div id=\"a0000000006\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\Pr [\\text{some } A_i \\text{ occurs}] ~ \\le ~  \\sum _i \\Pr [A_i]. <\/script><\/div>\n<\/div><\/div>\n<div id=\"a0000000007\" class=\"my-theorem latex-paragraph latex-Thm\">\n<div class=\"latex-paragraph-heading\">   <b>Theorem 3<\/b> (linearity of expectation).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> For any numeric random variables <script type=\"math\/tex;\">X,Y<\/script> and real constant <script type=\"math\/tex;\">c<\/script>, <\/p>\n<div id=\"a0000000008\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\textrm{E}[X+Y] ~ =~  \\textrm{E}[X]+\\textrm{E}[Y] ~ \\text{ and }~  \\textrm{E}[c X] ~ =~  c\\, \\textrm{E}[X]. <\/script><\/div>\n<\/div><\/div>\n<div id=\"a0000000009\" class=\"my-theorem latex-paragraph latex-Thm\">\n<div class=\"latex-paragraph-heading\">   <b>Theorem 4<\/b> (Markov bound).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> For any non-negative random variable <script type=\"math\/tex;\">X<\/script> and constant <script type=\"math\/tex;\">c\\gt 0<\/script>, <\/p>\n<div id=\"a0000000010\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\Pr [X\\ge {}c] ~ \\le ~  \\textrm{E}[X]\/c <\/script><\/div>\n<p> and, if <script type=\"math\/tex;\">E[X]\\gt 0<\/script>, then<a href=\"#a0000000011\" class=\"footnote\"><sup class=\"footnotemark\">1<\/sup><\/a> <\/p>\n<div id=\"a0000000012\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\Pr [X\\gt c] ~ \\lt ~  \\textrm{E}[X]\/c. <\/script><\/div>\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=\"a0000000013\">Related<\/h1>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000014\">Introductory textbooks on basic probability, available online<\/h2>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"https:\/\/www.google.com\/search?q=%22Notes+on+Discrete+Probability%22+trevisan\">Notes on Discrete Probability<\/a> \u2014 by Trevisan <\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/www.google.com\/search?q=%22Introduction+to+Probability%22+Grinstead+Snell+pdf\">Introduction to Probability<\/a> \u2014 by Grinstead and Snell (see Chapters 1, 4, 6) <\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/www.google.com\/search?q=%22Lecture+Notes+on+Probability+Theory+and+Random+Processes%22+Walrand+pdf\">Lecture Notes on Probability Theory and Random Processes<\/a> \u2014 by Walrand (see Chapters 1\u20136) <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000015\">On Wikipedia<\/h2>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Linearity_of_expectation\">Linearity of expectation<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Markov&#x27;s_inequality\">Markov\u2019s inequality<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Probabilistic_method\">Probabilistic method<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div><\/div>\n<\/div>\n<\/div>\n<\/div>\n<div id=\"footnotes\">\n<div>\n<h2>Footnotes<\/h2>\n<ol>\n<li id=\"a0000000011\">Here is a proof of the second claim in the Markov bound. <br \/>If <script type=\"math\/tex;\">\\Pr [X\\gt c]=0<\/script>, we\u2019re done, so assume <script type=\"math\/tex;\">\\Pr [X\\gt c]\\gt 0<\/script>. <br \/>Then <script type=\"math\/tex;\">\\textrm{E}[X] \\ge \\Pr [X \\gt c] \\textrm{E}[X \\, |\\, X \\gt c] \\gt \\Pr [X \\gt c]\\,  c<\/script> so <script type=\"math\/tex;\">\\textrm{E}[x]\/c \\gt \\Pr [X \\gt c]<\/script>.<\/li>\n<\/ol><\/div>\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Existence proofs, the naive union bound, linearity of expectation, Markov bound.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":901,"menu_order":1,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-7215","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/7215","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=7215"}],"version-history":[{"count":3,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/7215\/revisions"}],"predecessor-version":[{"id":9027,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/7215\/revisions\/9027"}],"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=7215"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}