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

Question

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?

Answer 1

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<i}p_{j}\right)p_{i+1}R_{i+1}+\left(\prod_{j<i}p_{j}\right)p_{i+1} p_{i}R_{i} + ....+\left( \prod_{j<n}p_{j} \right)R_{n} $$

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<i}p_{j}\right)p_{i}R_{i}+\left(\prod_{j<i}p_{j}\right)p_ip_{i+1}R_{i+1} -\left(\prod_{j<i}p_{j}\right)p_{i+1}R_{i+1}-\left(\prod_{j<i}p_{j}\right)p_{i+1}p_{i}R_{i} \geq 0$$

Since all probabilities are positive, we divide by $\prod_{j<i} p_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!