The Probabilistic Method
Lists
Only you see this
Abstract
The probabilistic method is a way of proving the existence of objects. The underlying principle is simple: to prove the existence of an object with certain properties, we demonstrate a sample space of objects in which the probability is positive that a randomly selected object has the required properties. If the probability of selecting an object with the required properties is positive, then the sample space must contain such an object, and therefore such an object exists. For example, if there is a positive probability of winning a million-dollar prize in a raffle, then there must be at least one raffle ticket that wins that prize.
BibTeX
@inproceedings{mitzenmacher2005probabilistic,
author = {Michael Mitzenmacher and Eli Upfal},
title = {{The Probabilistic Method}},
booktitle = {Cambridge},
year = {2005},
doi = {10.1017/cbo9780511813603.007},
}Loading related content...