{"id":5690,"date":"2013-11-24T10:51:43","date_gmt":"2013-11-24T18:51:43","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=5690"},"modified":"2026-09-30T09:16:23","modified_gmt":"2026-09-30T17:16:23","slug":"markov-for-supermartingales","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/stopping-times\/markov-for-supermartingales\/","title":{"rendered":"Markov bound for super-martingales"},"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> For any non-negative super-martingale, the probability that its maximum <script type=\"math\/tex;\">\\max _t X_t<\/script> ever exceeds a given value <script type=\"math\/tex;\">c<\/script> is at most <script type=\"math\/tex;\">\\textrm{E}[X_0]\/c<\/script>. <\/em><\/center><\/p><\/blockquote>\n<p>  The <a href=\"http:\/\/algnotes.info\/on\/basic-bounds\">Markov bound<\/a> plays a fundamental role in the following sense: many probabilistic proofs, including, for example, <a href=\"http:\/\/algnotes.info\/on\/chernoff-bound-proof\">the proof of the Chernoff bound<\/a>, rely ultimately on the Markov bound. This note discusses a bound that plays a role similar to the Markov bound in a particular important scenario: when analyzing the maximum value achieved by a given non-negative super-martingale. <\/p>\n<p>Here\u2019s a simple example. Alice goes to the casino with $1. At the casino, she plays the following game repeatedly: she bets half her current balance on a fair coin flip. (For example, on the first flip, she bets 50 cents, so she wins 50 cents with probability 1\/2 and loses 50 cents with probability 1\/2.) Will Alice\u2019s winnings <em>ever<\/em> reach $10 or more? The bound here says this happens with probability at most 1\/10.<!--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\/basic-bounds\">Markov bound<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/walds\">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\">Markov bound for super-martingale maxima<\/h1>\n<p> Let <script type=\"math\/tex;\">X_0,X_1,X_2,\\ldots <\/script> be a non-negative super-martingale \u2014 a sequence of non-negative random variables that is non-increasing in expectation: <script type=\"math\/tex;\">\\textrm{E}[X_t\\, |\\, X_{t-1}] \\le X_{t-1}<\/script>, and <script type=\"math\/tex;\">X_t \\ge 0<\/script> for each <script type=\"math\/tex;\">t<\/script>. The sequence may be finite or infinite. <\/p>\n<p>Consider the event that <script type=\"math\/tex;\">\\max _t X_t \\ge c<\/script>, for some given <script type=\"math\/tex;\">c<\/script>. To bound the probability of this event, <em>if<\/em> we have a bound on the expectation of <script type=\"math\/tex;\">\\max _t X_t<\/script> we can use the Markov bound. For example, in the ideal case, if it happens that <script type=\"math\/tex;\">\\textrm{E}[\\max _t X_t]<\/script> is at most <script type=\"math\/tex;\">\\textrm{E}[X_0]<\/script>, then the Markov bound implies that the event in question happens with probability at most <script type=\"math\/tex;\">\\textrm{E}[X_0]\/c<\/script>. Although <script type=\"math\/tex;\">\\textrm{E}[\\max _t X_t]<\/script> can be much larger than <script type=\"math\/tex;\">\\textrm{E}[X_0]<\/script>, the desired bound in any case: <\/p>\n<div id=\"a0000000004\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma <\/b> (Markov for super-martingale maxima).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Fix any <script type=\"math\/tex;\">c\\ge 0<\/script>.\u00a0<br \/>(a) <script type=\"math\/tex;\">\\Pr [\\max _t X_t \\ge c] \\le E[X_0]\/c<\/script>. <br \/>(b) <script type=\"math\/tex;\">\\Pr [\\max _t X_t > c] < E[X_0]\/c<\/script>. <\/p>\n<\/div><\/div>\n<p>In short, this bound substitutes for the Markov bound to give us a natural bound on the probability of the event <script type=\"math\/tex;\">\\max _t X_t\\ge c<\/script>. Note that in most applications <script type=\"math\/tex;\">X_0<\/script> will be a fixed value independent of the outcome. <\/p>\n<\/div>\n<div class=\"latex-section\">\n<h1 id=\"a0000000005\">Proof idea<\/h1>\n<p> For our purposes, knowing how to <em>use<\/em> this bound is more important than knowing how to prove it. Here is the proof just for the sake of completeness. <\/p>\n<p>To get the intuition, consider the following seemingly weaker bound. If <script type=\"math\/tex;\">T<\/script> is any stopping time with finite expectation, then by Wald\u2019s equation <script type=\"math\/tex;\">\\textrm{E}[X_T]<\/script> is at most <script type=\"math\/tex;\">\\textrm{E}[X_0]<\/script>, so by Markov <script type=\"math\/tex;\">\\Pr [X_T \\ge c]<\/script> is at most <script type=\"math\/tex;\">\\textrm{E}[X_0]\/c<\/script>. That is, the desired bound holds for the single value <script type=\"math\/tex;\">X_T<\/script>. <\/p>\n<p>The proof of the lemma uses this argument, with <script type=\"math\/tex;\">T<\/script> specifically defined to be the <em>first time<\/em> such that <script type=\"math\/tex;\">X_T \\ge c<\/script> (if any, else <script type=\"math\/tex;\">\\infty <\/script>). (In the example, this is analogous to Alice quitting as soon as her winnings reach $<script type=\"math\/tex;\">10<\/script>.) This <script type=\"math\/tex;\">T<\/script> is indeed a stopping time, and, crucially, the event <script type=\"math\/tex;\">\\max _t X_t \\ge c<\/script> occurs only if <script type=\"math\/tex;\">X_T \\ge c<\/script>. So the bound on <script type=\"math\/tex;\">\\Pr [X_T \\ge c]<\/script> from the previous paragraph implies the result. A technical obstacle is that <script type=\"math\/tex;\">T<\/script> might not have finite expectation, but this is easily overcome via a limit argument. <\/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<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> Assume without loss of generality that <script type=\"math\/tex;\">X_0<\/script> is a fixed value (non-random). (If not, then condition first on any particular value of <script type=\"math\/tex;\">X_0<\/script>.) <\/p>\n<p><em>Part (a).<\/em> Let <script type=\"math\/tex;\">T=\\min \\{ t \\, |\\, X_t \\ge c\\} <\/script>. The probability in question is <script type=\"math\/tex;\">\\Pr [T\\lt \\infty ]<\/script>, which equals <script type=\"math\/tex;\">\\lim _{n\\rightarrow \\infty } \\Pr [T \\le n]<\/script>. To prove (a), we prove that <script type=\"math\/tex;\">\\forall n. \\,  \\Pr [T\\le n] \\le X_0\/c<\/script> <\/p>\n<p>Define <script type=\"math\/tex;\">T_n = \\min (n, T)<\/script>, so that <script type=\"math\/tex;\">T\\le n \\,  \\Leftrightarrow X_{T_n} \\ge c<\/script>. Then <script type=\"math\/tex;\">T_n<\/script> is a stopping time with finite expectation, and, for <script type=\"math\/tex;\">t\\le T_n<\/script>, each difference <script type=\"math\/tex;\">X_{t}-X_{t-1}<\/script> is non-positive in expectation and uniformly bounded below (by <script type=\"math\/tex;\">0 - c<\/script>), so, by Wald\u2019s, <script type=\"math\/tex;\">\\textrm{E}[X_{T_n}]\\le X_0<\/script>. <\/p>\n<p>Finally, <script type=\"math\/tex;\">\\Pr [T\\le n] = \\Pr [X_{T_n} \\ge c]<\/script>, which by Markov is at most <script type=\"math\/tex;\">\\textrm{E}[X_{T_n}]\/\\, c \\le X_0\/c<\/script>. <\/p>\n<p><em>Part (b).<\/em> Let <script type=\"math\/tex;\">T=\\min \\{ t \\, |\\, X_t \\gt c\\} <\/script> and <script type=\"math\/tex;\">T_n = \\min (n,T)<\/script>. The probability in question is <script type=\"math\/tex;\">\\Pr [T\\lt \\infty ]<\/script>, which equals <script type=\"math\/tex;\">\\lim _{n\\rightarrow \\infty } \\Pr [T \\le n]<\/script>, which equals <\/p>\n<div id=\"a0000000008\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{align*}  \\lim _{n\\rightarrow \\infty } \\Pr [X_{T_n} \\gt c] & ~ \\le ~  \\lim _{n\\rightarrow \\infty } \\frac{\\textrm{E}[X_{T_n}]}{\\textrm{E}[X_{T_n}\\, |\\, X_{T_n} \\gt c ]} \\\\ & ~ \\le ~  \\frac{X_0}{\\lim _{n\\rightarrow \\infty } \\textrm{E}[X_{T_n}\\, |\\, X_{T_n} \\gt c]} \\\\ & ~ =~  \\frac{X_0}{\\textrm{E}[X_{T}\\, |\\, T \\lt \\infty ]}. \\end{align*}<\/script><\/div>\n<p> (The first inequality follows from <script type=\"math\/tex;\">\\textrm{E}[X_{T_n}]\\,  \\ge \\,  \\Pr [X_{T_n} \\gt c]\\,  \\textrm{E}[X_{T_n} \\, |\\, X_{T_n} \\gt c]<\/script>, using the non-negativity of <script type=\"math\/tex;\">X_{T_n}<\/script>. The second follows, using Wald\u2019s as in the proof of part (a), from <script type=\"math\/tex;\">\\textrm{E}[X_{T_n}] \\le X_0<\/script>. The third follows by calculation using that <script type=\"math\/tex;\">\\lim _{n\\rightarrow \\infty }\\Pr [T\\ge n \\, |\\, T < \\infty ] = 0<\/script>.) <\/p>\n<p>To conclude, note that (using <script type=\"math\/tex;\">\\Pr [T\\lt \\infty ] \\gt 0<\/script>, for otherwise we are done) that by definition <script type=\"math\/tex;\">T\\lt \\infty \\Rightarrow X_T \\gt c<\/script>, so the expectation in the denominator on the right-hand side is a weighted average of values each of which exceeds <script type=\"math\/tex;\">c<\/script>, and so must itself exceed <script type=\"math\/tex;\">c<\/script> (that is, <script type=\"math\/tex;\">\\textrm{E}[X_{T}\\, |\\, T \\lt \\infty ] = \\textrm{E}[X_{T}\\, |\\, X_T > c] > c<\/script>). <\/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=\"a0000000009\">Pessimistic estimator<\/h1>\n<p> <em>(a)<\/em> Given the value <script type=\"math\/tex;\">X_{t}<\/script> at the current time <script type=\"math\/tex;\">t<\/script>, as long as the bad event has not yet happened (that is, as long as <script type=\"math\/tex;\">\\forall s \\lt t. ~ X_s \\lt c <\/script>), the value <script type=\"math\/tex;\">\\phi _t = X_t\/c<\/script> is a pessimistic estimator for the conditional probability of the event <script type=\"math\/tex;\">\\exists t.~  X_t \\ge c<\/script>. The value is initially <script type=\"math\/tex;\">\\textrm{E}[X_0]\/c<\/script>, it is non-increasing in expectation with each step, and, as long as it remains less than 1, the event in question doesn\u2019t happen. <\/p>\n<p><em>(b)<\/em> The same <script type=\"math\/tex;\">\\phi _t<\/script> is a pessimistic estimator for the event in part (b): the value is initially <script type=\"math\/tex;\">\\textrm{E}[X_0]\/c<\/script>, it is non-increasing in expectation with each step, and, as long as it remains less than or equal to 1, the event in question doesn\u2019t happen. <\/p>\n<\/div><\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>For any non-negative super-martingale, the probability that its maximum ever exceeds a given value is at most . The Markov bound plays a fundamental role in the following sense: many probabilistic proofs, including, for example, the proof of the Chernoff bound, rely ultimately on the Markov bound. This note discusses a bound that plays a [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":5735,"menu_order":3,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-5690","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/5690","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=5690"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/5690\/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=5690"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}