I 'm searching for an algorithm (and except the naive brute force solution had no luck) that efficiently ($O(n^2)$preferably) does the following:
Supposing I’m playing a game and in this game I’ll have to answer n questions (each question from a different category). For each category $i$, $i=1,...,n$ I’ve calculated the probability $p_i$ to give a correct answer.
For each consecutive k correct answers I’m getting $k^4$ points. What is the expected average profit?
I will clarify what I mean by expected profit in the following 2 example2:
example 1 In the case n=3 and $p_1=0.2,p_2=0.3,p_3=0.4$
The expected profit is
$ EP=\left(0.2\cdot 0.3\cdot 0.4\right)3^4+$ (I get all 3 answers correct)
$+\left(0.2\cdot 0.3\cdot 0.6\right)2^4+\left(0.8\cdot 0.3\cdot 0.4\right)2^4+\left(0.2\cdot 0.7\cdot 0.4 \right)2+$ (2 answers correct)
$+\left(0.2\cdot 0.7\cdot 0.6\right) +\left(0.8\cdot 0.3\cdot 0.6\right)+\left(0.8\cdot 0.7\cdot 0.4\right)$ (1 answer correct)
clearly for each possible outcome I'm calculating the probability and multiply it with the points gained. And then get the sum off all those.
example 2 In the case n=5
I can have answers of the form CWCCC where C stands for correct and W for wrong. This answers gets $(1+3^4)$ points and in order to calculate the expected profit I must multiply those points with the probability $(1+3^4)p_1\cdot (1-p_2) \cdot p_3 \cdot p_4 \cdot p_5$ Then take the sum for all possible answers.
Any ideas? I'm only interested in the sum itself.