MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 0 down vote accepted

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.

share|cite|improve this answer
Thank you! Answer accepted :) – Vertical Jan 5 '13 at 20:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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