An Algorithm to Determine a probable profit

Question

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!

Answer 1

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

\begin{array}{rcl} E(p_0,p_1,\ldots,p_n) &=& p_np_{n-1}\cdots p_1(1-p_0)(n-0)^2 \cr && +\ p_np_{n-1}\cdots p_2(1-p_1)\left((n-1)^2 +E(p_0)\right) \cr && +\ p_np_{n-1}\cdots p_3(1-p_2)\left((n-2)^2+E(p_0,p_1)\right)\cr && +\ p_np_{n-1}\cdots p_4(1-p_3)\left((n-3)^2 + E(p_0,p_1,p_2)\right)\cr && +\ \ldots \cr && +\ (1-p_n)\left((n-n)^2 + E(p_0,p_1,\ldots p_{n-1})\right)\cr &=& p_np_{n-1}\cdots p_1\left( n^2 + \sum_{k=1}^n{ (1-p_k)\over p_1\cdots p_k}\left((n-k)^2+E(p_0,\ldots p_{k-1}) \right)\right) \end{array}

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

To repeat, I've reordered the questions from last to first, for notational convenience -- I found it best to think in terms of the number of questions that remain to be answered. I hope this doesn't cause too much confusion.