2
$\begingroup$

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?

$\endgroup$
1

1 Answer 1

5
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.