Fair price: receive sum of the last decreasing sequence

expected valuegame theoryprobabilityproblem solvingsequences-and-series

This is a Jane Street Interview question.

What is the fair price of a game in which you shuffle nine cards labeled 1 through 9 then keep choosing whether to open the next card or stop, given that you will receive the sum of the last decreasing sequence?

So far, I have solved for the expected value of having $2$ cards which is $\frac12 \times 3$ and the expected value of having $3$ cards, which is $2 \times \frac23$. My question is, how do we even determine the expected value of the decreasing sequence in the first place. I cannot find anything online about this. After solving that, I believe we can simply compare expected values to determine optimal stopping.

Best Answer

You want to take a dynamic programming approach (which I think should be similar to fedja's answer). Let $A(n,\ell,S)$ be the expected reward when the current sum is $n$, the last number drawn is $\ell$ and the set of remaining numbers is $S$. We're looking for $A(0,10,\{1,2,3,4,5,6,7,8,9\})$ (here $\ell$ can be any number greater than $9$).

For each state $A(n,\ell,S)$, we consider either stopping or drawing:

  • If we stop, the expected reward is $n$.
  • If we draw another card, we need to consider every card that's left. For each card $i$ in $S$, if $i \le n$, it continues the decreasing sequence, and the expected reward is $A(n+i, S-\{i\})$. If $i > n$, it breaks the sequence, and the expected reward is $A(i, i, S-\{i\})$.

Here is a Python implementation of this logic:

from functools import lru_cache

@lru_cache(None)
def A(current_sum, last_number, remaining_numbers):
    # If there are no numbers left, the expected reward is the current sum
    if not remaining_numbers:
        return current_sum
    
    # Compute expected value of drawing another number
    EV_draw = sum(
        A(current_sum + i if i <= last_number else i, i, remaining_numbers - {i}) 
        for i in remaining_numbers) / len(remaining_numbers)
    
    # The optimal strategy is to stop if current_sum >= EV_draw, and draw if current_sum < EV_draw
    return max(current_sum, EV_draw)

# Initialise with current_sum = 0, last_number = 10 (greater than any card), and all numbers remaining
print(A(0, 10, frozenset(range(1, 10))))

This gives an expected value of $2749727/181440 \approx 15.15502094356261$.

If anyone can work out the formula, we also have the following answers starting with $2$ cards: $5/2, 25/6, 143/24, 463/60, 6853/720, 57229/5040, 66713/5040, 2749727/181440$. (It looks like there could be a $n!$ in the denominator).