Evaluating the expected value of negatively correlated random variables
I think that in principle it would take exponential time to compute this probability exactly. Hence sampling would be the only option here, although you would have to settle for additive and multiplicative approximation here.
Can I ask you about the problem in which you need this value to be computed?