{"id":3712,"date":"2018-04-13T13:15:50","date_gmt":"2018-04-13T18:15:50","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=3712"},"modified":"2019-01-28T14:32:55","modified_gmt":"2019-01-28T20:32:55","slug":"how-to-upper-bound-the-probability-of-something-bad","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=3712","title":{"rendered":"How to upper-bound the probability of something bad"},"content":{"rendered":"

Scott Alexander has a new post<\/a> decrying how rarely experts encode their knowledge in the form of detailed guidelines with conditional statements and loops—or what one could also call flowcharts or expert systems—rather than just blanket recommendations.  He gives, as an illustration of what he’s looking for, an algorithm that a psychiatrist might use to figure out which antidepressants or other treatments will work for a specific patient—with the huge proviso that you shouldn’t try his algorithm at home, or (most importantly) sue him if it doesn’t work.<\/p>\n

Compared to a psychiatrist, I have the huge advantage that if my<\/em> professional advice fails, normally no one gets hurt or gets sued for malpractice or commits suicide or anything like that.  OK, but what do I actually know that can be encoded in if-thens?<\/p>\n

Well, one of the commonest tasks in the day-to-day life of any theoretical computer scientist, or mathematician of the Erd\u00f6s flavor, is to upper bound the probability that something bad will happen<\/em>: for example, that your randomized algorithm or protocol will fail, or that your randomly constructed graph or code or whatever it is won’t have the properties needed for your proof.<\/p>\n

So without further ado, here are my secrets revealed, my ten-step plan to probability-bounding and computer-science-theorizing success.<\/p>\n

Step 1.<\/strong> “1” is definitely an upper bound on the probability of your bad event happening.  Check whether that upper bound is good enough.  (Sometimes, as when this is an inner step in a larger summation over probabilities, the answer will actually be yes.)<\/p>\n

Step 2.<\/strong> Try using Markov\u2019s inequality<\/a> (a nonnegative random variable exceeds its mean by a factor of k at most a 1\/k fraction of the time), combined with its close cousin in indispensable obviousness, the union bound<\/a> (the probability that any of several bad events will happen, is at most the sum of the probabilities of each bad event individually).  About half the time, you can stop right here.<\/p>\n

Step 3.<\/strong> See if the bad event you\u2019re worried about involves a sum of independent random variables exceeding some threshold. If it does, hit that sucker with a Chernoff<\/a> or Hoeffding<\/a> bound.<\/p>\n

Step 4.<\/strong> If your random variables aren’t independent, see if they at least form a martingale<\/a>: a fancy word for a sum of terms, each of which has a mean of 0 conditioned on all the earlier terms, even though it might depend on the earlier terms in subtler ways.  If so, Azuma<\/a> your problem into submission.<\/p>\n

Step 5.<\/strong> If you don\u2019t have a martingale, but you still feel like your random variables are only weakly correlated, try calculating the variance<\/a> of whatever combination of variables you care about, and then using Chebyshev\u2019s inequality<\/a>: the probability that a random variable differs from its mean by at most k times the standard deviation (i.e., the square root of the variance) is at most 1\/k2<\/sup>.  If the variance doesn’t work, you can try calculating some higher moments too—just beware that, around the 6th<\/sup> or 8th<\/sup> moment, you and your notebook paper will likely both be exhausted.<\/p>\n

Step 6.<\/strong> OK, umm … see if you can upper-bound the variation distance<\/a> between your probability distribution and a different distribution for which it\u2019s already known (or is easy to see) that it\u2019s unlikely that anything bad happens. A good example of a tool you can use to upper-bound variation distance is Pinsker\u2019s inequality<\/a>.<\/p>\n

Step 7.<\/strong> Now is the time when you start ransacking Google and Wikipedia for things like the Lov\u00e1sz Local Lemma<\/a>, and concentration bounds for low-degree polynomials<\/a>, and H\u00f6lder’s inequality<\/a>, and Talagrand’s inequality<\/a>, and other isoperimetric-type inequalities<\/a>, and hypercontractive inequalities<\/a>, and other stuff that you\u2019ve heard your friends rave about, and have even seen successfully used at least twice, but there\u2019s no way you\u2019d remember off the top of your head under what conditions any of this stuff applies, or whether any of it is good enough for your application. (Just between you and me: you may have already<\/em> visited Wikipedia to refresh your memory about the earlier items in this list, like the Chernoff bound.) “Try a hypercontractive inequality” is surely the analogue of the psychiatrist\u2019s \u201ctry electroconvulsive therapy,\u201d for a patient on whom all milder treatments have failed.<\/p>\n

Step 8.<\/strong> So, these bad events … how bad are they, anyway? Any chance you can live with them?  (See also: Step 1.)<\/p>\n

Step 9.<\/strong> You can\u2019t<\/em> live with them? Then back up in your proof search tree, and look for a whole different approach or algorithm, which would make the bad events less likely or even kill them off altogether.<\/p>\n

Step 10.<\/strong> Consider the possibility that the statement you\u2019re trying to prove is false—or if true, is far beyond any existing tools.  (This might be the analogue of the psychiatrist’s: consider the possibility that evil conspirators really are<\/em> out to get your patient.)<\/p>\n","protected":false},"excerpt":{"rendered":"

Scott Alexander has a new post decrying how rarely experts encode their knowledge in the form of detailed guidelines with conditional statements and loops—or what one could also call flowcharts or expert systems—rather than just blanket recommendations.  He gives, as an illustration of what he’s looking for, an algorithm that a psychiatrist might use to […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false},"categories":[29],"tags":[],"class_list":["post-3712","post","type-post","status-publish","format-standard","hentry","category-nerd-self-help"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/3712","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3712"}],"version-history":[{"count":5,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/3712\/revisions"}],"predecessor-version":[{"id":4103,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/3712\/revisions\/4103"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3712"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3712"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3712"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}