Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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 2 example2:

example 1 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.

example 2 In the case n=5

I can have answers of the form CWCCC where C stands for correct and W for wrong. This answers gets $(1+3^4)$ points and in order to calculate the expected profit I must multiply those points with the probability $(1+3^4)p_1\cdot (1-p_2) \cdot p_3 \cdot p_4 \cdot p_5$ Then take the sum for all possible answers.

Any ideas? I'm only interested in the sum itself.

Thank you!

share|cite|improve this question
up vote 2 down vote accepted

Dynamic programming is the keyword.

Let $E_{m,r}$ be the expected number of points gained in the first $m$ rounds under the assumption that your last $r$ answers ($0\le r\le m$) are correct and let $P_{m,r}$ be the probability that the last $r$ answers were correct. Then you have the recursion $$P_{m+1,0}=(1-p_{m+1})$$ $$P_{m+1,r+1}=p_{m+1}P_{m,r}$$ $$E_{m+1,0}=\sum_{r=0}^m P_{m,r}E_{m,r}$$ $$E_{m+1,r+1}=((r+1)^4-r^4)E_{m,r}$$ Ultimately, you want to find $E_{n+1,0}$.

share|cite|improve this answer
Thank you @Hagen von Eitzen answer accepted and upvoted – epsilon Jan 5 '13 at 20:31

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.