{"id":5735,"date":"2013-11-25T12:09:21","date_gmt":"2013-11-25T20:09:21","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=5735"},"modified":"2023-09-14T17:14:50","modified_gmt":"2023-09-15T01:14:50","slug":"stopping-times","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/stopping-times\/","title":{"rendered":"Bounds related to random stopping times"},"content":{"rendered":"<div class=\"latex-file\">\n<div class=\"latex-document\">\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000002\">Links to notes on bounds related to random stopping times<\/h1>\n<div class=\"ccchildpages\"><article class=\"hentry ccchildpage\">\r\n<header class=\"entry-header\">\r\n<h1 class=\"entry-title\">\r\n<a href=\"https:\/\/algnotes.info\/on\/background\/stopping-times\/walds\/\" class=\"\">Wald\u2019s equation<\/a>\r\n<\/h1>\r\n<\/header>\r\n<div class=\"entry-summary\">\r\n<div class=\"latex-file\"><div class=\"latex-document\"> <div class=\"latex-outer-sheet\"><div class=\"latex-inner-sheet\"> <p><blockquote class=\"quote\"><center><em>Wald\u2019s equation, a form of linearity of expectation for sums with randomly many terms.<\/em><\/center><\/blockquote><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.\r\n<!--- a href=\"https:\/\/algnotes.info\/on\/background\/stopping-times\/walds\/\" class=\"\">More...<\/a --->\r\n<\/div>\r\n<footer class=\"entry-meta\">\r\n<\/footer>\r\n<\/article><article class=\"hentry ccchildpage\">\r\n<header class=\"entry-header\">\r\n<h1 class=\"entry-title\">\r\n<a href=\"https:\/\/algnotes.info\/on\/background\/stopping-times\/walds-dependent\/\" class=\"\">Wald\u2019s equation for dependent increments<\/a>\r\n<\/h1>\r\n<\/header>\r\n<div class=\"entry-summary\">\r\n<div class=\"latex-file\"><div class=\"latex-document\"> <div class=\"latex-outer-sheet\"><div class=\"latex-inner-sheet\"> <p><blockquote class=\"quote\"><center><em>A variant of Wald\u2019s equation to use when the expected increment depends on the sum so far.<\/em><\/center><\/blockquote>  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?\r\n<!--- a href=\"https:\/\/algnotes.info\/on\/background\/stopping-times\/walds-dependent\/\" class=\"\">More...<\/a --->\r\n<\/div>\r\n<footer class=\"entry-meta\">\r\n<\/footer>\r\n<\/article><article class=\"hentry ccchildpage\">\r\n<header class=\"entry-header\">\r\n<h1 class=\"entry-title\">\r\n<a href=\"https:\/\/algnotes.info\/on\/background\/stopping-times\/markov-for-supermartingales\/\" class=\"\">Markov bound for super-martingales<\/a>\r\n<\/h1>\r\n<\/header>\r\n<div class=\"entry-summary\">\r\n<div class=\"latex-file\"><div class=\"latex-document\"> <div class=\"latex-outer-sheet\"><div class=\"latex-inner-sheet\"> <p><blockquote class=\"quote\"><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><\/blockquote><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><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.\r\n<!--- a href=\"https:\/\/algnotes.info\/on\/background\/stopping-times\/markov-for-supermartingales\/\" class=\"\">More...<\/a --->\r\n<\/div>\r\n<footer class=\"entry-meta\">\r\n<\/footer>\r\n<\/article><article class=\"hentry ccchildpage\">\r\n<header class=\"entry-header\">\r\n<h1 class=\"entry-title\">\r\n<a href=\"https:\/\/algnotes.info\/on\/background\/stopping-times\/stopping-time-chernoff\/\" class=\"\">\u201cStopping-time\u201d Chernoff bounds<\/a>\r\n<\/h1>\r\n<\/header>\r\n<div class=\"entry-summary\">\r\n<div class=\"latex-file\"><div class=\"latex-document\"> <div class=\"latex-outer-sheet\"><div class=\"latex-inner-sheet\"> <p><blockquote class=\"quote\"><center><em>Extending the Chernoff bound to handle sums with randomly many terms.<\/em><\/center><\/blockquote>  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>.\r\n<!--- a href=\"https:\/\/algnotes.info\/on\/background\/stopping-times\/stopping-time-chernoff\/\" class=\"\">More...<\/a --->\r\n<\/div>\r\n<footer class=\"entry-meta\">\r\n<\/footer>\r\n<\/article><article class=\"hentry ccchildpage\">\r\n<header class=\"entry-header\">\r\n<h1 class=\"entry-title\">\r\n<a href=\"https:\/\/algnotes.info\/on\/background\/stopping-times\/expected-maximum-sum\/\" class=\"\">Expected maximum (or minimum) of many sums<\/a>\r\n<\/h1>\r\n<\/header>\r\n<div class=\"entry-summary\">\r\n<div class=\"latex-file\"><div class=\"latex-document\"> <div class=\"latex-outer-sheet\"><div class=\"latex-inner-sheet\"> <p><blockquote class=\"quote\"><center><em>Bounds on the expected maximum (or minimum) among a collection of sums.<\/em><\/center><\/blockquote><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><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><p>The bound differs from Chernoff in a few ways: <\/p><ul class=\"itemize\"> <li><p>it bounds the expected maximum or minimum (as opposed to the probability of a large deviation), <\/p><\/li><li><p>the sums can have randomly many terms, so they don\u2019t have to be concentrated around their means. <\/p><\/li> <\/ul><p>\r\n<!--- a href=\"https:\/\/algnotes.info\/on\/background\/stopping-times\/expected-maximum-sum\/\" class=\"\">More...<\/a --->\r\n<\/div>\r\n<footer class=\"entry-meta\">\r\n<\/footer>\r\n<\/article><article class=\"hentry ccchildpage\">\r\n<header class=\"entry-header\">\r\n<h1 class=\"entry-title\">\r\n<a href=\"https:\/\/algnotes.info\/on\/background\/stopping-times\/expected-deviation\/\" class=\"\">Expected deviation of a sum<\/a>\r\n<\/h1>\r\n<\/header>\r\n<div class=\"entry-summary\">\r\n<div class=\"latex-file\"><div class=\"latex-document\"> <div class=\"latex-outer-sheet\"><div class=\"latex-inner-sheet\"> <p><blockquote class=\"quote\"><center><em>Bounds on the expected deviation of a sum from a threshold.<\/em><\/center><\/blockquote><p>  Here are bounds on the expected deviation of a sum of 0\/1-random variables above or below some threshold (typically near its mean). <\/p><p>For example, suppose Alice flips a fair coin <script type=\"math\/tex;\">n<\/script> times. She pays Bob $1 for each head after the first <script type=\"math\/tex;\">(1+\\varepsilon )n\/2<\/script> heads (if any). What is her expected payment to Bob? The bounds here say: at most <script type=\"math\/tex;\">\\varepsilon ^{-1} \\exp (-\\varepsilon ^2 n\/6)<\/script>. For example, if <script type=\"math\/tex;\">\\varepsilon =\\Omega (1\/\\sqrt n)<\/script>, the expected payment is <script type=\"math\/tex;\">O(\\sqrt n)<\/script>. If <script type=\"math\/tex;\">\\varepsilon =\\sqrt{6c\\ln (n)\/n}<\/script>, the expected payment is <script type=\"math\/tex;\">O(1\\, \/\\, n^{c-1}\\sqrt{\\ln n})<\/script>. In general the expectation is about <script type=\"math\/tex;\">\\varepsilon ^{-1}<\/script> times the probability (according to Chernoff) that the sum exceeds its mean by a factor of <script type=\"math\/tex;\">1+\\varepsilon <\/script>.\r\n<!--- a href=\"https:\/\/algnotes.info\/on\/background\/stopping-times\/expected-deviation\/\" class=\"\">More...<\/a --->\r\n<\/div>\r\n<footer class=\"entry-meta\">\r\n<\/footer>\r\n<\/article><\/div>\n<\/div><\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Links to notes on bounds related to random stopping times<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8676,"menu_order":2,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-5735","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/5735","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=5735"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/5735\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8676"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=5735"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}