Fair price: receive sum of the last decreasing sequence

Question

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.

Answer 1

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).

Answer 2

(migrated from comments)

If one is allowed to program, then the exercise is easy and the answer is $$\frac{2749727}{181440}≈15.1550209435626$$ unless I have made a programming error. However, I do not see how to immediately guess that it is between $15$ and $16$ with just pen and paper.

---

How did you program this?

Here is a simple recursive code I used. It is by no means efficient, but with numbers so small pretty much anything you can write would execute reasonably fast. The language is Asymptote.

real f(int[] a, int lst, int sm)
{
if(a.length==0) return sm;
real s=0;
for(int k=0;k<a.length;++k)
{
int newlst=a[k];
int newsm=(newlst<lst? sm+newlst:newlst);
int[] b; 
for(int kk=0;kk<a.length;++kk)
if(kk!=k) b[b.length]=a[kk];
s+=f(b,newlst,newsm);
}
return max(sm,s/a.length);
}

int[] a={1,2,3,4,5,6,7,8,9};
real u=f(a,10,0);
write(u, u*factorial(a.length), factorial(a.length));

pause();