Minimum Spread Tolerance for Target Fill Rate

做市算法的报价台需要确定价差预算：限价单的价格容忍窗口要开多宽，才能让算法在昨天的中间价 tape 上至少有 $\rho \cdot N$ 个历史 mid 跨过限价并成交？开得太窄成交率崩盘；开得太宽执行成本飙升。答案是最小阈值 $T$，使得在至少 $\lceil \rho N \rceil$ 个样本上 $|p_i - r| \le T$ 成立——其中 $r$ 是算法参考价（如理论公允价）。

实现 solution(prices, reference, target_ratio, abs_tol) -> float。返回满足成交率约束的最小 $T$。

结构是对连续阈值的 binary-search-on-answer：

1. 定义 $\mathrm{fill}(T) = \#\\{i : |p_i - r| \le T\\}$。该函数关于 $T$ 单调不降，因此谓词 feasible(T) = fill(T) >= ceil(target_ratio * N) 也单调。
2. 区间：$[\mathrm{lo}, \mathrm{hi}] = [0,\, \max_i |p_i - r|]$。下端通常不可行（除非所有偏差均为零），上端总是可行。
3. 二分：$\mathrm{mid} = (\mathrm{lo} + \mathrm{hi})/2$，可行 $\mathrm{hi} \leftarrow \mathrm{mid}$，否则 $\mathrm{lo} \leftarrow \mathrm{mid}$。$\mathrm{hi} - \mathrm{lo} < \mathrm{abs\_tol}$ 时停止。返回 $\mathrm{hi}$——已证明可行的最小阈值。

输入校验。 空 prices、target_ratio <= 0、target_ratio > 1 或 abs_tol <= 0 抛 ValueError。当 target_ratio = 1.0（或经向上取整后 required 等于 $N$），直接返回 $\max_i |p_i - r|$——bisection 同样会收敛到那里，但直接返回避免了等式边界上的浮点漂移。

示例

solution([97.0, 99.0, 101.0, 103.0], 100.0, 0.5, 1e-6) 返回约 1.0。相对 $r=100$ 的偏差为 $[3, 1, 1, 3]$，排序后 $[1, 1, 3, 3]$。$\rho = 0.5$ 需要 $\lceil 0.5 \cdot 4 \rceil = 2$ 个成交，第二小的偏差 $T = 1.0$ 即为答案。bisection 在 $[0, 3]$ 上收敛到 $\mathrm{abs\_tol} = 10^{-6}$ 内。

solution([100.1, 100.2, 100.3, 150.0], 100.0, 0.75, 1e-6) 返回约 0.3。偏差 $[0.1, 0.2, 0.3, 50.0]$。$\lceil 0.75 \cdot 4 \rceil = 3$ 个成交，第三小偏差 $0.3$ 胜出。离群值 $50.0$ 被忽略——这正是基于分位数的价差预算相对均值预算的核心优势。

solution([99.0, 100.0, 101.0, 102.0], 100.0, 1.0, 1e-6) 返回 2.0：$\rho = 1.0$ 强制全部成交，$T$ 至少为最大偏差 $\max(|99-100|, |100-100|, |101-100|, |102-100|) = 2$。求解器在 required==N 时直接返回最大值，避免 bisection 在边界上的浮点漂移。

参见 stubs/stub.py 的函数骨架。

实战背景

执行算法——VWAP、TWAP、POV、Implementation Shortfall——的标定需要历史成交统计：给定昨天的中间价 tape 相对公允价的偏差分布，限价单容忍窗口要开多宽，算法才能达到目标参与率？基于偏差均值设阈值非常脆弱：一根肥尾（一笔过期报价、一次 5 秒集合竞价不平衡）就把阈值拉高，算法在剩余时段普遍报价过宽。基于成交率的阈值则是偏差分布的分位数——天生抗离群。用 binary-search-on-answer 求解是经典模式：它直接推广到滑点预算（使 95% 执行滑点 $< \sigma$ 的最小 $\sigma$）、风险带尺寸（突破 $\le \alpha$ 历史日的最小 VaR 阈值），以及任何"满足频率目标的最紧阈值"型规约。本题归到 binary-search-on-answer cell，是因为 bisection 跑在答案空间（连续阈值 $T$）上，而非输入数组——每个候选 $T$ 处的 feasibility 才是内层谓词。同样模式在 coding-smallest-position-meeting-risk-budget（离散答案空间）以及做市台上任何"满足计数/单调约束的最紧参数"问题中反复出现。