{"id":1270,"date":"2010-04-08T20:01:06","date_gmt":"2010-04-09T04:01:06","guid":{"rendered":"http:\/\/obliviousrounding.com\/blog\/?p=1270"},"modified":"2026-09-30T09:16:40","modified_gmt":"2026-09-30T17:16:40","slug":"pessimistic-estimators","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/probabilistic-method\/pessimistic-estimators\/","title":{"rendered":"pessimistic estimators (Tur\u00e1ns theorem)"},"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>Pessimistic estimators in the method of conditional probabilities.<\/em><\/center><\/p><\/blockquote>\n<p>  In applying the method of conditional probabilities, exact conditional probabilities (or expectations) are sometimes hard to compute. Pessimistic estimators can be used instead. We illustrate the idea by example, using Tur\u00e1n\u2019s theorem.<!--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\/method-of-conditional-probabilities\">The method of conditional probabilities<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/examples\">Tur\u00e1n\u2019s theorem and proof<\/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\">Existence proof (Tur\u00e1n\u2019s theorem)<\/h1>\n<p> Recall that <a href=\"http:\/\/algnotes.info\/on\/examples\">Tur\u00e1n\u2019s theorem<\/a> states that any <script type=\"math\/tex;\">n<\/script>-vertex graph contains an independent set <script type=\"math\/tex;\">S<\/script> of size at least <script type=\"math\/tex;\">n\/(\\bar d + 1)<\/script>, where <script type=\"math\/tex;\">\\bar d<\/script> is the average degree. <\/p>\n<p>We assume familiarity with <a href=\"http:\/\/algnotes.info\/on\/examples\">the proof<\/a>. It considers the vertices in random order, taking them greedily (taking each vertex unless a neighbor has already been taken). The expected size of the resulting independent set is at least <script type=\"math\/tex;\">n\/(\\bar d+1)<\/script>, because a vertex <script type=\"math\/tex;\">v<\/script> with degree <script type=\"math\/tex;\">d_v<\/script> has at least a <script type=\"math\/tex;\">1\/(d_v+1)<\/script> chance of being taken, and <script type=\"math\/tex;\">\\sum _v 1\/(d_v+1) \\ge n\/(\\bar d + 1)<\/script>. <\/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=\"a0000000004\">Applying the method of conditional probabilities<\/h1>\n<p> To guarantee a successful outcome, instead of choosing the next vertex randomly from the remaining vertices at each step, the algorithm should choose the vertex deterministically, so as to keep the conditional expectation of the size of the final set at or above <script type=\"math\/tex;\">n\/(\\bar d + 1)<\/script>. The next step is to analyze this conditional expectation. <\/p>\n<p>If some vertex <script type=\"math\/tex;\">v<\/script> is added to the independent set at some point, then no neighbors of <script type=\"math\/tex;\">v<\/script> will be added after that. Imagine for the analysis that, when <script type=\"math\/tex;\">v<\/script> is chosen, <script type=\"math\/tex;\">v<\/script> and all its neighbors are deleted from the graph. <\/p>\n<p>Suppose that some <script type=\"math\/tex;\">t<\/script> vertices have been considered so far. Let <script type=\"math\/tex;\">S_t<\/script> contain those vertices that have been added to the independent set so far. Let <script type=\"math\/tex;\">V_t<\/script> denote the remaining (undeleted) vertices. <\/p>\n<p>All vertices in <script type=\"math\/tex;\">S_t<\/script> will of course end up in the independent set. Each vertex <script type=\"math\/tex;\">v\\in V_t<\/script> will be added to <script type=\"math\/tex;\">S<\/script> provided it is considered before any of its remaining neighbors (in <script type=\"math\/tex;\">V_t<\/script>). This will happen with probability <em>at least<\/em> <script type=\"math\/tex;\">1\/(d_v+1)<\/script>, where <script type=\"math\/tex;\">d_v<\/script> is the degree of <script type=\"math\/tex;\">v<\/script> in the original graph. (Indeed, it will happen with probability at least <script type=\"math\/tex;\">1\/(d'_v+1)<\/script>, where <script type=\"math\/tex;\">d'_v \\le d_v<\/script> is the degree in the remaining graph.) By linearity of expectation, the conditional expectation of the size <script type=\"math\/tex;\">|S|<\/script> of the final independent set <script type=\"math\/tex;\">S<\/script>, given <script type=\"math\/tex;\">S_t<\/script> and <script type=\"math\/tex;\">V_t<\/script>, is <em>at least<\/em> <\/p>\n<div id=\"a0000000005\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\Phi _t ~ =~  |S_t| + \\sum _{v\\in V_t} \\frac{1}{d_v+1}.  <\/script><\/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=\"a0000000006\">This is a pessimistic estimator<\/h1>\n<p> We\u2019ve calculated above that <script type=\"math\/tex;\">\\Phi _t<\/script> is a lower bound on the conditional expectation that we care about. To keep the conditional expectation high enough (at or above <script type=\"math\/tex;\">n\/(\\bar d + 1)<\/script>), it suffices to keep <script type=\"math\/tex;\">\\Phi _t<\/script> high enough. The original proof proved that <script type=\"math\/tex;\">\\Phi _0<\/script> is high enough. So, to keep <script type=\"math\/tex;\">\\Phi _t<\/script> high enough, it suffices to make each choice to ensure <script type=\"math\/tex;\">\\Phi _{t+1} \\ge \\Phi _t<\/script>. <\/p>\n<p>Is this always possible? That is, is there always some choice that ensures <script type=\"math\/tex;\">\\Phi _{t+1} \\ge \\Phi _t<\/script>? In this case, yes, it is. As we will verify, <script type=\"math\/tex;\">\\Phi <\/script> is a sub-martingale \u2014 in expectation, it is non-decreasing in each step: for each <script type=\"math\/tex;\">t<\/script>, the conditional expectation of <script type=\"math\/tex;\">\\Phi _{t+1}<\/script>, given the current value of <script type=\"math\/tex;\">\\Phi _t<\/script>, is at least <script type=\"math\/tex;\">\\Phi _t<\/script>. This ensures that there exists a choice that ensures <script type=\"math\/tex;\">\\Phi _{t+1} \\ge \\Phi _t<\/script>. <\/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\">Verifying the sub-martingale property<\/h1>\n<p> Since <script type=\"math\/tex;\">\\Phi _t<\/script> is not a conditional expectation per se, one has to verify that is a sub-martingale.<a href=\"#a0000000008\" class=\"footnote\"><sup class=\"footnotemark\">1<\/sup><\/a> Here, as usual, this verification is a routine calculation, reusing the calculations from the original proof. <\/p>\n<p>Suppose the first <script type=\"math\/tex;\">t<\/script> vertices have been considered. If the next vertex considered is, say <script type=\"math\/tex;\">v<\/script>, how will <script type=\"math\/tex;\">\\Phi _{t+1}<\/script> compare to <script type=\"math\/tex;\">\\Phi _t<\/script>? <\/p>\n<p>In the case that <script type=\"math\/tex;\">v<\/script> is not in <script type=\"math\/tex;\">V_t<\/script> (that is, <script type=\"math\/tex;\">v<\/script> is a neighbor of a vertex in <script type=\"math\/tex;\">S<\/script>) then <script type=\"math\/tex;\">v<\/script> is not added to <script type=\"math\/tex;\">S<\/script>, and by inspection of its definition, <script type=\"math\/tex;\">\\Phi _{t+1}=\\Phi _t<\/script>. <\/p>\n<p>In the case that <script type=\"math\/tex;\">v<\/script> is in <script type=\"math\/tex;\">V_t<\/script>, vertex <script type=\"math\/tex;\">v<\/script> is added to <script type=\"math\/tex;\">S<\/script>, so <script type=\"math\/tex;\">|S_{t+1}|=1+|S_t|<\/script>. That contributes an increase of 1 to <script type=\"math\/tex;\">\\Phi <\/script>. But <script type=\"math\/tex;\">\\Phi <\/script> also decreases because <script type=\"math\/tex;\">v<\/script>\u2019s neighbors no longer contribute: for each remaining vertex <script type=\"math\/tex;\">w\\in V_t<\/script>, let \u201c<script type=\"math\/tex;\">[w\\in N(v)]<\/script>\u201d denote 1 if <script type=\"math\/tex;\">w<\/script> is <script type=\"math\/tex;\">v<\/script> or a neighbor of <script type=\"math\/tex;\">v<\/script>, and 0 otherwise. When <script type=\"math\/tex;\">v<\/script> is added, the increase in the pessimistic estimator, <script type=\"math\/tex;\">\\Phi _{t+1} - \\Phi _t<\/script>, is <\/p>\n<div id=\"turan:eqn\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{turan:eqn} 1 - \\sum _{w\\in V_t} \\frac{[{w}\\in N(v)]}{d_{w}+1}. \\end{equation}<\/script><\/div>\n<p> The conditional expectation of <script type=\"math\/tex;\">[w\\in N(v)]<\/script>, given that <script type=\"math\/tex;\">v\\in V_t<\/script>, is at most <script type=\"math\/tex;\">(d_w+1)\/|V_t|<\/script>. Thus, the expectation of (\\ref{turan:eqn}) above is at least <\/p>\n<div id=\"a0000000009\" class=\"equation\"><script type=\"math\/tex; mode=display\">  1 ~ -~  \\sum _{w\\in V_t} \\frac{(d_w+1)\/|V_t|}{d_w+1} ~ ~ =~ ~  0.  <\/script><\/div>\n<p> We\u2019ve verified that <script type=\"math\/tex;\">\\Phi <\/script> is a sub-martingale. <\/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=\"a0000000010\">Many ways to keep the pessimistic estimator from decreasing<\/h1>\n<p> To guarantee success, the algorithm should choose the next vertex to ensure <script type=\"math\/tex;\">\\Phi _{t+1} \\ge \\Phi _t<\/script>. We\u2019ve verified that this is always possible. More concretely, what choices will ensure this? <\/p>\n<p>If the algorithm next considers some <script type=\"math\/tex;\">v<\/script> that has already been deleted (that is, <script type=\"math\/tex;\">v\\not\\in V_t<\/script> and <script type=\"math\/tex;\">v<\/script> has a neighbor in <script type=\"math\/tex;\">S<\/script> already), then the vertex <script type=\"math\/tex;\">v<\/script> will not be taken in the independent set. By inspection, <script type=\"math\/tex;\">\\Phi _{t+1}<\/script> equals <script type=\"math\/tex;\">\\Phi _t<\/script>. So, considering any deleted vertex (and not taking it) keeps the pessimistic estimator from decreasing. <\/p>\n<p>Otherwise, the algorithm next considers some <script type=\"math\/tex;\">v\\in V_t<\/script>. In this case (considering the random experiment), the algorithm must add <script type=\"math\/tex;\">v<\/script> to <script type=\"math\/tex;\">S<\/script>. As shown above, the increase <script type=\"math\/tex;\">\\Phi _{t+1}-\\Phi _t<\/script> is at least (\\ref{turan:eqn}). <\/p>\n<p>Next are a few different ways to make the choice to ensure that the increase is non-negative. They all lead to minor variations of the same basic greedy algorithm. <\/p>\n<\/div>\n<div class=\"latex-section\">\n<h1 id=\"a0000000011\">Maximizing the pessimistic estimator<\/h1>\n<p> Perhaps the most obvious way is, at each step, to <em> choose <script type=\"math\/tex;\">v\\in V_t<\/script> so as to maximize <script type=\"math\/tex;\">\\Phi _{t+1}<\/script>.<\/em> Since <script type=\"math\/tex;\">\\Phi <\/script> is a sub-martingale, this ensures <script type=\"math\/tex;\">\\Phi _{t+1}\\ge \\Phi _t<\/script>. More concretely, this gives the following algorithm: <\/p>\n<blockquote class=\"quote\"><p><em> Assign each vertex <script type=\"math\/tex;\">v<\/script> a fixed weight <script type=\"math\/tex;\">1\/(d_v+1)<\/script>. Repeat until no vertices remain: choose a vertex <script type=\"math\/tex;\">v<\/script> minimizing the total weight of <script type=\"math\/tex;\">v<\/script> and its current neighbors; add <script type=\"math\/tex;\">v<\/script> to <script type=\"math\/tex;\">S<\/script> and delete <script type=\"math\/tex;\">v<\/script> and its neighbors. Return <script type=\"math\/tex;\">S<\/script>.<\/em> <\/p><\/blockquote>\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\">In order of increasing original degree<\/h1>\n<p> Here\u2019s another way to choose <script type=\"math\/tex;\">v<\/script> that works: <em> Choose any <script type=\"math\/tex;\">v\\in V_t<\/script> whose original degree <script type=\"math\/tex;\">d_v<\/script> is at most the minimum, over <script type=\"math\/tex;\">v<\/script>\u2019s remaining neighbors <script type=\"math\/tex;\">w<\/script>, of the original degree <script type=\"math\/tex;\">d_w<\/script> of <script type=\"math\/tex;\">w<\/script>.<\/em> (For example, consider the vertices in order of increasing degree in the original graph.) <\/p>\n<p>By calculation, the lower bound (\\ref{turan:eqn}) is non-negative: when a vertex <script type=\"math\/tex;\">v<\/script> is added, at most <script type=\"math\/tex;\">d_v+1<\/script> vertices <script type=\"math\/tex;\">w<\/script> in <script type=\"math\/tex;\">V_t<\/script> are deleted from the graph, and each of those has <script type=\"math\/tex;\">1\/(d_w+1) \\le 1\/(d_v+1)<\/script>. <\/p>\n<p>Here is one such algorithm: <\/p>\n<blockquote class=\"quote\"><p><em> Consider the vertices in order of increasing degree. Add each vertex if, when it is considered, none of its neighbors have been added.<\/em> <\/p><\/blockquote>\n<\/div>\n<div class=\"latex-section\">\n<h1 id=\"a0000000013\">In order of increasing current degree<\/h1>\n<p> Alternatively, the algorithm can choose vertices based on their degree, say <script type=\"math\/tex;\">d'_v<\/script>, in the <em> remaining<\/em> graph, instead of the degree <script type=\"math\/tex;\">d_v<\/script> in the original graph: <\/p>\n<blockquote class=\"quote\"><p><em> Choose any <script type=\"math\/tex;\">v\\in V_t<\/script> whose current degree <script type=\"math\/tex;\">d'_v<\/script> is at most the minimum, over <script type=\"math\/tex;\">v<\/script>\u2019s remaining neighbors <script type=\"math\/tex;\">w<\/script>, of the current degree <script type=\"math\/tex;\">d'_w<\/script> of <script type=\"math\/tex;\">w<\/script>.<\/em> <\/p><\/blockquote>\n<p>This choice keeps the increase (\\ref{turan:eqn}) non-negative because there are <script type=\"math\/tex;\">d'_v+1<\/script> vertices <script type=\"math\/tex;\">w\\in V_t<\/script> that have <script type=\"math\/tex;\">w\\in N(v)<\/script>, and each of those has <script type=\"math\/tex;\">1\/(d_w+1)\\le 1\/(d_v+1)\\le 1\/(d'_v+1)<\/script>. <\/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\">Many pessimistic estimators<\/h1>\n<p>We\u2019ve seen above that a given pessimistic estimator can justify a variety of algorithms. As the next exercise illustrates, a given existence proof can also give rise to multiple pessimistic estimators. This is useful in designing algorithms. <\/p>\n<div id=\"a0000000015\" 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>Let <script type=\"math\/tex;\">\\tilde d_w<\/script> denote the number of not-yet-considered neighbors of <script type=\"math\/tex;\">w<\/script>. (Note <script type=\"math\/tex;\">d'_w \\le \\tilde d_w \\le d_w<\/script>.) Define <script type=\"math\/tex;\">\\tilde\\Phi _t = |S_t| + \\sum _{w\\in V_t} 1\/(\\tilde d_w+1)<\/script>. Show that this is also a valid pessimistic estimator. What algorithms can you derive using it? <\/p>\n<\/div><\/div>\n<div id=\"a0000000016\" 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>Instead of defining <script type=\"math\/tex;\">Q<\/script> to be the size of the independent set <script type=\"math\/tex;\">|S|<\/script>, define <script type=\"math\/tex;\">Q<\/script> to be the number of vertices <script type=\"math\/tex;\">v<\/script> such that <script type=\"math\/tex;\">v<\/script> is considered before any of its neighbors. Apply the method of conditional probabilities with this <script type=\"math\/tex;\">Q<\/script>. What algorithms can you derive this way? <\/p>\n<\/div><\/div>\n<div id=\"a0000000017\" class=\"my-theorem latex-paragraph latex-Exercise\">\n<div class=\"latex-paragraph-heading\">  <b>Exercise 3.<\/b>    <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>Which of the algorithms in this section do you think might find the largest independent sets in practice? Why? <\/p>\n<\/div><\/div>\n<div id=\"a0000000018\" class=\"my-theorem latex-paragraph latex-Exercise\">\n<div class=\"latex-paragraph-heading\">  <b>Exercise 4.<\/b>    <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>Each algorithm above produces an independent set of size at least <script type=\"math\/tex;\">n\/(\\bar d + 1)<\/script>. Describe examples of graphs for which the algorithms produce independent sets that are much smaller than the maximum possible independent sets. <\/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=\"a0000000019\">Wikipedia<\/h1>\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<h1 id=\"bibliography\">Bibliography<\/h1>\n<table class=\"bibliography\" cellspacing=\"0\" cellpadding=\"2\">\n<tr>\n<td valign=\"top\">[<a name=\"Erdos70Graph\">1<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;P+Erdos&quot;+intitle:&quot;+On+the+graph-theorem+of+Turan&quot;\">P.\u00a0Erd\u0151s. On the graph-theorem of Tur\u00e1n. <em>Math. Lapok.<\/em>, 21:249\u2013251, 1970. <\/a><\/td>\n<\/tr>\n<\/table><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<div id=\"footnotes\">\n<div>\n<h2>Footnotes<\/h2>\n<ol>\n<li id=\"a0000000008\">If, for some random variable <script type=\"math\/tex;\">Q<\/script>, each <script type=\"math\/tex;\">\\Phi _t<\/script> was exactly the conditional expectation of <script type=\"math\/tex;\">Q<\/script>, then <script type=\"math\/tex;\">\\Phi <\/script> would necessarily be a sub-martingale (in fact a martingale).<\/li>\n<\/ol><\/div>\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Pessimistic estimators in the method of conditional probabilities. In applying the method of conditional probabilities, exact conditional probabilities (or expectations) are sometimes hard to compute. Pessimistic estimators can be used instead. We illustrate the idea by example, using Tur\u00e1n\u2019s theorem.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":901,"menu_order":4,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1270","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/1270","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=1270"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/1270\/revisions"}],"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=1270"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}