{"id":1514,"date":"2010-05-05T12:55:22","date_gmt":"2010-05-05T20:55:22","guid":{"rendered":"http:\/\/greedyalgs.com\/blog\/?p=1514"},"modified":"2026-09-30T09:16:43","modified_gmt":"2026-09-30T17:16:43","slug":"walds","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/stopping-times\/walds\/","title":{"rendered":"Wald\u2019s equation"},"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>Wald\u2019s equation, a form of linearity of expectation for sums with randomly many terms.<\/em><\/center><\/p><\/blockquote>\n<p>Consider a sum <script type=\"math\/tex;\">\\sum _{t=1}^T x_t<\/script> of random variables, where the number of terms <script type=\"math\/tex;\">T<\/script> is itself a random variable. If each term <script type=\"math\/tex;\">x_t<\/script> has expectation at most (or at least) <script type=\"math\/tex;\">\\mu <\/script>, then the expectation of the sum is at most (or at least) <script type=\"math\/tex;\">\\mu \\, \\textrm{E}[T]<\/script> (the bound on the expectation of each term, times the expected number of terms). This holds provided the random variables in the sum are bounded above or below and <script type=\"math\/tex;\">T<\/script> is a <em>stopping time<\/em> with finite 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\/basic-bounds\">basic bounds<\/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\">Formal requirements<\/h1>\n<p> For Wald\u2019s equation to hold certain technical requirements must be met. Being aware of them can help avoid confusion in some corner cases. Here are the requirements: <\/p>\n<ol class=\"enumerate\">\n<li value=\"1\">\n<p><script type=\"math\/tex;\">T<\/script> must be a <em>stopping time<\/em>. That is, at each time <script type=\"math\/tex;\">t<\/script>, the state <script type=\"math\/tex;\">S_t<\/script> that determines <script type=\"math\/tex;\">x_t<\/script> is also enough to determine whether <script type=\"math\/tex;\">T=t<\/script>. (For example, if <script type=\"math\/tex;\">T<\/script> is the number of rolls until an odd roll, then <script type=\"math\/tex;\">T<\/script> is a stopping time. However, if <script type=\"math\/tex;\">T<\/script> is the number of rolls until the roll <em>before<\/em> the first odd roll, that is not a stopping time \u2014 knowing whether <script type=\"math\/tex;\">T\\ge t<\/script> requires knowing whether the <em>next<\/em> roll will be odd.) <\/p>\n<\/li>\n<li value=\"2\">\n<p><script type=\"math\/tex;\">T<\/script> must have finite expectation. (This implies that <script type=\"math\/tex;\">T<\/script> is finite with probability 1.) <\/p>\n<\/li>\n<li value=\"3\">\n<p>All <script type=\"math\/tex;\">T<\/script> terms must be (uniformly) bounded on one side \u2014 that is, there must <em>exist<\/em> a constant <script type=\"math\/tex;\">c<\/script>, independent of the outcome of the random experiment, such that either, in all outcomes, every <script type=\"math\/tex;\">x_t<\/script> is at most <script type=\"math\/tex;\">c<\/script>, or, in all outcomes, each <script type=\"math\/tex;\">x_t<\/script> is at least <script type=\"math\/tex;\">c<\/script>. <\/p>\n<\/li>\n<\/ol>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000004\">Wald\u2019s equation<\/h2>\n<div id=\"a0000000005\" class=\"my-theorem latex-paragraph latex-thm\">\n<div class=\"latex-paragraph-heading\">   <b \"=\"&quot;\">Theorem.<\/b>   <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>Let <script type=\"math\/tex;\">T<\/script> be a stopping time with finite expectation. Assume that the values <script type=\"math\/tex;\">x_t<\/script> (for <script type=\"math\/tex;\">t\\le T<\/script>) are bounded from above, or are bounded from below. <\/p>\n<p>If the expectation of each <script type=\"math\/tex;\">x_t<\/script> is at most <script type=\"math\/tex;\">\\mu <\/script>, then the sum\u2019s expectation is at most <script type=\"math\/tex;\">\\mu \\, \\textrm{E}[T]<\/script> \u2014 that is, if <script type=\"math\/tex;\">\\textrm{E}[x_t\\, |\\, T\\ge t] \\le \\mu <\/script> for all <script type=\"math\/tex;\">t<\/script>, then <script type=\"math\/tex;\">\\textrm{E}\\big[\\sum _{t=1}^T x_t\\big] ~ \\le ~  \\mu \\, \\textrm{E}[T]<\/script>. <\/p>\n<p>If the expectation of each <script type=\"math\/tex;\">x_t<\/script> is <em>at least<\/em> <script type=\"math\/tex;\">\\mu <\/script>, then the sum\u2019s expectation is at least <script type=\"math\/tex;\">\\mu \\, \\textrm{E}[T]<\/script>. <\/p>\n<\/div><\/div>\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=\"a0000000006\">Exercises<\/h1>\n<div id=\"a0000000007\" class=\"my-theorem latex-paragraph latex-Exercise\">\n<div class=\"latex-paragraph-heading\">  <b>Exercise 1.<\/b>    <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>Alice rolls a fair six-sided die (that is, she randomly sample numbers i.i.d.\u00a0uniformly from <script type=\"math\/tex;\">\\{ 1,2,3,4,5,6\\} <\/script>), until she rolls an odd number. What is the expected number of 5\u2019s that she rolls? <\/p>\n<\/div><\/div>\n<div class=\"expandable\" id=\"a0000000008\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for solution\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for solution\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p> Let <script type=\"math\/tex;\">T<\/script> be the number of rolls. First we use Wald\u2019s to show that <script type=\"math\/tex;\">\\textrm{E}[T] = 2<\/script>. Indeed, by Wald\u2019s, the expected number of odd rolls, which is always 1, equals <script type=\"math\/tex;\">\\textrm{E}[T]<\/script> times 1\/2 (the probability that a given roll is odd). It follows that <script type=\"math\/tex;\">\\textrm{E}[T] = 2<\/script>. <\/p>\n<p>By Wald\u2019s again, the expected number of 5\u2019s rolled is the expected number of rolls (which is 2) times the chance that any given roll is 5 (which is 1\/6). That is, the expected number of 5\u2019s is 2\/6 = 1\/3. <\/p>\n<\/div>\n<\/details>\n<\/div>\n<div id=\"a0000000009\" class=\"my-theorem latex-paragraph latex-Exercise\">\n<div class=\"latex-paragraph-heading\">  <b>Exercise 2.<\/b>    <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>Roll a fair six-sided die, stopping with the first 1. (i) Show that the expected sum of the rolls is 21. (ii) Show that if you stop with the first 6 (instead of the first 1) the expected sum is also 21. <\/p>\n<\/div><\/div>\n<div class=\"expandable\" id=\"a0000000010\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for solution\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for solution\u2026<\/summary>\n<div class=\"collapseomatic_content\"> Following the same reasoning as in the first exercise, the expected number of rolls is 6 in either case. The expectation of each roll is 3.5. By Wald\u2019s, the expected sum is the product <script type=\"math\/tex;\">3.5 \\cdot 6 = 21<\/script>. <\/div>\n<\/details>\n<\/div>\n<div id=\"a0000000011\" class=\"my-theorem latex-paragraph latex-Exercise\">\n<div class=\"latex-paragraph-heading\">  <b>Exercise 3.<\/b>    <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>Show that each of the three technical requirements above is necessary. For each requirement, describe a random sum meeting the other two requirements, but with <script type=\"math\/tex;\">\\textrm{E}[x_t] = 0<\/script> and <script type=\"math\/tex;\">\\textrm{E}[\\sum _{t=1}^T x_t] = 1<\/script>. <\/p>\n<\/div><\/div>\n<div class=\"expandable\" id=\"a0000000012\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for solution\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for solution\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p>Repeatedly flip a fair coin. On each flip <script type=\"math\/tex;\">t<\/script>, bet some amount (<script type=\"math\/tex;\">b_t<\/script>, as described below) that the flip is heads. Let <script type=\"math\/tex;\">x_t<\/script> be the amount won in the <script type=\"math\/tex;\">t<\/script>th flip, either <script type=\"math\/tex;\">b_t<\/script> or <script type=\"math\/tex;\">-b_t<\/script>, <\/p>\n<p>For (3), let <script type=\"math\/tex;\">b_t = 2^t<\/script>; stop after the first win. <\/p>\n<p>For (2), let each <script type=\"math\/tex;\">b_t = 1<\/script>; stop when the total winnings equals 1. (But note that this counter-example is a bit weak, because <script type=\"math\/tex;\">\\mu = 0<\/script> and <script type=\"math\/tex;\">\\textrm{E}[T] = \\infty <\/script>, so <script type=\"math\/tex;\">\\mu \\, \\textrm{E}[T]<\/script> is not well defined. We do have <script type=\"math\/tex;\">\\Pr [T=\\infty ] = 0<\/script> though.) <\/p>\n<p>For (1), let each <script type=\"math\/tex;\">b_t = 1<\/script>; stop just before the first tail. (<script type=\"math\/tex;\">T<\/script> is not a stopping time. Technically, the assumption that fails here is <script type=\"math\/tex;\">\\textrm{E}[x_t \\, |\\, T\\ge t] = 0<\/script> for all <script type=\"math\/tex;\">t<\/script>, because <script type=\"math\/tex;\">x_t = 1<\/script> for all <script type=\"math\/tex;\">t\\le T<\/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=\"a0000000013\">Proof of Wald\u2019s equation<\/h1>\n<p> This \u201cone-sided\u201d variant of Wald\u2019s equation is a little non-standard. Here\u2019s a proof. <\/p>\n<div class=\"expandable\" id=\"a0000000014\" 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>As <script type=\"math\/tex;\">\\textrm{E}[T]\\lt \\infty <\/script>, we have <script type=\"math\/tex;\">\\sum _{t=1}^\\infty \\Pr [T=t] = 1<\/script>, and, by linearity of expectation, <\/p>\n<div id=\"a0000000015\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{eqnarray*}  \\textrm{E}[\\textstyle \\sum _{t=1}^T x_t] & =& \\textstyle \\sum _{s=1}^\\infty \\Pr [T=s]\\,  \\textrm{E}[\\sum _{t=1}^s x_t \\, |\\, T=s] \\\\ & =& \\textstyle \\sum _{s=1}^\\infty \\sum _{t=1}^{s} \\Pr [T=s]\\, E[x_t \\, |\\, T=s]. \\end{eqnarray*}<\/script><\/div>\n<p> The sum above is absolutely convergent (the order of summation doesn\u2019t matter), because either (i) the total of the positive terms in the sum is finite or (ii) the total of the negative terms is finite. (This follows from the assumption that either (i) each <script type=\"math\/tex;\">x_t<\/script> is at most some constant <script type=\"math\/tex;\">c<\/script>, or (ii) each <script type=\"math\/tex;\">x_t<\/script> is at least some constant <script type=\"math\/tex;\">c<\/script>. For example, if each <script type=\"math\/tex;\">x_t<\/script> is at most <script type=\"math\/tex;\">c<\/script>, then the total of the positive terms in the sum is at most <\/p>\n<div id=\"a0000000016\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\textstyle \\sum _{s=1}^\\infty \\sum _{t=1}^{s} \\Pr [T=s]\\, c ~ =~  c\\sum _{s=1}^\\infty \\Pr [T=s] s ~ =~  c\\, \\textrm{E}[T], <\/script><\/div>\n<p> which is finite by the assumption that <script type=\"math\/tex;\">\\textrm{E}[T]<\/script> is finite. Similarly, if each <script type=\"math\/tex;\">x_t<\/script> is at least <script type=\"math\/tex;\">c<\/script>, the total of the negative terms is finite.) <\/p>\n<p>Exchanging the order of summation, the sum equals <\/p>\n<div id=\"a0000000017\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{eqnarray*}  \\textstyle \\sum _{t=1}^\\infty \\big( \\sum _{s={t}}^\\infty \\Pr [T=s]\\, \\textrm{E}[x_t \\, |\\, T=s]\\big) & =&  \\textstyle \\sum _{t=1}^\\infty \\,  \\Pr [T\\ge t]\\,  \\textrm{E}[x_t \\, |\\, T \\ge t]\\\\ & \\le &  \\textstyle \\sum _{t=1}^{\\infty } \\Pr [T\\ge t]\\,  \\mu \\\\ & =&  \\textrm{E}[T]\\, \\mu . \\end{eqnarray*}<\/script><\/div>\n<p> The inequality above holds by the assumption <script type=\"math\/tex;\">\\textrm{E}[x_t\\, |\\, T\\ge t] \\le \\mu <\/script>. This proves the first claim. If <script type=\"math\/tex;\">\\textrm{E}[x_t\\, |\\, T\\ge t] \\ge \\mu <\/script>, then the inequality above is reversed, proving the second claim. <\/p>\n<\/div>\n<\/details>\n<\/div>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000018\">A false proof<\/h2>\n<p> Here\u2019s what <em>seems to be<\/em> a proof that Wald\u2019s equation holds even without the last two technical requirements. Can you find the error? <\/p>\n<div class=\"expandable\" id=\"a0000000019\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for \u201cproof\u201d \u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for \u201cproof\u201d \u2026<\/summary>\n<div class=\"collapseomatic_content\"> For <script type=\"math\/tex;\">t\\ge 1<\/script>, define r.v.\u00a0<script type=\"math\/tex;\">y_t<\/script> to be <script type=\"math\/tex;\">x_t<\/script> iff <script type=\"math\/tex;\">T \\ge t<\/script> and 0 otherwise. Then <script type=\"math\/tex;\">\\sum _{t=1}^T x_t = \\sum _{t=1}^\\infty y_t<\/script>. We argue that <script type=\"math\/tex;\">\\textrm{E}[\\sum _{t=1}^\\infty y_t] \\le \\mu \\textrm{E}[T]<\/script>. By linearity of expectation, <\/p>\n<div id=\"a0000000020\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{eqnarray*}  \\textrm{E}[\\textstyle \\sum _{t=1}^\\infty y_t] & =& \\textstyle \\sum _{t=1}^\\infty \\textrm{E}[y_t]\\\\ & =&  \\textstyle \\sum _{t=1}^\\infty \\,  \\Pr [T\\ge t]\\,  \\textrm{E}[y_t \\, |\\, T \\ge t] + \\Pr [T \\lt t]\\, \\textrm{E}[y_t \\, |\\, T \\lt t] \\\\ & =&  \\textstyle \\sum _{t=1}^\\infty \\,  \\Pr [T\\ge t]\\,  \\textrm{E}[x_t \\, |\\, T \\ge t] + 0\\\\ & \\le &  \\textstyle \\sum _{t=1}^{\\infty } \\Pr [T\\ge t]\\,  \\mu \\\\ & =&  \\textrm{E}[T]\\, \\mu . \\end{eqnarray*}<\/script><\/div>\n<p> The inequality above holds by the assumption <script type=\"math\/tex;\">\\textrm{E}[x_t\\, |\\, T\\ge t] \\le \\mu <\/script>. <\/div>\n<\/details>\n<\/div>\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=\"a0000000021\">Related<\/h1>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/walds-dependent\">What if <script type=\"math\/tex;\">\\textrm{E}[x_t \\, |\\, T \\ge t]<\/script> depends on <script type=\"math\/tex;\">\\sum _{s\\lt t} x_s<\/script>\u00a0?<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/markov-for-supermartingales\">Markov bound for sums with randomly many terms<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/stopping-time-chernoff\">Chernoff bound for sums with randomly many terms<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Stopping_time\">Stopping time (wikipedia)<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Wald%27s_equation\">Wald\u2019s equation (wikipedia)<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Optional_stopping_theorem\">Optional stopping theorem (wikipedia)<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Martingale_(probability_theory)\">Martingale (wikipedia)<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div><\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Wald\u2019s equation, a form of linearity of expectation for sums with randomly many terms. Consider a sum of random variables, where the number of terms is itself a random variable. If each term has expectation at most (or at least) , then the expectation of the sum is at most (or at least) (the bound [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":5735,"menu_order":1,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1514","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/1514","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=1514"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/1514\/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=1514"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}