patternMinor
What does the "principle of deferred decisions" formally mean
Viewed 0 times
principletheformallywhatmeandecisionsdoesdeferred
Problem
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?
$\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?
Solution
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.
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.
Context
StackExchange Computer Science Q#54060, answer score: 7
Revisions (0)
No revisions yet.