What's the fastest way to find this sum of "like multiplications"?

Question

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.

Answer 1

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