这是 StackOverflow 的衍生产品question.
假设你有一个固定的号码k存储位置和两个柜台的空间。您将收到n随机顺序的项目（所有排列n项的可能性相同）。收到每件物品后，您可以将其存放在其中一个k位置（丢弃先前存储的值之一），或丢弃该项目。您还可以递增或递减任一计数器。任何丢弃的物品都无法找回。
问题是
- 最大化找到准确中位数的概率的策略是什么？
- 这个概率是多少？
显然，如果k > n/2，我们可以找到中位数。一般来说，尝试保持丢弃的高值的数量等于丢弃的低值的数量的相同策略似乎应该是最佳的，但我不确定如何证明它，也不知道如何计算它找到的概率中位数。
同样有趣的是我们不知道的情况n但知道概率分布n.
Edit:现在假设这些值是不同的（没有重复）。但是，如果您也可以解决非不同的情况，那么这将令人印象深刻。
Munro 和 Paterson 在他们的论文中本质上研究了这个问题有限存储的选择和排序。他们表明，您的算法需要 k = Ω(√n) 才能以恒定概率成功，并且通过利用一维随机游走的基本结果，这是渐近最优的。
如果我想证明绝对最优性，我首先要尝试的是考虑任意算法 A，然后couple它使用算法 A' 执行，当 A 第一次偏离您的算法时，您的算法会改为执行，然后尝试尽可能接近地遵循 A。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
