# An Algorithm to Determine a probable profit

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.

Thank you!

• This seems like a simple exercise rather than on the level of research, so it might fit some of the other sites in the FAQ better. If you really mean "consecutive" (contrary to your example) then there is an $O(n^2)$ algorithm by considering the events that a streak of length $i$ ends in position $j$. If you don't mean consecutive then there is an even faster algorithm from expressing the probabilities as a convolution. – Douglas Zare Jan 5 '13 at 4:55
• @Douglas Zare If you have 5 questions then a possible answer could be CWCCC where C=correct and W=wrong. This answer will get $(1+3^4)p_1⋅(1−p_2)⋅p_3⋅p_4⋅p_5$ points. So consecutive answers get more points that's what I meant. And I'm only interested on the sum of the points. Can you be more precise? – Vertical Jan 5 '13 at 12:07

It's best, I think, to think of the questions as being asked in backwards order: $n$ first, then $n-1$, etc., down to question $1$. And just for fun, let's tack on one final question for which the probability of answering correctly is $p_0=0$. The relevant recursion then is
Starting from $E(p_0)=0$, one can compute (and store) values for $E(p_0,p_1)$, $E(p_0,p_1,p_2)$, etc. The complexity is probably something like $O(n^3)$.