Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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. –  Robert Israel Mar 4 '12 at 18:02

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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