Method of conditional probabilities: Difference between revisions

Revision as of 15:00, 11 August 2014

Revision as of 15:09, 11 August 2014

Line 129:

If ''u'' already has a neighbor in ''S'', then ''u'' is not added to ''S'' and (by inspection of ''Q''^(''t'')), the pessimistic estimator is unchanged. If ''u'' does ''not'' have a neighbor in ''S'', then ''u'' is added to ''S''.

By calculation, if ''u'' is chosen randomly from the remaining vertices, the expected increase in the pessimistic estimator is non-negative. ['''The calculation:.''' Conditioned on choosing a vertex in ''R''^(''t''), the probability that a given term 1/(''d''(''w'')+1) is dropped from the sum in the pessimistic estimator is at most (''d''(''w'')+1)/|''R''^(''t'')|, so the expected decrease in each term in the sum is at most 1/|''QR''^(''t'')|. There are ''R''^(''t'') terms in the sum. Thus, the expected decrease in the sum is at most 1. Meanwhile, the size of ''S'' increases by 1.]

Thus, there must exist some choice of ''u'' that keeps the pessimistic estimator from decreasing.