Ski Rental 问题

等待购买保留了“明天就结束”的可能，代价是不断付租金；立即购买锁定长期成本，代价是可能只用一天。阈值的作用是限制此前已付租金：一旦它快追上购买价，继续等待就可能使两份费用同时失控。

图中算法在购买后成本变平，离线成本在租金累计到买价时变平。最坏差距应在购买附近计算，不能只看长期两条曲线都不再增长。

成本与确定性下界 ​

取 $B=5$。使用四天时，阈值策略花 4 元，与离线相同；第五天开始购买，累计花 $4+5=9$ 元，而离线花 5 元，比率为 $9/5$。此后使用多久，算法都不再付费，故比率不再增加。

任意确定性策略在每天持续需要使用的历史上，都有一个固定的首次购买日 $d$，或者永不购买。若 $d\le B$，对手取 $T=d$，比率为

若 $d>B$，同样取 $T=d$，比率为 $(d-1+B)/B\ge 2$。永不购买则让 $T$ 任意长，比率无界。这覆盖了所有确定性选择，并证明阈值 $d=B$ 最优。这里对手只需预先知道确定性策略，无须在运行中偷看未来。

哪些改动会改变结论 ​

若 $B$ 不是整数，购买日仍须为整数，要重新比较相邻阈值；不能直接写“租 $B-1$ 天”。若购买发生在当天租金支付之后，购买当天的成本也会改变。允许退款、二手残值、变化的租金或结束时间预测时，离线基准与阈值都要重新计算。

随机购买时间怎样改善保证 ​

在连续时间版本，把购买价与时间单位归一化为 1。令随机购买时刻 $X\in [0,1]$ 的密度为

这确是分布，因为其积分为 1。对固定结束时间 $0<t\le 1$，已买的人付 $X+1$，尚未买的人付 $t$，所以

此式对 $t$ 的导数为 $f(t)+\text{Pr}(X>t)=e/(e-1)$，且零时成本为零，因此期望成本为 $et/(e-1)$。当 $t\ge 1$，人人已买，期望成本固定为 $e/(e-1)$。于是对每个固定 $t>0$，期望成本与 $min(t,1)$ 的比均为 $e/(e-1)$。注意递增的是购买时刻密度；生存概率为 $(e-e^t)/(e-1)$，不能笼统说成指数衰减。

这是随机化算法理路随机化算法Randomized algorithm把随机比特作为额外输入并分析输出正确率或运行时间分布的算法。面对预先固定结束时间的保证。若结束时间可以根据是否已买而改变，上述固定 $t$ 的积分不再是同一个实验。离散天需要另设离散购买概率，不能原样套用密度。预测辅助方案则还需分别说明预测准确与预测失准时的保证。