Method of conditional probabilities: Difference between revisions

Revision as of 09:00, 21 March 2018

Revision as of 17:05, 17 March 2019

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 (the word "efficient" usually means an algorithm, whichthat needsruns in the [[polynomial time]] of the input size), even though typically the number of possible outcomes is huge (exponentially large). For example, consider the task with coin flipping, 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.