Principle of deferred decisions is a technique used in analysis of
randomized algorithm
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...
s.
Definition
A
randomized algorithm
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...
makes a set of random choices. These
random
In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no :wikt:order, order and does not follow an intelligible pattern or combination. Ind ...
choices may be intricately related making it difficult to analyze it. In many of these cases ''Principle of Deferred Decisions'' is used. The idea behind the principle is that the entire set of random choices are not made in advance, but rather fixed only as they are revealed to the algorithm.
Applications
The Clock Solitaire Game
The principle is used to evaluate and determine the probability of "win" from a
deck of cards
A playing card is a piece of specially prepared card stock, heavy paper, thin cardboard, plastic-coated paper, cotton-paper blend, or thin plastic that is marked with distinguishing motifs. Often the front (face) and back of each card has a fi ...
. The idea is to let the random choices unfold, until the iteration ends at 52, where if the fourth card is drawn out of a group labeled "K", the game terminates.
References
Sources
*
M. Mitzenmacher and
E. Upfal. Probability and Computing : Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (NY), 2005. Section 1.3, page 9.
Randomized algorithms
{{algorithm-stub