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

Question

这是对此StackOverflow 问题的一个衍生。

假设您有固定数量的存储位置k和两个计数器的空间。您将以随机顺序收到n个项目（所有n个项目的排列方式都是等可能的）。在收到每个项目后，您可以将其存储在k个位置之一中（丢弃先前存储的一个值），或者丢弃该项目。您还可以增加或减少任何一个计数器。任何被丢弃的项目都无法恢复。

问题是：

1.最大化找到确切中位数的概率的策略是什么？ 2.那个概率是多少？

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

同样有趣的是，当我们不知道n但是知道n的概率分布时。

编辑：现在假设这些值是不同的（没有重复）。然而，如果您也能解决具有重复值的情况，那将会很令人印象深刻。

- deinst

Answer 1

Munro和Paterson在他们的论文“带有有限存储器的选择和排序”中研究了这个问题。他们表明，你的算法需要k = Ω(√n)才能在恒定概率下成功，并且通过引用关于一维随机行走的基本结果，证明了这是渐近最优的。

如果我想证明绝对最优性，我会首先考虑任意算法A，然后将其执行与算法A'耦合，A'在A第一次偏离你的算法时，会执行你的算法，然后尽可能地跟随A。

- user382751

Answer 2

一个猜测：丢弃距离当前存储值的平均值最远的元素。

如果值的分布是多模式的，并且我们首先从非主导模式获取值，则与当前中位数进行比较不起作用。

- Mau

---

我们不一定能够计算平均值。中位数只需要一个完全排序，而平均数需要算术属性。如果所有排列都是等可能的，多峰性可能不是问题，但这提醒我应该注意到这些值可以被视为不同的。（我认为这会使数学更容易。） - deinst

嗯，有趣。我没考虑过非数值的情况。 - Mau