# Efficient Fast Fourier Transform to calculate the expected value

Suppose two people A and B draw a list of cards with difference scores n = {0, 1, 2, ..., n - 1}. Let $$i \in$$n such that $$i \in [0, n - 1].$$ Let $$a_i$$ be the probability that the person A draws a card with score of $$i$$, and let $$b_i$$ be the probability that the person B draws a card with score of $$i$$. In the event in which A gets $$i$$ score and B gets $$j$$ score, we define the expected gain of A's is $$(a_i * b_j) * (i - j).$$ We need to calculate the expected gain of A's.

My naive solution is $$O(n^2)$$ which counts all cases that A and B can happen and then add them together. Is there any hint how to use FFT to make the solution run in $$O(n \log n)$$?

• If I'm understanding the problem right (the expected gain is the expected value of the difference of their score?), you don't need FFT to do better. Try writing out the sum explicitly and/or use linearity of expectation. – Lorenzo Najt Sep 22 '20 at 20:15
• @Lorenzo Najt Yes, your understanding is correct. The naive solution requires $O(n^2)$ since A and B are two independent events. For example, $a_0 * b_0 * (0 - 1) + a_0 * b_1 * (0 - 1) +...+ a_{0} * b_{n - 1} * (n - 1) + a_1 * b_0 * (1 - 0) +...$ – hck007 Sep 22 '20 at 20:40
• You can use linearity of expectation to get O(n) time. – Lorenzo Najt Sep 22 '20 at 20:48
• (Equivalently, you can try to cleverly factor that sum.) – Lorenzo Najt Sep 22 '20 at 21:31
• @Lorenzo Najt Thanks for the reply!!! Do you mean E[A - B] = E[A] - E[B]? If this is true, then I can just simply calculate $E[A] = \sum_{i = 0}^{i = n - 1}a_i * i$ and for E[B] and plug the value into the equation. – hck007 Sep 22 '20 at 21:32