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!

  • $\begingroup$ 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. $\endgroup$ – Douglas Zare Jan 5 '13 at 4:55
  • $\begingroup$ @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? $\endgroup$ – 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

\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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.