Method of conditional probabilities: Difference between revisions

Revision as of 15:31, 6 February 2014

Revision as of 14:56, 11 August 2014

Line 123:

Let ''Q''^(''t'') denote the above quantity, which is called a '''pessimistic estimator''' for the conditional expectation.

The proof showed that the pessimistic estimator is initially at least |''V''|/(''D''+1). (That is, ''Q''⁽⁰⁾> ≥ |''V''|/(''D''+1).) The algorithm will make each choice to keep the pessimistic estimator from decreasing, that is, so that ''Q''^(''t''+1) ≥ ''Q''^(''t'') for each ''t''. Since the pessimistic estimator is a lower bound on the conditional expectation, this will ensure that the conditional expectation stays above |''V''|/(''D''+1), which in turn will ensure that the conditional probability of failure stays below 1.

Let ''u'' be the vertex considered by the algorithm in the next ((''t''+1)-st) step.