For a random objective with an easily computable conditional expectation, reveal one random choice at a time and choose an outcome whose conditional expected objective is at least the current value. Such an outcome exists because the current value is an average of the child values. When all choices are fixed, the actual objective is at least the initial expectation. Biased as well as fair choices work. Efficient expectation updates make the resulting deterministic procedure a polynomial-time algorithm.
Articles by others on the same topic
The method of conditional probabilities is a mathematical technique used primarily in probability theory and statistics to calculate the probability of an event given that another related event has occurred. This approach is particularly useful when dealing with complex problems where direct calculation of probabilities is infeasible. ### Key Concepts: 1. **Conditional Probability**: The conditional probability of an event \(A\) given that event \(B\) has occurred is denoted as \(P(A | B)\).