Estimating the expected cost of strategies for function evaluation problem

ABSTRACT
In our research, we addressed the problem of estimating the expected cost of a given strategy for a given k-out-of-n function. The binary decision tree that describes the full strategy has an exponential size in k and n. As a result, using the standard ways over the binary decision tree causes the computation of the strategy’s expected cost in exponential time. In the research, we suggest estimating the expected cost by taking samples of the inputs like in the Monte Carlo method. We find out by numerical experiments if the strategy’s expected cost can be estimated accurately by this sampling approach.