Method of conditional probabilities: Difference between revisions

Revision as of 16:33, 15 July 2013

Revision as of 15:22, 6 February 2014

Line 38:

== Efficiency ==

In a typical application of the method, the goal is to be able to implement the resulting deterministic process by a reasonably efficient algorithm (formallythe word "efficient" usually means an algorithm, onewhich takingneeds the [[polynomial time|time polynomial]] inof the input size), even though typically the number of possible outcomes is huge (exponentially large). (E.g., consider the example above, but extended to ''n'' flips for large ''n''.)

In the ideal case, given a partial state (a node in the tree), the conditional probability of failure (the label on the node) can be efficiently and exactly computed. (The example above is like this.) If this is so, then the algorithm can select the next node to go to by computing the conditional probabilities at each of the children of the current node, then moving to any child whose conditional probability is less than 1. As discussed above, there is guaranteed to be such a node.