分布中位数与内存约束

Question

任务

我想近似给定分发的中位数 $ d $ 我可以从中采样。

一个简单的算法，使用 $ n $ 样本，是：

samples = [D.sample() for i in range(n)] # generate n samples from D
sort(samples)
return samples[n/2]

. 但是，我正在寻找一种算法，即需要小于 $ o（n）$ 空间。

思想

我看过这些算法：

• 中位数：需要 $ o （n）$ 空间，所以它对我不起作用。
• 随机中位数：似乎这可以很容易地推广到使用 $ o（n ^ {3/4}）$ 空格的算法。

是否有任何其他算法使用少于 $ o（n）$ 空格，可以解决我的问题？特别是，我认为可以有一个算法可以通过生成来使用 $ o（m）$ 空间使用 $ o（m）$ 空间$ d $ size $ m $ ...

详细信息

• 理想情况下，我正在寻找对算法的参考，该算法还包括分析（成功概率，预期的运行时等）。
实际上，我需要一种算法来估计 $ d $ s $ p $ -th百分位数对于给定的 $ p $ ，但我希望大多数中位数发现算法概括为。
• 我希望达到与上面所示的简单算法相同的准确性。实现这一目标的一种方法是通过使用其输出分布与样本算法相同的算法（但是可能在罕见情况下可能失败的新算法）

Answer 1

当然，您可以使用更多的运行时间来实现这一点。这是一种概念上简单的方法，可能不是最佳的，但会让你开始，可能很好：

使用二进制搜索查找近似中位数 $ m $ 。你如何知道是否是候选者 $ m $ 太大或太小？ sample $ n'$ 从分布中的时间，计算样本是 $ \ ge m $ 的次数，并将其与 $ n'/ 2 $ 进行比较。这可以用 $ o（1）$ 空间来完成。

然后关键问题变成：我们如何选择 $ n'$ ，以控制错误的概率？一个简单的方法是选择 $ n'$ 足够大于 $ n $ 的概率二进制搜索的每次迭代中的错误是 $ t $ 小于使用 $ n $ 时出错的概率样本，其中 $ t $ 是实现所需精度所需的二进制搜索的迭代次数。然后，联盟绑定确保这将符合您的准确性条件。

不幸的是，当我们对数据分发的任何东西都没有任何了解数据时，您的准确性条件有点难以使用，因为样品中位数的准确性可以是任意差的。例如，考虑输出 $ 0 $ 的分发，具有概率 $（1- \ epsilon）/ 2 $ $ 100 $ 具有概率 $（1+ \ epsilon）/ 2 $ 。然后样品中值大约可能是0或100，而分配中位数为100， 因此，样本中位数的平均误差约为50（除非您绘制 $ \ gg 1 / epsilon ^ 2 $ 样本）。这是一个特别讨厌的分布，它会努力工作。但是如果您假设分布是高斯（例如）使用标准偏差 $ \ sigma $ ，那么样本中位数的错误，带 $ n $ 样本，大致 $ 1.25 \ sigma / \ sqrt {n} $ 。因此，可以使用上述算法，其中我们设置 $ t \ them \ lg（\ sqrt {n} /1.25）$ ，我们设置 $ n'\大约nt ^ 2 $ 。

这是一种简单的方法。你可能做得更好。您可能想查找用于计算中位数的流算法，因为它们解决了您正在使用的问题：给出了来自分布的无限数量的样本，但只有有限的空间，我们可以获得最佳估计中位数？例如，这里是一种简单的算法：第一层重复服用三个样本并输出那三个的中位数;第二层反复从第一层中取三个数字，并输出那些三个的中值;等等。在对数的层数之后，您可以获得与中位数合理的近似值。这个主题有一个整个文学，你应该能够更多地找到更多。