Uniform Sampling Game - Fair Price
Bob plays an optimal-stopping game. A fresh value $v$ is drawn uniformly from $[0, n]$. After seeing the current draw Bob either KEEPS it (the game ends and he is paid $v$ dollars) or pays a resample fee of $d$ dollars to throw the value away and draw again. There is no limit on the number of resamples. The first draw is free; every resample after that costs $d$.
Bob plays the value-maximizing strategy, which is a single threshold: keep the current draw iff it is at least the optimal threshold $T = n - \sqrt{2 n d}$, otherwise pay $d$ and redraw. Under this policy each individual draw stops the game with probability $p = (n - T)/n$, so the number of draws is geometric and the expected number of resamples is $E[\text{resamples}] = T/(n - T)$. The expected payout conditioned on stopping is the mean of a uniform variable above the threshold, $E[v \mid v \ge T] = (n + T)/2$.
A player pays an entry price $x$ up front to play, then receives Bob's net result (payout minus all resample fees). The FAIR price is the $x$ at which the player's expected profit is exactly zero:
$x = \dfrac{n + T}{2} - d \cdot \dfrac{T}{n - T}$.
Implement calc_optimal_price(n, d) returning this fair price $x$ as a float (full precision, NOT rounded to the nearest cent).
I/O contract: inputs are two numbers n (the upper bound of the uniform draw, $n > 0$) and d (the per-resample fee, $0 < d < n/2$ so that $T$ lies strictly in $(0, n)$). The function returns one float, the fair entry price.
Worked example: calc_optimal_price(100, 8). Here $T = 100 - \sqrt{2 \cdot 100 \cdot 8} = 100 - \sqrt{1600} = 100 - 40 = 60$. The expected payout is $(100 + 60)/2 = 80$, the expected number of resamples is $60/(100 - 60) = 1.5$, so $x = 80 - 8 \cdot 1.5 = 80 - 12 = 68.0$.
Hints
- First compute the threshold $T = n - \sqrt{2 n d}$ with
math.sqrt. - The expected payout is the mean of a uniform draw above $T$, namely $(n + T)/2$; the expected number of resamples is $T/(n - T)$.
- Assemble the answer as expected payout minus fee times expected resamples: $x = (n + T)/2 - d \cdot T/(n - T)$. Return the raw float without rounding.
Worked Solution
How to Think About It: This builds on the optimal-stopping threshold $T = n - \sqrt{2nd}$: Bob keeps a draw iff $v \ge T$. The fair entry price is Bob's expected *net* winnings under that policy — expected payout minus expected resample fees. Each draw independently stops the game with probability $p = (n - T)/n$, so the number of draws is Geometric($p$) with mean $n/(n - T)$; since the first draw is free, the expected number of *paid* resamples is $n/(n-T) - 1 = T/(n - T)$. The payout, conditioned on stopping, is uniform on $[T, n]$ with mean $(n + T)/2$.
Algorithm:
- Threshold: $T = n - \sqrt{2 n d}$.
- Expected payout: $E[v \mid v \ge T] = (n + T)/2$.
- Expected fees: $d \cdot T/(n - T)$ (geometric draw count, first draw free).
- Fair price: return $x = \dfrac{n + T}{2} - d \cdot \dfrac{T}{n - T}$ at full float precision — do not round.
Code:
```python import math
def calc_optimal_price(n, d): T = n - math.sqrt(2 * n * d) return (n + T) / 2 - d * (T / (n - T)) ```
Complexity: $O(1)$ time and space — a square root and a few arithmetic operations.
Answer: $x = \frac{n + T}{2} - \frac{dT}{n - T}$ with $T = n - \sqrt{2nd}$. Check with $n = 100$, $d = 8$: $T = 60$, payout $= 80$, resamples $= 1.5$, so $x = 80 - 12 = 68$. (The constraint $0 < d < n/2$ keeps $T \in (0, n)$, so the division is safe.)
Intuition
The threshold $T = n - \sqrt{2 n d}$ is exactly the point where the marginal benefit of one more draw equals its cost $d$. Above $T$ you keep; below it you pay to redraw. Once you fix that policy the game is a geometric process: each draw independently stops with probability $p = (n - T)/n$, giving $E[\text{resamples}] = (1-p)/p = T/(n - T)$, and the kept value is uniform on $[T, n]$ with mean $(n + T)/2$. The fair price is just expected payout minus expected total fees. Equivalently, the fair price is the fixed point $V$ of the Bellman optimality equation $V = E[\max(v, V - d)]$ for $v \sim U[0, n]$: the value of playing optimally is the same number a risk-neutral player should pay to enter.