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 example:
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.
Any ideas? I'm only interested in the sum itself.