在独立增量模型下，每轮贪心选择最优解是全局最优的。
Greedy Selection under Independent Increments: A Toy Model Analysis
- 每轮保留当前值最高的若干过程，基于独立增量假设
- 证明贪心策略能选出最终最大值过程，无需回溯
- 适合理解高维场景中多阶段淘汰算法的原理
我们研究了在 N 个独立同分布的离散时间随机过程（具有独立增量）上的迭代选择问题。每一轮根据观测值保留固定数量的过程。在此简单模型下，我们证明：为选出最终最大值过程，最优策略是在每轮都采用贪心选择。尽管该结论依赖于强独立性假设，但它为多阶段淘汰场景中的贪心启发式方法提供了清晰的理论支持，并可作为理解高维应用中相关算法的简化范例。
原文摘要 · Abstract (English)
We study an iterative selection problem over N i.i.d. discrete-time stochastic processes with independent increments. At each stage, a fixed number of processes are retained based on their observed values. Under this simple model, we prove that the optimal strategy for selecting the final maximum-value process is to apply greedy selection at each stage. While the result relies on strong independence assumptions, it offers a clean justification for greedy heuristics in multi-stage elimination settings and may serve as a toy example for understanding related algorithms in high-dimensional applications.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。