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)$?

  • $\begingroup$ 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. $\endgroup$ – Lorenzo Najt Sep 22 '20 at 20:15
  • $\begingroup$ @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) +...$ $\endgroup$ – hck007 Sep 22 '20 at 20:40
  • $\begingroup$ You can use linearity of expectation to get O(n) time. $\endgroup$ – Lorenzo Najt Sep 22 '20 at 20:48
  • $\begingroup$ (Equivalently, you can try to cleverly factor that sum.) $\endgroup$ – Lorenzo Najt Sep 22 '20 at 21:31
  • $\begingroup$ @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. $\endgroup$ – hck007 Sep 22 '20 at 21:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.