Method of conditional probabilities: Difference between revisions

Revision as of 05:05, 19 October 2016

Revision as of 15:27, 15 November 2016

Line 23:

: ''Probabilistic proof.'' If the three coins are flipped randomly, the expected number of tails is 1.5. Thus, there must be some outcome (way of flipping the coins) so that the number of tails is at least 1.5. Since the number of tails is an integer, in such an outcome there are at least 2 tails. ''QED''

In this example the random experiment consists of flipping three fair coins. The experiment is illustrated by the rooted tree in the adjacent diagram to the right. There are eight outcomes, each corresponding to a leaf in the tree. A trial of the random experiment corresponds to taking a random walk from the root (the top node in the tree, where no coins have been flipped) to a leaf. The successful outcomes are those in which at least two coins came up tails. The interior nodes in the tree correspond to partially determined outcomes, where only 0, 1, or 2 of the coins have been flipped so far.

To apply the method of conditional probabilities, one focuses on the ''conditional probability of failure, given the choices so far'' as the experiment proceeds step by step.

Line 260:

{{DEFAULTSORT:Method Of Conditional Probabilities}}

[[Category:Approximation algorithms]]

[[Category:Probabilistic arguments]]