Method of conditional probabilities
In mathematics and computer science, the probabilistic method is used to prove the existence of mathematical objects with desired combinatorial properties. The proofs are probabilistic — they work by showing that a random object, chosen from some probability distribution, has the desired properties with positive probability. Consequently, they are nonconstructive — they don't explicitly describe an efficient method for computing the desired objects.
- Abstraction100002137
- Act100030358
- Activity100407535
- Algorithm105847438
- Argument106648724
- Communication100033020
- Event100029378
- Evidence106643408
- Indication106797169
- Procedure101023820
- PsychologicalFeature100023100
- Rule105846932
- WikicatApproximationAlgorithms
- WikicatProbabilisticArguments
- YagoPermanentlyLocatedEntity
- Comment
- enIn mathematics and computer science, the probabilistic method is used to prove the existence of mathematical objects with desired combinatorial properties. The proofs are probabilistic — they work by showing that a random object, chosen from some probability distribution, has the desired properties with positive probability. Consequently, they are nonconstructive — they don't explicitly describe an efficient method for computing the desired objects.
- Depiction
- Has abstract
- enIn mathematics and computer science, the probabilistic method is used to prove the existence of mathematical objects with desired combinatorial properties. The proofs are probabilistic — they work by showing that a random object, chosen from some probability distribution, has the desired properties with positive probability. Consequently, they are nonconstructive — they don't explicitly describe an efficient method for computing the desired objects. The method of conditional probabilities, converts such a proof, in a "very precise sense", into an efficient deterministic algorithm, one that is guaranteed to compute an object with the desired properties. That is, the method derandomizes the proof. The basic idea is to replace each random choice in a random experiment by a deterministic choice, so as to keep the conditional probability of failure, given the choices so far, below 1. The method is particularly relevant in the context of randomized rounding (which uses the probabilistic method to design approximation algorithms). When applying the method of conditional probabilities, the technical term pessimistic estimator refers to a quantity used in place of the true conditional probability (or conditional expectation) underlying the proof.
- Is primary topic of
- Method of conditional probabilities
- Label
- enMethod of conditional probabilities
- Link from a Wikipage to an external page
- books.google.com/books%3Fid=EILqAmzKgYIC&q=%22method+of+conditional%22
- books.google.com/books%3Fid=Kz0B0KkwfVAC
- books.google.com/books%3Fid=q3lUjheWiMoC&q=%22method+of+conditional+probabilities%22
- books.google.com/books%3Fid=QKVY4mDivBEC&q=%22method+of+conditional+probabilities%22
- algnotes.info/on/background/probabilistic-method/method-of-conditional-probabilities/
- Link from a Wikipage to another Wikipage
- Approximation algorithm
- Cambridge University Press
- Category:Approximation algorithms
- Category:Probabilistic arguments
- Computer science
- Convex function
- Derandomization
- Deterministic algorithm
- Expected value
- File:Method of conditional probabilities.png
- Graph (discrete mathematics)
- Independent set (graph theory)
- Journal of Computer and System Sciences
- Mathematics
- Max cut
- Maximum cut
- Nonconstructive proof
- Polynomial time
- Probabilistic method
- Randomized rounding
- Springer Verlag
- Turán's theorem
- SameAs
- 4rz3V
- m.0bmdhx3
- Method of conditional probabilities
- Q6823704
- Метод условных вероятностей
- Subject
- Category:Approximation algorithms
- Category:Probabilistic arguments
- Thumbnail
- WasDerivedFrom
- Method of conditional probabilities?oldid=1087497644&ns=0
- WikiPageLength
- 21158
- Wikipage page ID
- 26944505
- Wikipage revision ID
- 1087497644
- WikiPageUsesTemplate
- Template:Citation
- Template:Cite book
- Template:Harv
- Template:ISBN
- Template:No footnotes
