Optimal Stopping with Multiplicatively Decreasing Uniform Payoffs
You play the following game starting on turn $i = 1$:
- Generate $X_i \sim \text{Uniform}(0, \alpha^{i-1})$, where $0 < \alpha < 1$, independently of all other draws.
- You may either accept $X_i$ as your payoff (the game ends) or reject it and advance to turn $i + 1$.
- If you reject, the process repeats with $i \leftarrow i + 1$.
The game continues indefinitely until you accept.
Assuming you play optimally, what is your expected payoff? Compute the answer for $\alpha = 1/2$, rounded to the nearest thousandth.
Hints
- The game has a self-similar structure: drawing from $U(0, \alpha^k)$ is the same as $\alpha$ times a draw from $U(0, \alpha^{k-1})$. This means the expected payoff scales linearly: $E_z = z \cdot E_1$.
- If you define $\theta = \alpha E_1$ as the threshold for accepting, the expected payoff is $E_1 = \int_0^1 \max(x, \theta) \, dx$. Evaluate this integral by splitting at $\theta$.
- Substituting $\theta = \alpha E_1$ into $E_1 = (1 + \theta^2)/2$ gives a quadratic in $E_1$. Take the root that satisfies $E_1 \leq 1$.
Worked Solution
How to Think About It: This is an optimal stopping problem with a self-similar structure. Each turn, the range of the uniform draw shrinks by a factor of $\alpha$. The key observation: drawing $X \sim U(0, \alpha^{k})$ is the same as $\alpha$ times a $U(0, \alpha^{k-1})$ draw. So the game starting at turn $i+1$ is a scaled-down copy of the game starting at turn $i$. This self-similarity means the continuation value at any turn is a fixed fraction of the continuation value at the previous turn, and you can write a single equation for the expected payoff.
Quick Estimate: For $\alpha = 1/2$, the first draw is $U(0, 1)$ with mean $0.5$. If you wait, the next draw is $U(0, 0.5)$ with mean $0.25$, and so on. The ranges shrink fast, so you should usually take the first draw unless it's really low. Your expected payoff should be somewhat above $0.5$ -- maybe $0.53$ or so.
Approach: Define $E_1$ as the expected payoff starting from $U(0, 1)$, use the self-similarity to relate the continuation value to $E_1$, and solve the resulting equation.
Formal Solution:
Let $E_z$ denote the expected payoff when the current draw is $U(0, z)$. By the scaling property of uniform random variables, $U(0, z) = z \cdot U(0, 1)$, so all payoffs scale linearly:
$E_z = z \cdot E_1 \quad \text{for all } z > 0$
We want to find $E_1$. On turn 1, you draw $X_1 \sim U(0, 1)$. If you see value $x$, your two options are: - Accept: payoff $= x$ - Reject: expected payoff $= E_{\alpha} = \alpha \cdot E_1$ (the next draw is $U(0, \alpha)$)
The optimal strategy is to accept $x$ if $x \geq \alpha E_1$, and reject if $x < \alpha E_1$. Denote the threshold $\theta = \alpha E_1$.
The expected payoff is:
$E_1 = \int_0^1 \max(x, \theta) \, dx$
Split the integral at $\theta$:
$E_1 = \int_0^{\theta} \theta \, dx + \int_{\theta}^{1} x \, dx = \theta^2 + \frac{1 - \theta^2}{2} = \frac{1 + \theta^2}{2}$
Substitute $\theta = \alpha E_1$:
$E_1 = \frac{1 + \alpha^2 E_1^2}{2}$
$2E_1 = 1 + \alpha^2 E_1^2$
$\alpha^2 E_1^2 - 2E_1 + 1 = 0$
By the quadratic formula:
$E_1 = \frac{2 \pm \sqrt{4 - 4\alpha^2}}{2\alpha^2} = \frac{1 \pm \sqrt{1 - \alpha^2}}{\alpha^2}$
We need $E_1 \leq 1$ (since all payoffs are in $(0, 1)$). The $+$ root gives:
$\frac{1 + \sqrt{1 - \alpha^2}}{\alpha^2} \geq \frac{1 + 0}{\alpha^2} = \frac{1}{\alpha^2} > 1$
So we take the $-$ root:
$E_1 = \frac{1 - \sqrt{1 - \alpha^2}}{\alpha^2}$
Sanity checks:
- As $\alpha \to 0$: $\sqrt{1 - \alpha^2} \approx 1 - \alpha^2/2$, so $E_1 \approx (\alpha^2/2)/\alpha^2 = 1/2$. Correct -- if waiting is very costly (range shrinks fast), you just take the first draw, which has mean /2$.
- As $\alpha \to 1$: $\sqrt{1 - \alpha^2} \to 0$, so $E_1 \to 1/\alpha^2 \to 1$. Correct -- if the range barely shrinks, you can wait for a value near 1.
For $\alpha = 1/2$:
$E_1 = \frac{1 - \sqrt{1 - 1/4}}{1/4} = \frac{1 - \sqrt{3/4}}{1/4} = 4\left(1 - \frac{\sqrt{3}}{2}\right) = 4 - 2\sqrt{3}$
$\sqrt{3} \approx 1.7321$
$E_1 \approx 4 - 3.4641 = 0.5359$
The optimal threshold at turn 1 is $\theta = \alpha E_1 = 0.5 \times 0.536 \approx 0.268$. So you accept the first draw if it exceeds $0.268$, which happens about $73\%$ of the time.
Answer: The expected payoff under optimal play is:
$E_1 = \frac{1 - \sqrt{1 - \alpha^2}}{\alpha^2}$
For $\alpha = 1/2$: $E_1 = 4 - 2\sqrt{3} \approx 0.536$.
Intuition
This problem is a beautiful example of how self-similarity simplifies optimal stopping. The multiplicative shrinkage of the uniform range means the game at each turn is a scaled copy of the original game. This lets you collapse an infinite-horizon problem into a single fixed-point equation. The threshold rule -- accept if the draw exceeds the continuation value -- is a general principle in optimal stopping, but here the self-similarity makes the continuation value proportional to the current-turn expected payoff, yielding a clean quadratic.
The formula $E_1 = (1 - \sqrt{1 - \alpha^2})/\alpha^2$ has a nice interpretation: the cost of waiting is encoded in $\alpha$. When $\alpha$ is close to 1, waiting is nearly free (the range barely shrinks), so you can be very selective and your expected payoff approaches 1. When $\alpha$ is small, each rejection dramatically shrinks your opportunity set, so you should accept almost anything -- your payoff approaches
/2$, the mean of the first draw. In trading, this same structure appears in market-making decisions: each moment you wait to fill an order, the opportunity might shrink, and the optimal strategy balances the option value of waiting against the decay in available edge.