# An algorithm to determine expected profit on a game

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!

-

## 1 Answer

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

-
Thank you @Hagen von Eitzen answer accepted and upvoted –  epsilon Jan 5 '13 at 20:31