Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose that we have two sequences of $n$ naturals, which we'll call $a$ and $b$. We can denote the $k$th value in the sequence by the term $a_k$ and $b_k$ respectively. We can then define a like multiplication for some number $v$. To do this, we pick $j$ terms from $a$, and at the same time take the terms with the same indexes from $b$. For example, if we pick 3 terms from $a$, and they are $a_3$, $a_5$, and $a_9$, then we would also pick $b_3$, $b_5$ and $b_9$. The like multiplication is then $$(v+a_3+a_5+a_9) \cdot (v+b_3+b_5+b_9)$$

In other words, the like multiplication for $v$ is just $v$ plus some terms from $a$ multiplied by $v$ plus the same terms from $b$. I would like to know the fastest way to find the sum of all possible like multiplications for some $v$ and two equal length sequences $a$ and $b$.

This is somewhat related to this question that I asked before. In particular, we may be able to eliminate $v$ from the equations using that question's answer.

share|improve this question
    
There's a trivial way to do this in $O(2^n)$ by exhaustively multiplying every possible combination. However, I believe that we might be able to do this in $O(n)$ by using the answer to the other question. I'm hoping that someone can confirm this with an explanation. –  Matt Groff Jan 6 '12 at 14:08

1 Answer 1

up vote 4 down vote accepted

For ease of proof, we'll assume you allow the empty subset of indices, as well - that is, the term $v^2$ is in your sum.

Let $N=\{1,...,n\}$. For $S\subset N$ write $a_S=\sum_{i\in S} a_i$ and $b_S$ similarly. Then you want $$\sum_S (v+a_S)(v+b_S) = \sum_S v^2 + \sum_S (a_S+b_S)v + \sum_S a_Sb_S$$

But: $$\sum_S v^2 = 2^n v^2$$ $$\sum_S (a_S+b_S)v = v 2^{n-1}(a_N+b_N)$$

The second formula comes about because for each $k\in N$, $k$ occurs in $2^{n-1}$ subsets $S$, so $a_k$ and $b_k$ each occur $2^{n-1}$ times in the sum.

So the only tricky term is $\sum_S a_Sb_S$. How many times does $a_ib_j$ occur in this sum? If $i=j$, then it occurs in the sum $2^{n-1}$ times.

If $i\neq j$, then $a_ib_j$ occurs once whenever $i,j\in S$. There are $2^{n-2}$ such $S$. Let $D\sum_{i\in N} a_ib_i$. Let $E=\sum_{i,j\in N} a_ib_j = a_Nb_N$.

Then $$\sum_S a_Sb_S = 2^{n-2}(D+a_Nb_N)$$

So, your total is:

$$2^nv^2 + v2^{n-1}(a_N+b_N) + 2^{n-2}(D+a_Nb_N)$$

Since $a_N,b_N,D$ can all be computed in $O(n)$ time, so can your total.

Note that this total can be written as:

$$2^{n-2}[4v^2 + 2v(a_N+b_N) + a_Nb_N + D]$$

And

$$4v^2 + 2v(a_N+b_N) + a_Nb_N = (2v+a_N)(2v+b_N)$$

So we can write your sum as:

$$2^{n-2}[(2v+a_N)(2v+b_N) + D]$$

If you don't want to include the empty set in the sum, you have to subtract $v^2$ from this result, of course.

Dividing our formula by $2^n$ gives the average of $(v+a_S)(v+b_S)$, which this formula says is:

$$(v+\frac{a_N}2)(v+\frac{b_N}2) + \frac{D}{4}$$

Note that $v+\frac{a_N}2$ is the average value of $v+a_S$ and $v+\frac{b_N}2$ is the average of $v+b_S$. So this says that the average of the product $(v+a_S)(v+b_S)$ minus the product of the average of $v+a_S$ and the average of $v+b_S$ is always $\frac{D}4$.

share|improve this answer
    
Thanks for the extra information! –  Matt Groff Jan 6 '12 at 17:48

Your Answer

 
discard

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.