{"id":911,"date":"2010-04-06T02:44:21","date_gmt":"2010-04-06T10:44:21","guid":{"rendered":"http:\/\/obliviousrounding.com\/blog\/?p=911"},"modified":"2026-09-29T12:22:10","modified_gmt":"2026-09-29T20:22:10","slug":"method-of-conditional-probabilities","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/probabilistic-method\/method-of-conditional-probabilities\/","title":{"rendered":"method of conditional probabilities (Max Cut)"},"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>The method of conditional probabilities converts a probabilistic existence proof into a deterministic algorithm.<\/em><\/center><\/p><\/blockquote>\n<p>  The method of conditional probabilities is a systematic method for converting non-constructive probabilistic existence proofs into efficient deterministic algorithms that explicitly construct the desired object.<!--more--><\/p>\n<p><div style=\"margin:0pt;padding:0pt;margin-bottom:12px\"><\/div>\n<\/p>\n<hr \/>\n<p><div class=\"expandable\" id=\"a0000000002\" tabindex=\"10\" onclick=\"setTimeout(function(){MathJax.Hub.Queue([&#x27;Rerender&#x27;,MathJax.Hub,&#x27;a0000000002&#x27;])},100); return true;\"><span class=\"collapseomatic highlight\" id=\"id6abcb9bde7428\"  tabindex=\"0\" title=\"Click for background material\u2026\"    >Click for background material\u2026<\/span><div id=\"target-id6abcb9bde7428\" class=\"collapseomatic_content \">\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/probabilistic-method\">The probabilistic method<\/a> and\/or <a href=\"http:\/\/algnotes.info\/on\/randomized-rounding\">randomized rounding<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div><\/div>\n<\/p>\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\"><span id=\"Description\">Description<\/span><\/h1>\n<p> Raghavan (1988) gives this description of the method: <\/p>\n<blockquote class=\"quote\"><p><em> We first show the <em>existence<\/em> of a provably good approximate solution using the probabilistic method\u00a0<span class=\"cite\">[<a href=\"#Alon92Probabilistic\">1<\/a>]<\/span>. [We then] show that the probabilistic existence proof can be converted, in a very precise sense, into a deterministic approximation algorithm. To this end we use an interesting \u201cmethod of conditional probabilities\u201d\u2026We apply our method to integer programs arising in packing, routing, and maximum multicommodity flow\u2026\u00a0<span class=\"cite\">[<a href=\"#Raghavan88Probabilistic\">2<\/a>]<\/span><\/em> <\/p><\/blockquote>\n<p> (Raghavan is discussing the method in the context of randomized rounding, but it works with the probabilistic method in general.) <\/p>\n<p>To derive a constructive algorithm from a random experiment, one first casts the random experiment as a series of \u201csmall\u201d random choices, then modifies the random process, replacing each small random choice by a deterministic choice, chosen so as to <em>keep the current conditional probability of failure (given the choices made so far) below 1.<\/em> <\/p>\n<p><center> <img decoding=\"async\" src=\"http:\/\/algnotes.info\/b\/wp-content\/uploads\/2011\/02\/img-00013.png\" alt=\"\\includegraphics[type=pdf,ext=.pdf,read=.pdf,width=5.5in]{shared\/graphics\/method_of_conditional_probabilities_2}\" style=\"width:5.5in\" class=\"zoooom\" \/> <\/center><\/div>\n<\/p><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000004\"><span id=\"Trivial_example_flipping_three_coins\">Trivial example: flipping three coins<\/span><\/h1>\n<p> Here is a toy example to illustrate the principle. <\/p>\n<div id=\"a0000000005\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b \"=\"&quot;\">Lemma.<\/b>   <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>It is possible to flip three coins so that the number of tails is at least 2. <\/p>\n<\/div><\/div>\n<div id=\"a0000000006\" 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>If the three coins are flipped randomly, the expected number of tails is 1.5. Thus, there must be some outcome (way of flipping the coins) so that the number of tails is at least 1.5. Since the number of tails is an integer, in such an outcome there are at least 2 tails. <\/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<p>In this example the random experiment consists of flipping three fair coins. The experiment is illustrated by the rooted tree in the diagram. There are eight outcomes, each corresponding to a leaf in the tree. A trial of the random experiment corresponds to taking a random walk from the root (the top node in the tree, where no coins have been flipped) to a leaf. The successful outcomes are those in which at least two coins came up tails. The interior nodes in the tree correspond to partially determined outcomes, where only 0, 1, or 2 of the coins have been flipped so far. <\/p>\n<p>To apply the method of conditional probabilities, one focuses on the conditional probability of failure, given the choices so far as the experiment proceeds step by step. <\/p>\n<p>In the diagram, each node is labeled with this conditional probability. (For example, if only the first coin has been flipped, and it comes up tails, that corresponds to the second child of the root. Conditioned on that partial state, the probability of failure is 0.25.) <\/p>\n<p>We replace the random root-to-leaf walk by a deterministic walk to a leaf labeled 0. <\/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=\"a0000000007\"><span id=\"General_description\">General description<\/span><\/h1>\n<p> In general, it is always possible to replace each random step by a deterministic step to maintain the invariant that the conditional probability of failure, given the current state, is less than 1. The invariant holds initially (at the root), because the original proof showed that the (unconditioned) probability of failure is less than 1. At any interior node whose probability of failure is less than 1, because the probability at that node is a weighted average of the probabilities at the children, there is at least one child to choose that also has probability of failure less than 1. By maintaining the invariant until the end (when the walk arrives at a leaf), the outcome reached must be successful. <\/p>\n<p>In practice, there are various ways to make each choice to keep the conditional probability of failure below 1. Often, the exact conditional probability of failure is hard to compute. Instead one keeps <em>an upper bound<\/em> on the conditional probability of failure below 1, which suffices. Or, it may suffice to keep the conditional expectation of some other quantity above or below a certain threshold. (See the discussion of <a href=\"http:\/\/algnotes.info\/on\/pessimistic-estimators\">pessimistic estimators<\/a>.) <\/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=\"a0000000008\"><span id=\"Example_derandomizing_the_Max-Cut_existence_proof\">Example: derandomizing the Max-Cut existence proof<\/span><\/h1>\n<p> Here is how the method of conditional probabilities works for the Max-Cut example in <a href=\"http:\/\/algnotes.info\/on\/probabilistic-method\">the note on the probabilistic method<\/a>. That proof shows that for a randomly chosen cut, the number of edges in the graph <script type=\"math\/tex;\">G=(V,E)<\/script><span class=\"MathJax_Preview\">G=(V,E)<\/span> that are cut is <script type=\"math\/tex;\">|E|\/2<\/script><span class=\"MathJax_Preview\">|E|\/2<\/span> in expectation. Thus, the probability of cutting fewer than <script type=\"math\/tex;\">|E|\/2<\/script><span class=\"MathJax_Preview\">|E|\/2<\/span> edges is less than 1. <\/p>\n<p>Let random variable <script type=\"math\/tex;\">Q<\/script><span class=\"MathJax_Preview\">Q<\/span> be the number of edges cut. The algorithm will emulate the random experiment, coloring the vertices one by one. To keep the conditional probability of failure (<script type=\"math\/tex;\">Q \\lt |E|\/2<\/script><span class=\"MathJax_Preview\">Q \\lt |E|\/2<\/span>) below 1, the algorithm will keep the conditional expectation of <script type=\"math\/tex;\">Q<\/script><span class=\"MathJax_Preview\">Q<\/span> at or above <script type=\"math\/tex;\">|E|\/2<\/script><span class=\"MathJax_Preview\">|E|\/2<\/span>. To do this, it will simply color each vertex to keep the conditional expectation of <script type=\"math\/tex;\">Q<\/script><span class=\"MathJax_Preview\">Q<\/span> from decreasing. (Here, the \u201cconditional expectation\u201d refers to the expectation <em> if<\/em> the remaining vertices were to be colored randomly, even though the algorithm will end up coloring them deterministically.) <\/p>\n<p>So what is the conditional expectation of <script type=\"math\/tex;\">Q<\/script><span class=\"MathJax_Preview\">Q<\/span>? Suppose the first <script type=\"math\/tex;\">t<\/script><span class=\"MathJax_Preview\">t<\/span> vertices have been colored. Let <script type=\"math\/tex;\">S_t<\/script><span class=\"MathJax_Preview\">S_t<\/span> denote the state (first <script type=\"math\/tex;\">t<\/script><span class=\"MathJax_Preview\">t<\/span> vertex colors). Each edge that already has both endpoints colored differently will definitely be cut; let <script type=\"math\/tex;\">c(S_t)<\/script><span class=\"MathJax_Preview\">c(S_t)<\/span> denote the number of these edges. Each edge that already has both endpoints colored the same will definitely not be cut. Each other edge has at least one undetermined endpoint and has a 1\/2 chance of being cut; let <script type=\"math\/tex;\">u(S_t)<\/script><span class=\"MathJax_Preview\">u(S_t)<\/span> denote the number of these edges. Thus, the conditional expectation of <script type=\"math\/tex;\">Q<\/script><span class=\"MathJax_Preview\">Q<\/span> given <script type=\"math\/tex;\">S_t<\/script><span class=\"MathJax_Preview\">S_t<\/span>, that is, <script type=\"math\/tex;\">E[Q \\, |\\, S_t]<\/script><span class=\"MathJax_Preview\">E[Q \\, |\\, S_t]<\/span>, is <script type=\"math\/tex;\">c(S_t)+u(S_t)\/2<\/script><span class=\"MathJax_Preview\">c(S_t)+u(S_t)\/2<\/span> \u2014 the number of edges cut so far plus half the undetermined edges. <\/p>\n<p>To color the <script type=\"math\/tex;\">t+1<\/script><span class=\"MathJax_Preview\">t+1<\/span>st vertex, say <script type=\"math\/tex;\">v<\/script><span class=\"MathJax_Preview\">v<\/span>, the algorithm computes the conditional expectation <script type=\"math\/tex;\">(\\textrm{E}[Q \\, |\\, S_{t+1}] = c(S_{t+1})+u(S_{t+1})\/2)<\/script><span class=\"MathJax_Preview\">(\\textrm{E}[Q \\, |\\, S_{t+1}] = c(S_{t+1})+u(S_{t+1})\/2)<\/span> that would result from coloring <script type=\"math\/tex;\">v<\/script><span class=\"MathJax_Preview\">v<\/span> red and compares that to the conditional expectation that would result from coloring <script type=\"math\/tex;\">v<\/script><span class=\"MathJax_Preview\">v<\/span> blue. <em> One of these two choices will give a conditional expectation at least as large as the current one <script type=\"math\/tex;\">\\textrm{E}[Q \\, |\\, S_t]<\/script><span class=\"MathJax_Preview\">\\textrm{E}[Q \\, |\\, S_t]<\/span>.<\/em> (This is because the current conditional expectation is the average of the two possible next conditional expectations.) The algorithm colors <script type=\"math\/tex;\">v<\/script><span class=\"MathJax_Preview\">v<\/span> whichever way maximizes <script type=\"math\/tex;\">\\textrm{E}[Q \\, |\\, S_{t+1}]<\/script><span class=\"MathJax_Preview\">\\textrm{E}[Q \\, |\\, S_{t+1}]<\/span>, guaranteeing that <script type=\"math\/tex;\">\\textrm{E}[Q \\, |\\, S_{t+1}] \\ge \\textrm{E}[Q\\, |\\, S_t]<\/script><span class=\"MathJax_Preview\">\\textrm{E}[Q \\, |\\, S_{t+1}] \\ge \\textrm{E}[Q\\, |\\, S_t]<\/span>. <\/p>\n<p>More concretely, this algorithm reduces to the following: <em> Consider the vertices in any order. When considering a vertex <script type=\"math\/tex;\">v<\/script><span class=\"MathJax_Preview\">v<\/span>, color it red if among its colored neighbors, more are blue then red. Otherwise color it blue.<\/em> <\/p>\n<p>Since the algorithm maintains the invariant <script type=\"math\/tex;\">\\textrm{E}[Q \\, |\\, S_{t+1}] \\ge |E|\/2<\/script><span class=\"MathJax_Preview\">\\textrm{E}[Q \\, |\\, S_{t+1}] \\ge |E|\/2<\/span>, it maintains the invariant that the conditional probability of failure is less than 1. Thus, it is guaranteed to succeed (cut at least half the edges). <\/p>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000009\"><span id=\"Wikipedia\">Wikipedia<\/span><\/h2>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/method_of_conditional_probabilities\">The method of conditional probabilities<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<div>\n<h1 id=\"bibliography\"><span id=\"Bibliography\">Bibliography<\/span><\/h1>\n<table class=\"bibliography\" cellspacing=\"0\" cellpadding=\"2\">\n<tr>\n<td valign=\"top\">[<a name=\"Alon92Probabilistic\">1<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;N+Alon+&quot;+author:&quot;+J+H++Spencer&quot;+intitle:&quot;+The+Probabilistic+Method&quot;\">N.\u00a0Alon and J.\u00a0H. Spencer. <em>The Probabilistic Method<\/em>. John Wiley and Sons, New York, 1992. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Raghavan88Probabilistic\">2<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;P+Raghavan&quot;+intitle:&quot;+Probabilistic+construction+of+deterministic+algorithms+approximating+packing+integer+programs&quot;\">P.\u00a0Raghavan. Probabilistic construction of deterministic algorithms approximating packing integer programs. <em>J. Computer System Sciences<\/em>, 37(2):130\u2013143, Oct. 1988. <\/a><\/td>\n<\/tr>\n<\/table><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>The method of conditional probabilities converts a probabilistic existence proof into a deterministic algorithm. The method of conditional probabilities is a systematic method for converting non-constructive probabilistic existence proofs into efficient deterministic algorithms that explicitly construct the desired object.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":901,"menu_order":3,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/911"}],"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=911"}],"version-history":[{"count":1,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/911\/revisions"}],"predecessor-version":[{"id":8943,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/911\/revisions\/8943"}],"up":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/901"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=911"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}