Ski Rental 问题

过早购买会在季节立即结束时浪费买价，过晚购买又会在长季节里累积过多租金。确定阈值把两类最坏损失平衡在购买价附近；随机购买时间则把固定停止日面对的期望比率摊平，但只在对手看不见随机结果时保留优势。

随机与边界 ​

随机购买时刻可对 oblivious 对手达到 $e/(e-1)$ 量级；若 adaptive 对手观察购买决定后再选择结束，保证会改变。取消、残值、非恒定租金或预测信息都会形成新模型。

买入日的 off-by-one 必须与“当天先租还是先买”约定一致。

离散日与连续时间的随机常数和归一化略有差别。引用竞争比时必须同时标明时间模型、购买发生在当天何时，以及对手能观察哪些随机动作。

确定阈值的逐日成本 ​

约定前 $B-1$ 天租，第 $B$ 天若仍滑雪则先买。若 $T=B-1$，ALG=OPT=$B-1$；若 $T=B$，ALG=$2B-1$、OPT=$B$；若更长，ALG 不再增加。最坏比率 $2-1/B$ 正出现在购买当天附近。

任意确定算法等价于某个首次购买日 $d$（或永不买）。对手若在 $d$ 天结束，使算法既付此前租金又购买；若 $d$ 太晚则让季节很长。平衡两类损失得到阈值约 $B$，形成接近 2 的下界。

随机购买时间 ​

作为随机化在线算法公理库随机化算法Randomized algorithm把随机比特作为额外输入并分析输出正确率或运行时间分布的算法。，连续版本选择购买时间分布，使 survival function 按指数衰减；对每个固定停止时间，期望成本与 OPT 的比率被平衡到 $e/(e-1)$。离散天需要归一化和 off-by-one 修正。每天独立固定概率购买对应几何分布，未必是有限截断模型的最优分布。

保证面对 oblivious 停止时间。若对手观察是否已买再决定当天结束，可专门在购买后停止，随机优势可能消失。

模型变化 ​

有二手残值、购买可取消、每日租金变化或可靠使用期预测时，OPT 与阈值都改变。Prediction-augmented ski rental 会在预测准时改善、预测错时保持鲁棒比；不能仍引用原始 $e/(e-1)$ 当完整结论。