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?