2
$\begingroup$

Suppose you have one $k$-sided die (labeled $1, \ldots, k$). You want to roll the highest number you can. You get $T$ trials. When you roll, you can either accept the number you rolled, or you can forfeit that number and roll again, leaving $T-1$ trials remaining.

When should you stop rolling?

Intuitively the number you stop at tends to $k$ as $T \to \infty$, and $k/2$ if $k$ is large relative to $T$, but beyond that I don't have much intuition. I feel like there should be a way to set up some recurrence to solve for when you should stop.

This is not homework, I am practicing probability problems for a interview I have coming up, and I saw this problem which stumped me. Could someone explain it to me?

  • 1
    The usual secretary problem is quite different: you don't know the actual "numbers" you roll, only their ranks relative to the previous ones; the sampling is without replacement, and your objective is to maximize the probability of choosing the highest number.2012-03-04

1 Answers 1

5

I assume you want to maximize the expected value of the number you stop at. Let $f(T)$ be the optimal value of this objective. If you reject a roll with $T$ trials remaining, your expected score is $f(T-1)$. So you should accept any roll greater than $f(T-1)$, and reject any below that. The recursion is then $\eqalign{f(T) &= \frac{\lfloor f(T-1)\rfloor}{k} f(T-1) + \sum_{j=\lfloor f(T-1) \rfloor + 1}^{k} \frac{j}{k}\cr &= \frac{\lfloor f(T-1)\rfloor}{k} f(T-1) + \frac{(k - \lfloor f(T-1) \rfloor)(k+\lfloor f(T-1) \rfloor + 1)}{2k}\cr} $ with initial condition $f(1) = (k+1)/2$.