5
$\begingroup$

I have encountered the phrase "Principle of deferred decisions" in Mitzenmacher and Upfal's book on Randomized Algorithms and several other courses online. Isn't it just conditional probability? In my understanding, it seems to be an intuitive way of using conditional probability:

$\Pr(\bigcap_{i = 1}^{n} E_i) = \prod_{i = 1}^{n} \Pr(E_i | E_{i-1},\dots,E_{0})$ where $E_0 = \emptyset$.

Is my understanding right?

$\endgroup$
  • 1
    $\begingroup$ I have never heard of this phrase. Perhaps you could give an example? $\endgroup$ – Yuval Filmus Mar 6 '16 at 7:48
5
$\begingroup$

The principle of deferred decisions is the concept that we have two ways to make a random choice both of which are equivalent.

One way is that you can toss a coin yourself at the exact step when you need a random input in some algorithm. In the other way you can imagine that there is an oracle who has already tossed a coin infinitely many times and has some sequence of the form $HTHTHH\dots$, and we query this oracle to tell us the next randomized outcome.

Basically we can defer the act of actually using a randomized input for as long as we have to and this won't affect the randomness of this input.

$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .