找到有限空间中值的概率

Question

这是StackOverflow 问题的衍生产品.

假设您有一个固定数量k的存储位置,以及两个计数器的空间.您将收到ñ随机顺序的项目(的所有排列ň项目也同样可能).收到每个项目后,您可以将其存储在k个位置之一(丢弃之前存储的值之一),或丢弃该项目.您也可以递增或递减任一计数器.无法检索任何丢弃的项目.

问题是

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

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

同样感兴趣的是我们不知道的情况下ñ但要知道的概率分布ñ.

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

Answer 1

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

如果我想证明绝对最优性,我首先要考虑的是考虑一个任意算法A,然后将其执行与算法A'结合起来,这是第一次A偏离你的算法时,你的算法会改为做然后尝试尽可能地密切关注A.