MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Are the terms in the sum similar in value, or do they vary a lot? – Brendan McKay Feb 6 '12 at 23:32
$c_i x_i$ usually have a few peaks (large values) and mostly small values. – eakbas Feb 7 '12 at 0:02
What will you do with the estimate? There are cases where using an extreme valuation is good, and others where using an average or expected value is good. Gerhard "Ask Me About System Design" Paseman, 2012.02.06 – Gerhard Paseman Feb 7 '12 at 1:35
I need the average of $c_i x_i$. – eakbas Feb 7 '12 at 2:11
For what end do you need this average? Gerhard "Ask Me About System Design" Paseman, 2012.02.06 – Gerhard Paseman Feb 7 '12 at 7:15
up vote 0 down vote accepted

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.)

share|cite|improve this answer

Assuming that $x_i$ are independent, you should consider the highest values of $x_i$. This can be seen as a lossy compression like DCT, KL,...

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.