Picking a number out of 1 to 100 three times A box contains $100$ tickets, labeled from $1$ to $100$. You are given up to three times to randomly pick a ticket in the box. At any point, you can stop and the number on that ticket becomes your final score. What is your best strategy to optimize your score ? What is the best expected score ?
I was thinking that $\Bbb E[X_1]=50.5$. If we get better than this in the first pick, we will keep it, if not we roll again. So the $$\Bbb E[X_2]= 0.5\cdot 50.5 + 51\cdot(1/100)+\cdots+100\cdot(1/100).$$ Similarly, would get $\Bbb E[X_3]$ this way. Not sure if I'm on the right track though.
 A: I am assuming that we put the ticket back each time we decide to pick another number. When you draw the second ticket, the threshold will be $\frac{100 + 1}{2} = 50.5$, since this is the expected value of the third turn: we stop if we pick a higher number, and continue if we pick a lower one. To determine the threshold for the first turn, we calculate the expected value of our number if we decide to go for a second turn:

*

*With probability $\frac{1}{2}$, we will pick a number higher than $50.5$ in the second turn. In this case, we stop, with an expected value of $\frac{100 + 51}{2} = 75.5$;

*With probability $\frac{1}{2}$,, we will pick a number lower than $50.5$ in the second turn. In this case, we pick again, with an expected value of $\frac{100 + 1}{2} = 50.5$.

Thus, the expected value of the number starting from the second turn, equals $\frac{75.5 + 50.5}{2} = 63$. If we pick a lower number in the first turn, we draw again; in all other cases, we stop. Putting everything together, we find that the expected value equals:
$$\frac{63}{100} \cdot 63 + \frac{37}{100} \cdot \frac{100 + 64}{2} = 70.03$$
