{"id":3998,"date":"2010-05-06T21:53:44","date_gmt":"2010-05-07T05:53:44","guid":{"rendered":"http:\/\/algnotes.info\/b\/?p=3998"},"modified":"2026-09-30T09:16:20","modified_gmt":"2026-09-30T17:16:20","slug":"stopping-time-chernoff","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/stopping-times\/stopping-time-chernoff\/","title":{"rendered":"\u201cStopping-time\u201d Chernoff 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>Extending the Chernoff bound to handle sums with randomly many terms.<\/em><\/center><\/p><\/blockquote>\n<p>  Alice goes to the casino and plays bets on a sequence of fair coin flips. On the <script type=\"math\/tex;\">t<\/script>th bet, Alice chooses an amount <script type=\"math\/tex;\">a_t\\in [0,1]<\/script> to bet: she wins <script type=\"math\/tex;\">a_t<\/script> if this flip is heads, otherwise she loses <script type=\"math\/tex;\">a_t<\/script>. Since it\u2019s Vegas, she never stops playing. Fix any <script type=\"math\/tex;\">\\varepsilon \\gt 0<\/script>. Let <script type=\"math\/tex;\">W_t<\/script> be the sum of bets won after the <script type=\"math\/tex;\">t<\/script>th bet. Let <script type=\"math\/tex;\">L_t<\/script> be the sum of bets lost after the <script type=\"math\/tex;\">t<\/script>th bet. Will Alice ever reach a time <script type=\"math\/tex;\">t<\/script> such that <script type=\"math\/tex;\">W_t\/(1+\\varepsilon ) - L_t\/(1-\\varepsilon ) \\ge \\varepsilon \\mu <\/script>? The bound below says that the probability that she does is less than <script type=\"math\/tex;\">\\exp (-\\varepsilon ^2\\mu )<\/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\/walds\">Stopping times and Wald\u2019s equation<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/markov-for-supermartingales\">Markov for stopping time<\/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\">\u201cStopping-time\u201d Chernoff bound<\/h1>\n<p> The bound applies to a system that goes through a random sequence of states <script type=\"math\/tex;\">S_1,S_2,S_3,\\ldots <\/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 <script type=\"math\/tex;\">x_t<\/script> is at most that of <script type=\"math\/tex;\">y_t<\/script>: <\/p>\n<div id=\"a0000000004\" 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> The bound shows that <script type=\"math\/tex;\">\\sum _{t=1}^T x_t<\/script> is unlikely to ever significantly exceed <script type=\"math\/tex;\">\\sum _{t=1}^T y_t<\/script> (for any <script type=\"math\/tex;\">T<\/script>). <\/p>\n<div id=\"a0000000005\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma <\/b> (stopping-time Chernoff).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Given the conditions above, let <script type=\"math\/tex;\">\\varepsilon ,\\mu \\gt 0<\/script> with <script type=\"math\/tex;\">\\varepsilon \\le 1<\/script>. The probability that <\/p>\n<div id=\"event2\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{event2} \\textstyle \\exists t.~ ~  \\sum _{s=1}^t x_s\/(1+\\varepsilon ) ~ -~  \\sum _{s=1}^t y_s\/(1-\\varepsilon ) ~ \\ge ~  \\varepsilon \\mu \\end{equation}<\/script><\/div>\n<p> is less than <script type=\"math\/tex;\">\\exp (-\\varepsilon ^2\\mu )<\/script>. <\/p>\n<\/div><\/div>\n<p> (Various bounds of this kind are possible. The constants in this bound are not optimized.) <\/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=\"a0000000006\">Proof<\/h1>\n<p>The proof adapts the standard Chernoff proof. <\/p>\n<div class=\"expandable\" id=\"a0000000007\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for proof\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for proof\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p> Define <script type=\"math\/tex;\"> \\phi _t ~ =~  (1+\\varepsilon )^{\\sum _{s=1}^t x_s}(1-\\varepsilon )^{\\sum _{s=1}^t y_s}e^{-\\varepsilon ^2\\mu }. <\/script> <\/p>\n<p>If\u00a0\\eqref{event2} happens for some <script type=\"math\/tex;\">t<\/script>, then by calculation<a href=\"#a0000000008\" class=\"footnote\"><sup class=\"footnotemark\">1<\/sup><\/a> <script type=\"math\/tex;\"> \\phi _t <\/script> exceeds 1. To finish, we observe that <script type=\"math\/tex;\">\\phi <\/script> is a non-negative super-martingale. This proves the lemma, because then, by <a href=\"http:\/\/algnotes.info\/on\/markov-for-supermartingales\">Markov for stopping time<\/a>, <script type=\"math\/tex;\">\\Pr [\\exists t. ~ \\phi _t \\gt 1]<\/script> is less than <script type=\"math\/tex;\">\\phi _0 = \\exp (-\\varepsilon ^2\\mu )<\/script>. <\/p>\n<p>By inspection each <script type=\"math\/tex;\">\\phi _t<\/script> is non-negative. To see that <script type=\"math\/tex;\">\\phi <\/script> is a super-martingale, note that, using <script type=\"math\/tex;\">\\varepsilon ,x_t,y_t\\in [0,1]<\/script>, <\/p>\n<div id=\"a0000000009\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\frac{\\phi _{t}}{\\phi _{t-1}} ~ =~  (1+\\varepsilon )^{x_t}(1-\\varepsilon )^{y_t} ~ \\le ~  (1+\\varepsilon x_t)(1-\\varepsilon {y_t}) ~ \\le ~  1+\\varepsilon x_t-\\varepsilon {y_t}.  <\/script><\/div>\n<p> Since <script type=\"math\/tex;\">\\textrm{E}[x_t-y_t\\, |\\, S_{t-1}] \\le 0<\/script>, the expectation of the right-hand side (conditioned on <script type=\"math\/tex;\">S_{t-1}<\/script>) is at most 1. <\/p>\n<\/div>\n<\/details>\n<\/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=\"a0000000010\">Pessimistic estimator<\/h1>\n<p> Note that <script type=\"math\/tex;\">\\phi _t<\/script> in the proof above also serves as a pessimistic estimator on the probability of event\u00a0\\eqref{event2}: that is, (a) its initial value, <script type=\"math\/tex;\">\\phi _0<\/script>, is <script type=\"math\/tex;\">\\exp (-\\varepsilon ^2\\mu )<\/script>, and (b) for each <script type=\"math\/tex;\">t<\/script>, given the current state <script type=\"math\/tex;\">S_t<\/script>, the conditional probability of\u00a0\\eqref{event2} is less than <script type=\"math\/tex;\">\\phi _t<\/script> (so the event won\u2019t happen as long as the algorithm keeps <script type=\"math\/tex;\">\\phi _t \\le 1<\/script>), and (c) <script type=\"math\/tex;\">\\phi <\/script> is a super-martingale. <\/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=\"a0000000011\">Related<\/h1>\n<ul class=\"itemize\">\n<li>\n<p>Azuma\u2019s inequality (<a href=\"http:\/\/en.wikipedia.org\/wiki\/Azuma%27s_inequality\">wikipedia<\/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=\"a0000000008\"> Let <script type=\"math\/tex;\">X=\\sum _{s=1}^t x_s<\/script> and <script type=\"math\/tex;\">Y=\\sum _{s=1}^t y_s<\/script>. \\eqref{event2} implies <script type=\"math\/tex;\"> \\exp (X \\varepsilon \/ (1+\\varepsilon ) - Y \\varepsilon \/(1-\\varepsilon )) ~ \\ge ~  \\exp (\\varepsilon ^2 \\mu ) <\/script>. Using <script type=\"math\/tex;\">e^{z\/(1+z)} \\lt 1+z<\/script> for <script type=\"math\/tex;\">z\\in \\{ \\varepsilon ,-\\varepsilon \\} <\/script> gives <script type=\"math\/tex;\"> (1+\\varepsilon )^X(1-\\varepsilon )^Y ~ \\gt ~  \\exp (\\mu \\varepsilon ^2). <\/script> <\/li>\n<\/ol><\/div>\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Extending the Chernoff bound to handle sums with randomly many terms. Alice goes to the casino and plays bets on a sequence of fair coin flips. On the th bet, Alice chooses an amount to bet: she wins if this flip is heads, otherwise she loses . Since it\u2019s Vegas, she never stops playing. Fix [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":5735,"menu_order":4,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-3998","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/3998","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=3998"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/3998\/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=3998"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}