Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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|improve this answer
    
Thank you @Hagen von Eitzen answer accepted and upvoted –  epsilon Jan 5 '13 at 20:31
add comment

Your Answer

 
discard

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.