algorithm - 找到有限空间中位数的概率

Question

这是 StackOverflow 的衍生产品 question .

假设您有固定数量 k 的存储位置，以及两个计数器的空间。您将以随机顺序收到 n 个项目(n 个项目的所有排列的可能性均等)。收到每个项目后，您可以将其存储在 k 个位置之一(丢弃先前存储的值之一)，或者丢弃该项目。您还可以递增或递减任一计数器。任何丢弃的元素都无法找回。

问题是

1. 可以最大限度地提高找到准确中位数的概率的策略是什么？
2. 这个概率是多少？

显然，如果k > n/2，我们可以找到中位数。一般来说，试图保持丢弃的高值数量等于丢弃的低值数量的相同策略似乎应该是最优的，但我不确定如何证明它，也不知道如何计算它找到的概率中位数。

同样有趣的是我们不知道 n 但知道 n 的概率分布的情况。

编辑:现在假设值是不同的(没有重复)。但是，如果您也可以解决非不同的情况，那将是令人印象深刻的。

Answer 1

Munro 和 Paterson 在他们的论文中研究了这个问题 Selection and sorting with limited storage .它们表明您的算法需要 k = Ω(√n) 才能以恒定概率成功，并且通过求助于一维随机游走的基本结果，这是渐近最优的。

如果我想证明绝对最优性，我会尝试的第一件事是考虑任意算法 A，然后将它的执行与算法 A' 结合，第一次 A 偏离你的算法，你的算法会做，然后尝试尽可能接近 A。