寻找具有有限的空间中位数的概率 [英] Probability of finding the median with finite space

问题描述

这是一个分拆这个计算器<一的href="http://stackoverflow.com/questions/3372006/incremental-median-computation-with-max-memory-efficiency">question.

假设你有两个计数器的固定数量的 K 的存储位置和空间。您将收到的 N 的随机顺序的项目（的所有排列的的 N 的项目也同样可能）。接收每个项目后，您可以将其存储于一体的的 K 的位置（丢弃一个$ P $的pviously存储值），或放弃该项目。您也可以增加或减少一个计数器。丢弃的项目不能被恢复。

的问题是

1. 什么是最大化找到确切的中位数？
您的几率战略
2. 什么是概率？

显然，如果 K> N / 2 的，我们能找到的中位数。一般看来，尝试同样的策略，以保持抛弃高值等于丢弃低值的数量应该是最佳的数目，但我不知道如何来证明这一点，也没怎么搞清楚的概率是它找到中位数。

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

编辑：现在假设值是不同的但是，如果你能解决不显着的情况下为好，那么这将是即时通讯pressive

解决方案

蒙罗和帕特森在他们的论文研究基本上是这个问题的选择和有限的存储空间排序。他们表明你的算法需要K =Ω（√N）恒定的概率获得成功，并认为这是渐近最优诉诸基本结果大约一维随机游动。

如果我想证明绝对最优的第一件事，我会尝试将考虑一个任意的算法，然后的夫妇的它的执行有一个算法A'的是，第一次从偏离你的算法，你的算法会做，而不是，然后尝试遵循尽可能接近，因为它可以。

This is a spin off of this StackOverflow question.

Assume that you have a fixed number k of storage locations, and space for two counters. You will receive n items in random order (all permutations of the n items are equally likely). After receiving each item you can either store it in one of the k locations (discarding one of the previously stored values), or discard the item. You can also increment or decrement either of the counters. Any discarded item cannot be retrieved.

The questions are

1. What is the strategy that maximizes your probability of finding the exact median?
2. What is that probability?

Obviously, if k > n/2, we can find the median. In general it seems that the same strategy of attempting to keep the number of discarded high values equal to the number of discarded low values should be optimal, but I am not sure how to prove it, nor how to figure out the probability that it finds the median.

Also of interest is the case where we do not know n but know the probability distribution of n.

Edit: Assume for now that the values are distinct (no duplicates.) However, if you can solve the non distinct case as well, then that would be impressive.

解决方案

Munro and Paterson studied essentially this problem in their paper Selection and sorting with limited storage. They show that your algorithm requires k = Ω(√n) to succeed with constant probability and that this is asymptotically optimal by appealing to basic results about one-dimensional random walks.

If I wanted to prove absolute optimality, the first thing I would try would be to consider an arbitrary algorithm A and then couple its execution with an algorithm A' that, the first time A deviates from your algorithm, does your algorithm would do instead and then attempts to follow A as closely as it can.

这篇关于寻找具有有限的空间中位数的概率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！