Sorry for the vague title but I couldn't find a better one. 


I want to compute the sum $S = \frac{1}{N}\sum\_{i=1}^N c\_i x\_i$ where $c\_i$s are known positive constants. The problem is that computing the value of each $x\_i$ takes a huge amount of time. That's why I want to estimate the sum $S$ by using only a small subset of $x\_i$s. How can I do this? I'm not sure if I can apply some sort of importance sampling here. 



Estimating a sum
This isn't an answer, but it occurs to me that a relatively simple (and timely) toy example of the type of calculation the OP is describing might help clarify what kinds of assumptions are needed in order to provide an actual answer.


Suppose you'd like to know how many of the 538 total votes in the Electoral College Obama can expect to get in November. In this case we're interested in $c\_1 x\_1 + c\_2 x\_2 + \cdots + c\_{51} x\_{51}$, where the $i$'s are the 50 states and the District of Columbia, the $c\_i$'s are their various Electoral College votes (ranging from 55 for California down to 3 for DC and a few other small states), and $x\_i$ is the probability of Obama winning state $i$. (Note, I've omitted the division by 51 here, but only because in presidential politics they talk about the "road to 270," not the "road to 5.2941.") "Computing" an $x\_i$ means commissioning a poll and doing a detailed analysis, so it's expensive. The OP's question here would seem to be, Can you get an *estimate* on Obama's expected EC total by looking at only *some* of the states?


In this regard, it seems natural to focus on states with the largest $c\_i$'s and order things so that $c\_1 \ge c\_2 \ge \cdots \ge c\_{51}$. My guess would be to compute something like


$$S\_k = \frac{538}{c\_1+\cdots + c\_k}(c\_1 x\_1 + \cdots + c\_kx\_k)$$


where $538 = c\_1+ \cdots + c\_{51}$ is the total number of Electoral College votes, and do this for $k=1,2,\ldots$ until the result doesn't seem to change much. The devil, I think, is in the details of the casual words "doesn't seem" and "much."


(A couple of sidenotes: First, I'm setting aside the fact that there are really only a dozen or so "battleground" states in the Presidential election, and pretending that we don't even know offhand how likely it is that Obama will win the District of Columbia. Also, I simplified the Electoral College here to be winner-take-all in each state. This isn't quite true for Nebraska and Maine. But they'd come late in the computation anyway. Finally, my apologies to non-U.S. readers who may need to consult Wikipedia for an explanation of the Electoral College.)


