# Dynamic programming: optimal order to answer questions to score the maximum expected marks

You have $$n$$ questions in an exam. Question $$i$$ is answered correctly with probability $$p_i > 0$$. If question $$i$$ is answered correctly, you get $$R_i$$ marks. You can choose to answer the questions in any order. As long as you are giving correct answers, you can accumulate all the marks. However, whenever your answer to a question is incorrect, the examination is over and you are not allowed to answer any other question. Given $$R_i$$ and $$p_i$$, what is the optimal order in which you should answer the questions to maximize the total expected marks you score?

Here is my approach - Let $$F_t(S_t)$$ be the expected max score you can have when $$t$$ questions are remaining, and the set of questions remaining is $$S_t$$. We get the recurrence as $$F_t(S_t)=\max_{i \in S_t} [p_i(R_i+F_{t-1}(S_t-\{i\}))]$$ with $$F_0(\phi)=0$$.
Now, $$F_1(\{i\})=p_iR_i$$. $$F_2(\{i,j\})=\max(p_i(R_i+p_jR_j),p_j(R_j+p_iR_i))$$. We see that the first term is larger when $$\frac{p_iR_i}{1-p_i}>\frac{p_jR_j}{1-p_j}.$$ This hints that the ordering may be based on the value of $$\frac{p_iR_i}{1-p_i}$$, but I am not sure how to give a formal proof, or how to solve the recurrence efficiently?

First, if any $$p_i=0$$, then immediately throw it away since you're guaranteed to lose. If any probability is $$1$$ then immediately ask it! (after all why risk not getting the reward when you're guaranteed to get it!). So I'll assume we're now considering probabilities in the range $$(0,1)$$.

Suppose you know that the optimal order is $$1,...,n$$ because a magical fairy told you so. What is your expected score? Well, it is

$$E_1 = p_{1}R_{1} + p_{1}p_{2}R_{2} + p_{1}p_{2}p_{3}R_{3} + .... + \prod_{j\leq n}p_{j} R_{n}$$

Now suppose you decided to switch indices $$i$$ and $$i+1$$ in the order that the fairy told you, so now your order is $$1, ..., i-1,{\bf i+1,i}, i+2, ...,n$$. What is your expectation now? Well, it is

$$E_2 = p_{1}R_{1} + p_{1}p_{2}R_{2} + .... + \left(\prod_{j

Because $$E_1$$ is optimal, then it must be $$E_1 \geq E_2 \implies E_1 - E_2 \geq 0$$ (otherwise the cheeky oracle lied to us!). But notice that $$E_1, E_2$$ are only different in their $$i$$ and $$i+1$$ terms, all other terms are exactly the same (verify this!). So:

$$E_1-E_2 = \left(\prod_{j

Since all probabilities are positive, we divide by $$\prod_{j to get:

$$p_{i}R_{i} + p_i p_{i+1}R_{i+1} - p_{i+1}R_{i+1} - p_i p_{i+1}R_{i} \geq 0$$ Or rearranging

$$p_i R_i (1-p_{i+1}) \geq p_{i+1}R_{i+1} (1-p_i)$$

Or:

$$\frac{p_i R_i }{1-p_i} \geq \frac{p_{i+1} R_{i+1} }{1-p_{i+1}}$$ Wait a minute! This is a condition on the optimal ordering the fairy gave us! So we actually don't need the fairy! Just sort by this order, and that's your optimal ordering!