{"id":5730,"date":"2013-11-24T23:30:42","date_gmt":"2013-11-25T07:30:42","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=5730"},"modified":"2026-09-30T09:16:16","modified_gmt":"2026-09-30T17:16:16","slug":"expected-deviation","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/stopping-times\/expected-deviation\/","title":{"rendered":"Expected deviation of a sum"},"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>Bounds on the expected deviation of a sum from a threshold.<\/em><\/center><\/p><\/blockquote>\n<p>  Here are bounds on the expected deviation of a sum of 0\/1-random variables above or below some threshold (typically near its mean). <\/p>\n<p>For example, suppose Alice flips a fair coin <script type=\"math\/tex;\">n<\/script> times. She pays Bob $1 for each head after the first <script type=\"math\/tex;\">(1+\\varepsilon )n\/2<\/script> heads (if any). What is her expected payment to Bob? The bounds here say: at most <script type=\"math\/tex;\">\\varepsilon ^{-1} \\exp (-\\varepsilon ^2 n\/6)<\/script>. For example, if <script type=\"math\/tex;\">\\varepsilon =\\Omega (1\/\\sqrt n)<\/script>, the expected payment is <script type=\"math\/tex;\">O(\\sqrt n)<\/script>. If <script type=\"math\/tex;\">\\varepsilon =\\sqrt{6c\\ln (n)\/n}<\/script>, the expected payment is <script type=\"math\/tex;\">O(1\\, \/\\, n^{c-1}\\sqrt{\\ln n})<\/script>. In general the expectation is about <script type=\"math\/tex;\">\\varepsilon ^{-1}<\/script> times the probability (according to Chernoff) that the sum exceeds its mean by a factor of <script type=\"math\/tex;\">1+\\varepsilon <\/script>.<!--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-proof\">Standard Chernoff bounds<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/stopping-time-chernoff\">stopping-time Chernoff bounds<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/walds\">Stopping times and Wald\u2019s equation<\/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\">Sums with a fixed number of terms<\/h1>\n<p>First, bounds that are directly analogous to standard Chernoff bounds: <\/p>\n<div id=\"a0000000004\" class=\"my-theorem latex-paragraph latex-Lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma 1<\/b> (expected deviation from threshold).  <\/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;\">\\textrm{E}[\\max \\{ 0, Y - (1+\\varepsilon )\\mu T\\} ] \\, \\lt \\,  \\varepsilon ^{-1}\\, \\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;\">\\textrm{E}[\\max \\{ 0, (1-\\varepsilon )\\mu T - Y\\} ] \\, \\lt \\,  \\varepsilon ^{-1}\\, \\exp ({-\\varepsilon ^2}\\mu T\/2).<\/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=\"a0000000005\">Proof of Lemma\u00a01<\/h1>\n<div id=\"a0000000006\" 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><em>(a)<\/em> Using<a href=\"#a0000000007\" class=\"footnote\"><sup class=\"footnotemark\">1<\/sup><\/a> <script type=\"math\/tex;\">\\max \\{ 0,z\\} \\le \\varepsilon ^{-1} (1+\\varepsilon )^z<\/script>, then following <a href=\"http:\/\/algnotes.info\/on\/chernoff-proof\">the proof of the Chernoff bound<\/a>, the expectation in question is at most <\/p>\n<div id=\"eqn\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{eqn} \\textrm{E}\\left[\\frac{\\varepsilon ^{-1}\\,  (1+\\varepsilon )^Y}{(1+\\varepsilon )^{(1+\\varepsilon )\\mu T}}\\right] ~ \\le ~  \\varepsilon ^{-1} \\Big( \\frac{e^{\\varepsilon }}{(1+\\varepsilon )^{1+\\varepsilon }} \\Big)^{\\mu T} ~ \\lt ~  \\varepsilon ^{-1} \\exp (-\\varepsilon ^2 \\mu T\/3). \\end{equation}<\/script><\/div>\n<p><em>(b)<\/em> Using<a href=\"#a0000000008\" class=\"footnote\"><sup class=\"footnotemark\">2<\/sup><\/a> <script type=\"math\/tex;\">\\max \\{ 0,z\\} \\le \\varepsilon ^{-1}(1-\\varepsilon )^{-z}<\/script>, then following the proof of the Chernoff bound, the expectation in question is at most <\/p>\n<div id=\"eqn2\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{eqn2} \\textrm{E}\\left[\\frac{\\varepsilon ^{-1}\\, (1-\\varepsilon )^Y}{(1-\\varepsilon )^{(1-\\varepsilon )\\mu T}}\\right] ~ \\le ~  \\varepsilon ^{-1} \\Big( \\frac{e^{-\\varepsilon }}{(1-\\varepsilon )^{1-\\varepsilon }} \\Big)^{\\mu T} ~ \\lt ~  \\varepsilon ^{-1} \\exp (-\\varepsilon ^2 \\mu T\/2). \\end{equation}<\/script><\/div>\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<h1 id=\"a0000000009\">Sums with randomly many terms<\/h1>\n<p>Assume a system goes through a random sequence of states <script type=\"math\/tex;\">S_1,S_2,\\ldots ,S_T<\/script>, where each state <script type=\"math\/tex;\">S_t<\/script> determines two values: <script type=\"math\/tex;\">x_t<\/script> and <script type=\"math\/tex;\">y_t<\/script>, each in <script type=\"math\/tex;\">[0,1]<\/script>, where the expectation of each <script type=\"math\/tex;\">x_t<\/script> is at most that of <script type=\"math\/tex;\">y_t<\/script>: <\/p>\n<div id=\"a0000000010\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\textrm{E}[x_t \\, |\\, S_{t-1}]~ \\le ~ \\textrm{E}[y_t \\, |\\, S_{t-1}]. <\/script><\/div>\n<p> Let <script type=\"math\/tex;\">X_t=\\sum _{i=1}^t x_i<\/script> and <script type=\"math\/tex;\">Y_t=\\sum _{i=1}^t y_i<\/script>. <\/p>\n<div id=\"a0000000011\" class=\"my-theorem latex-paragraph latex-Lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma 2<\/b> (expected deviation from threshold).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> For any stopping time <script type=\"math\/tex;\">T<\/script> with finite expectation, and any <script type=\"math\/tex;\">\\varepsilon ,\\mu \\gt 0<\/script> with <script type=\"math\/tex;\">\\varepsilon \\le 1<\/script>, if <script type=\"math\/tex;\">X_t - Y_t<\/script> is uniformly bounded from above (for all <script type=\"math\/tex;\">t\\lt T<\/script>, by some finite bound independent of the outcome of the experiment), then the expectation of <script type=\"math\/tex;\">\\textstyle \\max \\big\\{ \\, 0, ~ X_T\/(1+\\varepsilon ) ~ -~ Y_T\/(1-\\varepsilon ) ~ -~  \\varepsilon \\mu \\, \\big\\} <\/script> is at most <script type=\"math\/tex;\">\\varepsilon ^{-1}\\exp (-\\varepsilon ^2\\mu )<\/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=\"a0000000012\">Proof of Lemma\u00a02<\/h1>\n<div id=\"a0000000013\" 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>The proof is similar to that of Lemma 1, but following <a href=\"http:\/\/algnotes.info\/on\/stopping-time-chernoff\">the proof of stopping-time Chernoff<\/a>, instead of the proof of Chernoff. <\/p>\n<p>Using<a href=\"#a0000000014\" class=\"footnote\"><sup class=\"footnotemark\">3<\/sup><\/a> <script type=\"math\/tex;\">\\max \\{ 0,a-b-c\\} \\le \\varepsilon ^{-1}(1+\\varepsilon )^{(1+\\varepsilon )a}(1-\\varepsilon )^{(1-\\varepsilon )b}e^{-\\varepsilon c}<\/script> for <script type=\"math\/tex;\">a,b,c\\ge 0<\/script>, the expectation in question is at most <script type=\"math\/tex;\">\\textrm{E}[\\phi _T]<\/script> where <\/p>\n<div id=\"eqn3\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{eqn3} \\phi _t = \\varepsilon ^{-1}\\,  (1+\\varepsilon )^{X_t}(1-\\varepsilon )^{Y_t} e^{-\\varepsilon ^2\\mu }. \\end{equation}<\/script><\/div>\n<p> To finish, note that <script type=\"math\/tex;\">\\phi <\/script> is a super-martingale, and <script type=\"math\/tex;\">\\phi _t<\/script> is uniformly bounded from below (by 0) and from above (as <script type=\"math\/tex;\">(1+\\varepsilon )^{X_t}(1-\\varepsilon )^{Y_t} \\le \\exp (\\varepsilon (X_t-Y_t))<\/script> and <script type=\"math\/tex;\">X_t-Y_t<\/script> is uniformly bounded from above). Hence, by Walds, the expectation of <script type=\"math\/tex;\">\\phi _T<\/script> is at most <script type=\"math\/tex;\">\\phi _0 = \\varepsilon ^{-1}\\exp (-\\varepsilon ^2\\mu )<\/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<h1 id=\"a0000000015\">Related<\/h1>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/expected-maximum-sum\">Expected maximum deviation among many sums<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div><\/div>\n<\/div>\n<\/div>\n<\/div>\n<div id=\"footnotes\">\n<div>\n<h2>Footnotes<\/h2>\n<ol>\n<li id=\"a0000000007\"><script type=\"math\/tex;\">~  z\\le e^{z-1}<\/script> <script type=\"math\/tex;\">\\Rightarrow ~  \\alpha z \\le e^{\\alpha z}\/e<\/script> <script type=\"math\/tex;\">\\Rightarrow ~  z \\le e^{\\alpha z} \/ e\\alpha <\/script> <script type=\"math\/tex;\">\\Rightarrow ~  z \\le (1+\\varepsilon )^z \/ e\\ln (1+\\varepsilon )<\/script> <script type=\"math\/tex;\">\\Rightarrow ~  z \\le (1+\\varepsilon )^z \/ \\varepsilon <\/script>.<\/li>\n<li id=\"a0000000008\">WLOG <script type=\"math\/tex;\">z\\ge 0<\/script>. That and <script type=\"math\/tex;\">1+\\varepsilon \\lt 1\/(1-\\varepsilon )<\/script> and <script type=\"math\/tex;\">z\\le (1+\\varepsilon )^z\/\\varepsilon <\/script> imply <script type=\"math\/tex;\"> z \\le (1+\\varepsilon )^z \/ \\varepsilon \\lt (1-\\varepsilon )^{-z}\/\\varepsilon <\/script>.<\/li>\n<li id=\"a0000000014\">Using <script type=\"math\/tex;\">(1+\\varepsilon )^{1+\\varepsilon }(1-\\varepsilon )^{1-\\varepsilon } \\ge 1<\/script> and <script type=\"math\/tex;\">(1+\\varepsilon )^{1+\\varepsilon }e^{-\\varepsilon } \\ge 1<\/script>, reduce to case <script type=\"math\/tex;\">a=0<\/script> (trivial) or <script type=\"math\/tex;\">b=c=0<\/script> (follows from previous).<\/li>\n<\/ol><\/div>\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Bounds on the expected deviation of a sum from a threshold. Here are bounds on the expected deviation of a sum of 0\/1-random variables above or below some threshold (typically near its mean). For example, suppose Alice flips a fair coin times. She pays Bob $1 for each head after the first heads (if any). [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":5735,"menu_order":6,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-5730","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/5730","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=5730"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/5730\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/5735"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=5730"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}