2
$\begingroup$

In a programming language with short-circuiting, a conjunction of N independent conditions has the following expected cost:

expected cost

where:

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?

$\endgroup$
4
  • $\begingroup$ Looks similar to cs.stackexchange.com/q/35502/755 / cs.stackexchange.com/q/66894/755. Does the same method/algorithm/proof apply here? $\endgroup$
    – D.W.
    Sep 27 '17 at 1:39
  • $\begingroup$ @D.W. - Thank you for connecting the dots! I can see how his exchange argument would work for my problem too. If you post an answer showing that the optimal ordering is the conditions sorted by t / (1 - p), I'll accept your answer. $\endgroup$ Sep 27 '17 at 4:32
  • $\begingroup$ Cool, glad that it helps! I probably won't have a chance to work out the details or check that it all works, but I take your word for it. Given that you know the answer now, can I encourage you to post an answer to your own question? $\endgroup$
    – D.W.
    Sep 27 '17 at 5:38
  • $\begingroup$ In fact, it seems your task is identical to the one considered in D.W.'s second link, and the form of the optimal solution there immediately implies your property here. $\endgroup$ Sep 27 '17 at 7:13