You are presented with a symmetric random walk $X_n$ over $\mathbb{Z}$. But with a twist: At any given time $t$, a prophet tells me the range of the random walk $R_{t}$ in the next $T$ steps, where the range is the number of distinct values visited by the walk from $t$ to $t+T$.
At any given point in the walk $\tau$, I can take $X_{\tau}$. My goal is to maximize $\mathbb{E}[X_t]$ for any $t$ I choose to take. What is the optimal rule for stopping at any point?
Thoughts:
My hunch is to take $X_{\tau}$ whenever it is above the given range, but I can't prove that it's optimal.
Any ideas on how to expand upon this idea or simplify it would be appreciated.
Relevant References: