{"id":5684,"date":"2013-11-23T14:13:51","date_gmt":"2013-11-23T22:13:51","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=5684"},"modified":"2026-09-30T09:16:30","modified_gmt":"2026-09-30T17:16:30","slug":"expected-maximum-sum","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/stopping-times\/expected-maximum-sum\/","title":{"rendered":"Expected maximum (or minimum) of many sums"},"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 maximum (or minimum) among a collection of sums.<\/em><\/center><\/p><\/blockquote>\n<p>  It can be technically convenient to work with expectations directly, instead of working with probabilities. Here, given a <em>collection<\/em> of sums of 0\/1 random variables, we bound the expected maximum (or minimum) sum in the collection. <\/p>\n<p>For example, suppose Alice throws balls randomly into <script type=\"math\/tex;\">n<\/script> bins just until the first bin has <script type=\"math\/tex;\">n<\/script> balls. The bound says that the expected maximum number of balls in any bin will be at most <script type=\"math\/tex;\">n+2\\sqrt{n\\ln n}+\\ln n<\/script>. Similarly, the expected minimum number of balls in any bin will be at least <script type=\"math\/tex;\">n-2\\sqrt{n\\ln n}<\/script>. <\/p>\n<p>The bound differs from Chernoff in a few ways: <\/p>\n<ul class=\"itemize\">\n<li>\n<p>it bounds the expected maximum or minimum (as opposed to the probability of a large deviation), <\/p>\n<\/li>\n<li>\n<p>the sums can have randomly many terms, so they don\u2019t have to be concentrated around their means. <\/p>\n<\/li>\n<\/ul>\n<p><!--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\">Warm-up: sums with a fixed number of terms<\/h1>\n<p>For a warm up, here are bounds that are directly analogous to standard Chernoff bounds, in that they concern sums that have a fixed number of terms. <\/p>\n<div id=\"a0000000004\" class=\"my-theorem latex-paragraph latex-Lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma 1<\/b> (expected maximum or minimum of many sums).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>For each <script type=\"math\/tex;\">j\\in [m]<\/script>, let <script type=\"math\/tex;\">X^j=\\sum _{t=1}^T x^j_t<\/script> be a sum of independent random variables, where each <script type=\"math\/tex;\">x^j_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>. <\/p>\n<p>(a) If <script type=\"math\/tex;\">\\textrm{E}[x^j_t] \\le \\mu <\/script> for all <script type=\"math\/tex;\">t\\le T<\/script> and all <script type=\"math\/tex;\">j\\in [m]<\/script>, then <\/p>\n<div id=\"a0000000005\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\textstyle \\textrm{E}\\left[\\max _{j\\in [m]} X^j\\right] ~ \\lt ~  (1+\\varepsilon )(\\mu T + \\varepsilon ^{-1}\\ln m). <\/script><\/div>\n<p> Taking <script type=\"math\/tex;\">\\varepsilon = \\sqrt{\\ln (m)\/\\mu T}<\/script>, the expected maximum is less than <script type=\"math\/tex;\">\\mu T + 2\\sqrt{\\mu T \\ln m} + \\ln m<\/script>. <\/p>\n<p>(b) If <script type=\"math\/tex;\">\\textrm{E}[x^j_t] \\ge \\mu <\/script> for all <script type=\"math\/tex;\">t\\le T<\/script> and all <script type=\"math\/tex;\">j\\in [m]<\/script>, then <\/p>\n<div id=\"a0000000006\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\textstyle \\textrm{E}\\left[\\min _{j\\in [m]} X^j\\right] ~ \\gt ~  (1-\\varepsilon )\\mu T - \\varepsilon ^{-1}\\ln m. <\/script><\/div>\n<p> Taking <script type=\"math\/tex;\">\\varepsilon = \\sqrt{\\ln (m)\/\\mu T}<\/script>, the expected minimum is more than <script type=\"math\/tex;\">\\mu T - 2\\sqrt{\\mu T\\ln m}<\/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=\"a0000000007\">Proof of Lemma\u00a01<\/h1>\n<div class=\"expandable\" id=\"a0000000008\" 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> (a) The maximum <script type=\"math\/tex;\">\\max _{j\\in [m]} X^j<\/script> is at most <script type=\"math\/tex;\"> \\log _{1+\\varepsilon } \\sum _{j=1}^m (1+\\varepsilon )^{X^j}. <\/script> <\/p>\n<p>By the concavity of the logarithm, the expectation of the log of the sum is at most the log of the expectation of the sum. Following the <a href=\"http:\/\/algnotes.info\/on\/chernoff-proof\">the proof of the Chernoff bound<\/a>, the expectation of each term in the sum is at most <script type=\"math\/tex;\">\\exp (\\varepsilon \\mu T)<\/script>. Hence (using <script type=\"math\/tex;\">\\ln (1+\\varepsilon )\\gt \\varepsilon \/(1+\\varepsilon )<\/script>), the expectation of the maximum is at most <\/p>\n<div id=\"a0000000009\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\log _{1+\\varepsilon } \\left[ m \\exp (\\varepsilon \\mu T) \\right] ~ =~  \\frac{1}{\\ln 1+\\varepsilon } \\left[ \\ln m ~ +~  \\varepsilon \\mu T\\right] ~ \\lt ~  (1+\\varepsilon )(\\varepsilon ^{-1} \\ln m ~ +~  \\mu T).  <\/script><\/div>\n<p>(b) Assume <script type=\"math\/tex;\">\\varepsilon \\lt 1<\/script> (if not, (b) is trivial). The minimum <script type=\"math\/tex;\">\\min _{j\\in [m]} X^j<\/script> is at least <script type=\"math\/tex;\"> \\log _{1-\\varepsilon } \\sum _{j=1}^m (1-\\varepsilon )^{X^j}. <\/script> <\/p>\n<p>By the convexity of the logarithm with negative base, the expectation of the log of the sum is at least the log of the expectation of the sum. Following the <a href=\"http:\/\/algnotes.info\/on\/chernoff-proof\">the proof of the Chernoff bound<\/a>, the expectation of each term in the sum is at least <script type=\"math\/tex;\">\\exp (-\\varepsilon \\mu T)<\/script>. Hence (using <script type=\"math\/tex;\">\\varepsilon \\lt \\ln (1\/(1-\\varepsilon ))\\le \\varepsilon \/(1-\\varepsilon )<\/script>), the expectation of the minimum is at least <\/p>\n<div id=\"a0000000010\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\log _{1-\\varepsilon } \\left[ m \\exp (-\\varepsilon \\mu T) \\right] ~ =~  \\frac{1}{\\ln 1\/(1-\\varepsilon )} \\left[\\varepsilon \\mu T - \\ln m\\right] ~ \\gt ~  (1-\\varepsilon )\\mu T - \\varepsilon ^{-1} \\ln m.  <\/script><\/div>\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=\"a0000000011\">Sums with a random number of terms<\/h1>\n<p>The next bound applies to a system that goes through a random sequence of states <script type=\"math\/tex;\">S_1,S_2,S_3,\\ldots ,S_T<\/script>, where <script type=\"math\/tex;\">T<\/script> is a stopping time with finite expectation. At each time <script type=\"math\/tex;\">t<\/script>, the current state <script type=\"math\/tex;\">S_t<\/script> determines <script type=\"math\/tex;\">m+1<\/script> values: <script type=\"math\/tex;\">x^j_t<\/script> for <script type=\"math\/tex;\">j\\in [m]<\/script> and <script type=\"math\/tex;\">y_t<\/script>, where each <script type=\"math\/tex;\">x^j_t<\/script> is in <script type=\"math\/tex;\">[0,1]<\/script> and <script type=\"math\/tex;\">\\textrm{E}[x^j_t] \\le \\textrm{E}[y_t]<\/script> for <script type=\"math\/tex;\">j\\in [m]<\/script> (or <script type=\"math\/tex;\">\\textrm{E}[x^j_t] \\ge \\textrm{E}[y_t]<\/script> for <script type=\"math\/tex;\">j\\in [m]<\/script>). The bound shows that the expectation of <script type=\"math\/tex;\">\\max _j \\sum _{t=1}^T x^j_t<\/script> (or <script type=\"math\/tex;\">\\min _j \\sum _{t=1}^T x^j_t<\/script>) is close to the expectation of <script type=\"math\/tex;\">\\sum _{t=1}^T y_t<\/script>. <\/p>\n<div id=\"lemma2\" class=\"my-theorem latex-paragraph latex-Lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma 2<\/b> (expected maximum or minimum of many sums).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Given the conditions above, let <script type=\"math\/tex;\">\\varepsilon \\in [0,1]<\/script>. <\/p>\n<p>(c) If <script type=\"math\/tex;\">\\textrm{E}[x^j_t - y_t\\, |\\, S_{t-1}]\\le 0<\/script> for all <script type=\"math\/tex;\">j\\in [m]<\/script> and all <script type=\"math\/tex;\">t\\le T<\/script>, then <\/p>\n<div id=\"a0000000012\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\textstyle \\textrm{E}\\Big[\\, {\\max _{j\\in [m]}}\\,  \\sum _{t=1}^T x^j_t\\, \\Big] ~ \\le ~ (1+\\varepsilon ) \\big(\\textrm{E}\\big[\\sum _{t=1}^T y_t\\big] \\, +\\,  \\varepsilon ^{-1}\\ln m\\big). <\/script><\/div>\n<p>(d) If <script type=\"math\/tex;\">\\textrm{E}[x^j_t - y_t\\, |\\, S_{t-1}]\\ge 0<\/script> for all <script type=\"math\/tex;\">j\\in [m]<\/script> and all <script type=\"math\/tex;\">t\\le T<\/script>, then <\/p>\n<div id=\"a0000000013\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\textstyle \\textrm{E}\\Big[\\, {\\min _{j\\in [m]}}\\,  \\sum _{t=1}^T x^j_t\\, \\Big] ~ \\ge ~  (1-\\varepsilon )\\textrm{E}\\big[\\sum _{t=1}^T y_t\\big] \\, -\\,  \\varepsilon ^{-1}\\ln m. ~ ~   <\/script><\/div>\n<\/div><\/div>\n<p>The constants in the bounds 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=\"a0000000014\">Proof of Lemma\u00a02<\/h1>\n<div class=\"expandable\" id=\"a0000000015\" 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> <em>(c)<\/em> Define <script type=\"math\/tex;\">X^j_t = \\sum _{i=1}^t x^j_i<\/script> and <script type=\"math\/tex;\">\\phi _t ~ =~  \\log _{1+\\varepsilon } \\sum _{j=1}^m \\big(1+\\varepsilon \\big)^{X^j_t} <\/script>. <\/p>\n<p>Note that <script type=\"math\/tex;\">\\phi _T<\/script> is an upper bound on the maximum sum: <script type=\"math\/tex;\"> \\max _{j\\in [m]} X^j_T ~ \\le ~  \\phi _T. <\/script> <\/p>\n<p>Observe that <script type=\"math\/tex;\">\\phi <\/script> increases by at most <script type=\"math\/tex;\">(1+\\varepsilon )\\textrm{E}[y_t]<\/script> in expectation in step <script type=\"math\/tex;\">t<\/script>. Indeed, letting <script type=\"math\/tex;\">\\omega _j = (1+\\varepsilon )^{X^j_{t-1}}<\/script>, using <script type=\"math\/tex;\">x^j_t \\in [0,1]<\/script> and <script type=\"math\/tex;\">\\log _{1+\\varepsilon }(1+\\varepsilon z) \\le (1+\\varepsilon ) z<\/script>, <\/p>\n<div id=\"a0000000016\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\phi _{t} - \\phi _{t-1} ~ =~  \\log _{1+\\varepsilon }\\frac{\\sum _j (1+\\varepsilon )^{x^t_j}\\omega _j}{\\sum _j \\omega _j} ~ \\le ~  \\log _{1+\\varepsilon }\\frac{\\sum _j (1+\\varepsilon x^t_j)\\omega _j}{\\sum _j \\omega _j}  <\/script><\/div>\n<div id=\"eq:3\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation}  \\label{eq:3} ~ =~  \\log _{1+\\varepsilon } \\Big( 1 + \\varepsilon \\frac{\\sum _j x^j_t\\omega _j}{\\sum _j \\omega _j}\\Big) ~ \\le ~  (1+\\varepsilon )\\frac{\\sum _j x^j_t\\omega _j}{\\sum _j \\omega _j}, \\end{equation}<\/script><\/div>\n<p> and, given <script type=\"math\/tex;\">S_{t-1}<\/script>, the expectation of <script type=\"math\/tex;\">x^j_t<\/script> for each <script type=\"math\/tex;\">j\\in [m]<\/script> is at most <script type=\"math\/tex;\">\\textrm{E}[y_t]<\/script>, so by linearity of expectation, the expectation of <script type=\"math\/tex;\">\\phi _{t}-\\phi _{t-1}<\/script> given <script type=\"math\/tex;\">S_{t-1}<\/script> is at most <script type=\"math\/tex;\">(1+\\varepsilon )\\textrm{E}[y_t]<\/script>. <\/p>\n<p>Hence <script type=\"math\/tex;\">\\phi _t - (1+\\varepsilon )Y_t<\/script> is a super-martingale, and by Wald\u2019s equation, <script type=\"math\/tex;\">\\textrm{E}[\\phi _T - (1+\\varepsilon )Y_T] ~ \\le ~ \\phi _0<\/script>, which, by calculation, proves part (c). <\/p>\n<p>(d) Given the state <script type=\"math\/tex;\">S_t<\/script> after <script type=\"math\/tex;\">t<\/script> samples, define <script type=\"math\/tex;\">\\phi _t ~ =~  \\log _{1-\\varepsilon } \\sum _{j=1}^n \\big(1-\\varepsilon \\big)^{ X^j_t}. <\/script> Then <script type=\"math\/tex;\">\\phi _T<\/script> is a lower bound on the minimum sum, and <script type=\"math\/tex;\">\\phi <\/script> increases by at least <script type=\"math\/tex;\">(1-\\varepsilon )\\textrm{E}[y_t]<\/script> in expectation in the <script type=\"math\/tex;\">t<\/script>th step. Indeed, letting <script type=\"math\/tex;\">\\omega _j = (1-\\varepsilon )^{X^j_{t-1}}<\/script>, using <script type=\"math\/tex;\">x^j_t \\in [0,1]<\/script> and <script type=\"math\/tex;\">\\log _{1-\\varepsilon }(1-\\varepsilon z) \\ge (1-\\varepsilon ) z<\/script>, <\/p>\n<div id=\"a0000000017\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\phi _{t} - \\phi _{t-1} ~ =~  \\log _{1-\\varepsilon }\\frac{\\sum _j (1-\\varepsilon )^{x^t_j}\\omega _j}{\\sum _j \\omega _j} ~ \\ge ~  \\log _{1-\\varepsilon }\\frac{\\sum _j (1-\\varepsilon x^t_j)\\omega _j}{\\sum _j \\omega _j}  <\/script><\/div>\n<div id=\"eq:4\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation}  \\label{eq:4} ~ =~  \\log _{1-\\varepsilon } \\Big( 1 - \\varepsilon \\frac{\\sum _j x^j_t\\omega _j}{\\sum _j \\omega _j}\\Big) ~ \\ge ~  (1-\\varepsilon )\\frac{\\sum _j x^j_t\\omega _j}{\\sum _j \\omega _j}, \\end{equation}<\/script><\/div>\n<p> and, given <script type=\"math\/tex;\">S_{t-1}<\/script>, the expectation of <script type=\"math\/tex;\">x^j_t<\/script> for each <script type=\"math\/tex;\">j\\in [m]<\/script> is at least <script type=\"math\/tex;\">\\textrm{E}[y_t]<\/script>, so the expectation of <script type=\"math\/tex;\">\\phi _{t}-\\phi _{t-1}<\/script> given <script type=\"math\/tex;\">S_{t-1}<\/script> is at least <script type=\"math\/tex;\">(1-\\varepsilon )\\textrm{E}[y_t]<\/script>. <\/p>\n<p>By Wald\u2019s equation, <script type=\"math\/tex;\">\\textrm{E}[\\phi _T - (1-\\varepsilon )\\sum _{t=1}^T y_t] ~ \\ge ~ \\phi _0<\/script>, which, by calculation, proves part (d). <\/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=\"a0000000018\">Some pessimistic estimators for the bound (c)<\/h1>\n<p>(Right now we\u2019ve just recorded pessimistic estimators for (c). We\u2019ll add the rest here as needed.) <\/p>\n<p>The bound (c) relates <script type=\"math\/tex;\">\\max _{j\\in [m]} \\sum _{t=1}^T x_j^t<\/script> and <script type=\"math\/tex;\">\\sum _{t=1}^T y_t<\/script>. In a typical use of bound (c), we know a bound on one of the two quantities, and we use (c) to bound the expectation of the other. We start with pessimistic estimators for these two cases. Let <script type=\"math\/tex;\">X^j_t = \\sum _{i=1}^t x^j_i<\/script>. Let <script type=\"math\/tex;\">Y_t = \\sum _{i=1}^t y_i<\/script>. <\/p>\n<ol class=\"enumerate\">\n<li value=\"1\">\n<p>Consider first the case that we start with an upper bound <script type=\"math\/tex;\">Y_T \\le U<\/script>, and we use (c) to upper bound <script type=\"math\/tex;\">\\textrm{E}[\\max _{j\\in [m]} X^j_T]<\/script> by <script type=\"math\/tex;\">(1+\\varepsilon )(U + \\varepsilon ^{-1}\\ln m)<\/script>. <\/p>\n<p>Given the outcomes of the first <script type=\"math\/tex;\">t<\/script> iterations (in particular, values of <script type=\"math\/tex;\">Y_t<\/script> and <script type=\"math\/tex;\">X^j_t<\/script> for all <script type=\"math\/tex;\">j<\/script>) the following pessimistic estimator for the conditional expectation of <script type=\"math\/tex;\">\\textrm{E}[\\max _{j\\in [m]} X^j_T]<\/script> is implicit in the proof of (c): <\/p>\n<div id=\"pe:c:U\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{pe:c:U}\\textstyle \\psi _t ~ =~  \\phi _t + (1+\\varepsilon )(U - Y_t) ~ =~  \\log _{1+\\varepsilon }\\sum _{j=1}^m (1+\\varepsilon )^{X_t} ~ ~ +~  (1+\\varepsilon )(U - Y_t). \\end{equation}<\/script><\/div>\n<p> The initial value <script type=\"math\/tex;\">\\psi _0<\/script> is less than <script type=\"math\/tex;\">(1+\\varepsilon )(U + \\varepsilon ^{-1}\\ln m)<\/script>, as desired. The final value <script type=\"math\/tex;\">\\psi _T<\/script> is an upper bound on the maximum in question (given <script type=\"math\/tex;\">Y_T\\le U<\/script>). In a given iteration, letting <script type=\"math\/tex;\">\\omega _j = (1+\\varepsilon )^{X^j_t}<\/script>, the increase <script type=\"math\/tex;\">\\psi _t-\\psi _{t-1}<\/script> is at most <\/p>\n<div id=\"pe:c:U:delta\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{pe:c:U:delta}\\textstyle (1+\\varepsilon ) \\sum _j x^j_t \\omega _j\/\\sum _j \\omega _j ~ -~  (1+\\varepsilon )y_t, \\end{equation}<\/script><\/div>\n<p> which, in expectation is non-positive. <\/p>\n<\/li>\n<li value=\"2\">\n<p>Consider next the case that we start with a lower bound <script type=\"math\/tex;\">L \\le \\max _{j\\in [m]} X^j_T<\/script> on the maximum, and we use (c) to lower bound <script type=\"math\/tex;\">\\textrm{E}[Y_T]<\/script> by <script type=\"math\/tex;\">(1+\\varepsilon )^{-1} L - \\varepsilon ^{-1}\\ln m<\/script>. <\/p>\n<p>Given the outcomes of the first <script type=\"math\/tex;\">t<\/script> iterations (in particular, values of <script type=\"math\/tex;\">Y_t<\/script> and <script type=\"math\/tex;\">X^j_t<\/script> for all <script type=\"math\/tex;\">j<\/script>), the following pessimistic estimator for the conditional expectation of <script type=\"math\/tex;\">\\textrm{E}[Y_T]<\/script> is implicit in the proof of (c): <\/p>\n<div id=\"pe:c:L\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{pe:c:L}\\textstyle \\psi _t ~ =~  Y_t + (1+\\varepsilon )^{-1}(L - \\log _{1+\\varepsilon }\\sum _{j=1}^m (1+\\varepsilon )^{X_t}). \\end{equation}<\/script><\/div>\n<p> The initial value <script type=\"math\/tex;\">\\psi _0<\/script> is more than <script type=\"math\/tex;\">(1+\\varepsilon )^{-1}L - \\varepsilon ^{-1}\\ln m<\/script>, as desired. The final value <script type=\"math\/tex;\">\\psi _T<\/script> is a lower bound on <script type=\"math\/tex;\">Y_T<\/script> (given that the maximum is at least <script type=\"math\/tex;\">L<\/script>). In a given iteration, letting <script type=\"math\/tex;\">\\omega _j = (1+\\varepsilon )^{X^j_t}<\/script>, the increase <script type=\"math\/tex;\">\\psi _t-\\psi _{t-1}<\/script> is at least <\/p>\n<div id=\"pe:c:L:delta\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{pe:c:L:delta}\\textstyle y_t - \\sum _j x^j_t \\omega _j\/\\sum _j \\omega _j, \\end{equation}<\/script><\/div>\n<p> which, in expectation is non-negative. <\/p>\n<\/li>\n<li value=\"3\">\n<p>Or, it may be the case that we have no a-priori upper bound <script type=\"math\/tex;\">U<\/script> or lower bound <script type=\"math\/tex;\">L<\/script>. Rather, we simply want an outcome where the inequality in (c) holds: <script type=\"math\/tex;\">\\max _{j\\in [m]} X^j_t \\le (1+\\varepsilon ) (Y_T + \\varepsilon ^{-1} \\ln m)<\/script>. In that case, we can use the pessimistic estimator <\/p>\n<div id=\"pe:c\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{pe:c}\\textstyle \\psi _t ~ =~  \\log _{1+\\varepsilon } \\sum _j (1+\\varepsilon )^{X^j_t} ~ ~ -~  (1+\\varepsilon ) (Y_t + \\varepsilon ^{-1}\\ln m). \\end{equation}<\/script><\/div>\n<p> It is initially negative. If its final value is at most 0, then the desired inequality holds. In a given iteration, the increase <script type=\"math\/tex;\">\\psi _{t} - \\psi _{t-1}<\/script> is at most Expression\u00a0\\eqref{pe:c:U:delta}, which is non-positive in expectation. <\/p>\n<\/li>\n<\/ol>\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=\"a0000000019\">Related<\/h1>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/expected-deviation\">Expected deviation of a single sum from a threshold<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div><\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Bounds on the expected maximum (or minimum) among a collection of sums. It can be technically convenient to work with expectations directly, instead of working with probabilities. Here, given a collection of sums of 0\/1 random variables, we bound the expected maximum (or minimum) sum in the collection. For example, suppose Alice throws balls randomly [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":5735,"menu_order":5,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-5684","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/5684","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=5684"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/5684\/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=5684"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}