In a programming language with short-circuiting, a conjunction of N independent conditions has the following expected cost:
t_i = the expected cost of evaluating a conjunct p_i = the probability that a conjunct evaluates to true
I am trying to prove the following statement:
If you have an optimally ordered conjunction of N conditions and insert a new conjunct at location k (where k is chosen to be the insertion location that minimizes expected cost), then the resulting conjunction of N+1 conditions is also optimally ordered.
I strongly suspect that the above statement is true, because I wrote a Monte Carlo simulation that tested the statement on thousands of randomly generated examples. The test identifies the optimal ordering by brute force and confirms that the optimal ordering can be created by inserting the new condition at some location k. Can anyone help provide a formal proof?