{"id":5630,"date":"2013-11-19T15:57:29","date_gmt":"2013-11-19T23:57:29","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=5630"},"modified":"2026-09-30T09:16:27","modified_gmt":"2026-09-30T17:16:27","slug":"walds-dependent","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/stopping-times\/walds-dependent\/","title":{"rendered":"Wald\u2019s equation for dependent increments"},"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>A variant of Wald\u2019s equation to use when the expected increment depends on the sum so far.<\/em><\/center><\/p><\/blockquote>\n<p>  Wald\u2019s equation applies to any sequence that, with each step, increases (or decreases) in expectation by a constant additive amount. What about sequences where the expected change with each step depends on the current value? For example, suppose Alice starts with <script type=\"math\/tex;\">n<\/script> coins. In each round <script type=\"math\/tex;\">t=1,2,\\ldots ,T<\/script>, she flips each remaining coin and discards those that come up tails. She stops once all coins are discarded. What is the expected number of rounds?<!--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\/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\">Wald\u2019s for dependent increments<\/h1>\n<div id=\"a0000000004\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma <\/b> (Wald\u2019s for dependent increments).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Consider a random sequence <script type=\"math\/tex;\">X=X_0, X_1, \\ldots , X_T<\/script>, where <script type=\"math\/tex;\">T<\/script> is a stopping time with finite expectation. Let <script type=\"math\/tex;\">\\delta :{\\mathbb R}\\rightarrow {\\mathbb R}_+<\/script> be monotonic. <\/p>\n<p>If <script type=\"math\/tex;\">\\textrm{E}[X_{t+1} - X_{t} \\, |\\, X_t ] ~ \\le ~  \\delta (X_t)<\/script> for <script type=\"math\/tex;\">t\\lt T<\/script>, and <script type=\"math\/tex;\">X<\/script> is increasing and <script type=\"math\/tex;\">\\delta <\/script> is increasing, then <\/p>\n<div id=\"eqnLI\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{eqnLI} \\textrm{E}[T] \\, \\ge \\,  \\textrm{E}\\left[\\int _{X_0}^{X_T} \\frac{1}{\\delta (z)} dz\\right]. \\end{equation}<\/script><\/div>\n<p>If <script type=\"math\/tex;\">\\textrm{E}[X_{t+1} - X_{t} \\, |\\, X_t ] ~ \\ge ~  \\delta (X_t)<\/script> for <script type=\"math\/tex;\">t\\lt T<\/script>, and <script type=\"math\/tex;\">X<\/script> is increasing and <script type=\"math\/tex;\">\\delta <\/script> is decreasing, then <\/p>\n<div id=\"eqnGI\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{eqnGI} \\textrm{E}[T] \\, \\le \\,  \\textrm{E}\\left[\\int _{X_0}^{X_T} \\frac{1}{\\delta (z)} dz\\right]. \\end{equation}<\/script><\/div>\n<p>If <script type=\"math\/tex;\">\\textrm{E}[X_t - X_{t+1} \\, |\\, X_t ] ~ \\le ~  \\delta (X_t)<\/script> for <script type=\"math\/tex;\">t\\lt T<\/script>, and <script type=\"math\/tex;\">X<\/script> is decreasing and <script type=\"math\/tex;\">\\delta <\/script> is decreasing, then <\/p>\n<div id=\"eqnLD\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{eqnLD} \\textrm{E}[T] \\, \\ge \\,  \\textrm{E}\\left[\\int _{X_T}^{X_0} \\frac{1}{\\delta (z)} dz\\right]. \\end{equation}<\/script><\/div>\n<p>If <script type=\"math\/tex;\">\\textrm{E}[X_t - X_{t+1} \\, |\\, X_t ] ~ \\ge ~  \\delta (X_t)<\/script> for <script type=\"math\/tex;\">t\\lt T<\/script>, and <script type=\"math\/tex;\">X<\/script> is decreasing and <script type=\"math\/tex;\">\\delta <\/script> is increasing, then <\/p>\n<div id=\"eqnGD\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{eqnGD} \\textrm{E}[T] \\, \\le \\,  \\textrm{E}\\left[\\int _{X_T}^{X_0} \\frac{1}{\\delta (z)} dz\\right]. \\end{equation}<\/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=\"a0000000005\">Example<\/h1>\n<p> For Alice\u2019s coin-flipping example above, let <script type=\"math\/tex;\">T<\/script> be the number of rounds; let <script type=\"math\/tex;\">n_t<\/script> be the number of coins left after <script type=\"math\/tex;\">t<\/script> rounds. With each round, each remaining coin is discarded with probability <script type=\"math\/tex;\">1\/2<\/script>, so <\/p>\n<div id=\"a0000000006\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\textrm{E}[n_t - n_{t+1} \\, |\\, n_t ] ~ =~  \\textstyle \\frac{1}{2}\\,  n_t ~ =~  \\frac{1}{2}\\,  \\lceil n_t \\rceil . <\/script><\/div>\n<p> (The ceiling will be useful below.) What does this tell us about <script type=\"math\/tex;\">\\textrm{E}[T]<\/script>? <\/p>\n<p>Take <script type=\"math\/tex;\">\\delta (n_t) = \\frac{1}{2}\\lceil n_t\\rceil <\/script>. Since <script type=\"math\/tex;\">n_t<\/script> is decreasing and <script type=\"math\/tex;\">\\delta <\/script> is increasing, by\u00a0\\eqref{eqnGD} in the lemma, the expected number of rounds until all <script type=\"math\/tex;\">n<\/script> coins are discarded is at most <\/p>\n<div id=\"a0000000007\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\int _{n_T}^{n_0} \\frac{1}{\\frac{1}{2}\\lceil z\\rceil \\, dz} ~ =~  2 \\int _0^n \\frac{1}{\\lceil z \\rceil \\, dz} ~ =~  2\\,  {\\rm H}(n),  <\/script><\/div>\n<p> where <script type=\"math\/tex;\">{\\rm H}(n) = 1+\\frac{1}{2} + \\frac{1}{3} + \\cdots + \\frac{1}{n}<\/script> is the <script type=\"math\/tex;\">n<\/script>th Harmonic number. <\/p>\n<p>(Without the ceiling in <script type=\"math\/tex;\">\\delta (n_t)<\/script>, the lemma would only give bound <script type=\"math\/tex;\">2\\ln (n\/0) = \\infty <\/script>!) <\/p>\n<div id=\"a0000000008\" 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 throws balls one at a time randomly into <script type=\"math\/tex;\">n<\/script> bins. Show that the expected number of balls needed before all bins receive a ball is at most <script type=\"math\/tex;\">n\\, {\\rm H}(n)<\/script>. <\/p>\n<\/div><\/div>\n<div class=\"expandable\" id=\"a0000000009\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for hint\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for hint\u2026<\/summary>\n<div class=\"collapseomatic_content\"> Define <script type=\"math\/tex;\">n_t<\/script> to be the number of empty bins after <script type=\"math\/tex;\">t<\/script> throws. Observe that, with each throw, each empty bin becomes non-empty with probability <script type=\"math\/tex;\">1\/n<\/script>, so <script type=\"math\/tex;\">\\textrm{E}[n_t - n_{t+1} \\, |\\, n_t]<\/script> is <script type=\"math\/tex;\">n_t\/n<\/script>. Apply\u00a0\\eqref{eqnGD} from the lemma with <script type=\"math\/tex;\">\\delta (n_t) = \\lceil n_t \\rceil \/ n<\/script>. <\/div>\n<\/details>\n<\/div>\n<div id=\"a0000000010\" 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>Starting with just 1 amoeba, at each time <script type=\"math\/tex;\">t=1,2,\\ldots <\/script>, each existing amoeba splits into two with probability 1\/2. Show that the expected time before there are <script type=\"math\/tex;\">n<\/script> amoeba is at least <script type=\"math\/tex;\">1.5\\,  {\\rm H}(n)<\/script>. <\/p>\n<\/div><\/div>\n<div class=\"expandable\" id=\"a0000000011\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for hint\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for hint\u2026<\/summary>\n<div class=\"collapseomatic_content\"> Define <script type=\"math\/tex;\">n_t<\/script> to be the number of amoeba at time <script type=\"math\/tex;\">t<\/script> (so <script type=\"math\/tex;\">n_0 = 1<\/script>). Observe that <script type=\"math\/tex;\">\\textrm{E}[n_{t+1} - n_{t} \\, |\\, n_t]<\/script> is <script type=\"math\/tex;\">1.5 n_t<\/script>. Apply\u00a0\\eqref{eqnLI} from the lemma with <script type=\"math\/tex;\">\\delta (n_t) = 1.5\\lceil n_t \\rceil <\/script>. <\/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=\"a0000000012\">Proof of lemma<\/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>We first prove\u00a0\\eqref{eqnLI}. Define random sequence <script type=\"math\/tex;\">D_1, D_2,\\ldots , D_T<\/script> by <script type=\"math\/tex;\">\\displaystyle D_t ~ =~  \\int _{X_{t-1}}^{X_{t}} \\frac{1}{\\delta (z)}\\, dz.<\/script> <\/p>\n<p>Since <script type=\"math\/tex;\">\\delta <\/script> is increasing, <script type=\"math\/tex;\">D_t ~ \\le ~  (X_{t} - X_{t-1})\/\\delta (X_{t-1}).<\/script> <\/p>\n<p>By assumption <script type=\"math\/tex;\">\\textrm{E}[X_{t}-X_{t-1}\\, |\\, X_{t-1}] \\le \\delta (X_{t-1})<\/script>, giving <script type=\"math\/tex;\">\\textrm{E}[D_t \\, |\\, T \\ge t] \\le 1<\/script>. This (by Wald\u2019s equation) gives <script type=\"math\/tex;\">\\textrm{E}[\\sum _{t=1}^T D_t] \\le \\textrm{E}[T]<\/script>, implying the bound. <\/p>\n<p>(Wald\u2019s requires that the <script type=\"math\/tex;\">D_t<\/script>\u2019s are bounded from one side. Each <script type=\"math\/tex;\">D_t<\/script> is non-negative because <script type=\"math\/tex;\">X<\/script> is increasing and <script type=\"math\/tex;\">\\delta (z)\\ge 0<\/script>.) <\/p>\n<p>This proves\u00a0\\eqref{eqnLI}. The proof of\u00a0\\eqref{eqnGI} is similar, but uses <script type=\"math\/tex;\">D_t \\ge (X_t-X_{t-1})\/\\delta (X_{t-1})<\/script> to get <script type=\"math\/tex;\">\\textrm{E}[D_t \\, |\\, T \\ge t] \\ge 1<\/script>. Bounds\u00a0\\eqref{eqnLD} and\u00a0\\eqref{eqnGD} follow from\u00a0\\eqref{eqnLI} and\u00a0\\eqref{eqnGI} by the change of variables <script type=\"math\/tex;\">X'_t = -X_t<\/script> and <script type=\"math\/tex;\">\\delta '(z) = \\delta (-z)<\/script>. (Or redefine <script type=\"math\/tex;\">D_t = \\int _{X_{t}}^{X_{t-1}} 1\/\\delta (z)\\,  dz<\/script> in the proof above and proceed similarly.) <\/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>\n<div>\n<h1 id=\"bibliography\">Bibliography<\/h1>\n<table class=\"bibliography\" cellspacing=\"0\" cellpadding=\"2\">\n<tr>\n<td valign=\"top\">[<a name=\"lehre_general_2013\">1<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;P+K++Lehre+&quot;+author:&quot;+C+Witt&quot;+intitle:&quot;+General+drift+analysis+with+tail+bounds&quot;\">P.\u00a0K. Lehre and C.\u00a0Witt. General drift analysis with tail bounds. <em>arXiv:1307.2559 [cs]<\/em>, July 2013. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"lehre_concentrated_2014\">2<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;P+K++Lehre+&quot;+author:&quot;+C+Witt&quot;+intitle:&quot;+Concentrated+hitting+times+of+randomized+search+heuristics+with+variable+drift&quot;\">P.\u00a0K. Lehre and C.\u00a0Witt. Concentrated hitting times of randomized search heuristics with variable drift. In H.-K. Ahn and C.-S. Shin, editors, <em>Algorithms and Computation<\/em>, number 8889 in Lecture Notes in Computer Science, pages 686\u2013697. Springer International Publishing, Dec. 2014. DOI: 10.1007\/978-3-319-13075-0_54. <\/a><\/td>\n<\/tr>\n<\/table><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>A variant of Wald\u2019s equation to use when the expected increment depends on the sum so far. Wald\u2019s equation applies to any sequence that, with each step, increases (or decreases) in expectation by a constant additive amount. What about sequences where the expected change with each step depends on the current value? For example, suppose [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":5735,"menu_order":2,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-5630","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/5630","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=5630"}],"version-history":[{"count":3,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/5630\/revisions"}],"predecessor-version":[{"id":9033,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/5630\/revisions\/9033"}],"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=5630"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}