4

考虑一组从范围中以均匀概率分布选择的隐藏k随机数，其中 N 对我来说是未知的。在每个时间间隔中，数字都会显示给我，如果我还没有选择，我可以选择作为我的最终数字，或者继续下一个时间间隔。当向我透露时，我无法再选择任何一个。如果在显示时我还没有选择一个数字，那么默认情况下，它变成.{r1,r2...rk}[0..N]ririccrir1,r2..r(i-1)rkc

我想优化 c，在某种意义上最大化它的期望值。

如果N知道，那么答案是显而易见的。同样，如果k很大，那么我可以使用 的早期值ri来估计N。

目前进展：

如果k = 1那么没有选择。默认情况下c=r1。的期望值c为N/2。

如果k = 2那么所有选择算法都与期望值相同N/2。

如果k = 3那么最好的算法是

if r2/r1 >= 0.75 then 
  c=r2
else
  c=r3

的期望值c约为0.58N。

如果k = 4那么我想出的最好的就是

if r2/r1 > 0.920 then
  c=r2
elseif r3/r1 > 0.665 then
  c=r3
else
  c=r4

的期望值c约为0.64N。r1我相信我应该能够通过“使用”的值和r2选择是否接受作为我选择的值来做得更好，r3但是分析解决方案使我无法理解。

k=4任何人都可以为和/或提供更好的算法k=5吗？

关于秘书问题的注释： 在我能找到的所有版本的 SP 中，只有你有关于候选人与已经出现的候选人的相对等级的信息。但是在这个问题中，每个候选者都有一个值（当然来自未知范围 [0..N]），并且通过利用值的比率，您可以做得更好。例如，k=3 问题的 SP 解决方案（如果 p2 > p1 选择 p2 否则选择 p3）的预期回报为 o.5833N，而我的解决方案（如果 p2/p1 > 0.75 选择 p2 否则选择 p3）有预期回报为 0.5937。

到目前为止，我对任何 k 问题的最佳回报是：

 i = 0    
 repeat
    inc(i)
 until (r[i]/Max(r[1]..r[i-1]) > V[i]) or (i=k)
 c=r[i]

其中对于任何选择的 k，v[i]（或者如果您愿意，也可以称之为 v[k,i]）是一个预先选择的实数值数组。秘书问题的标准解决方案仅使用 VV=[inf,...inf,1,...,1] 中的 inf 和 1 的值，而我可以通过在V. 但我相信我的解决方案仍然是次优的，因为我只使用 Max(r1..ri) 的值，而在每个决策点的 r1..ri 值的分布中必须存在“隐藏”信息。

迄今为止的最佳解决方案：

k = 3 : v = [inf,0.75]          : cexp = 0.58N
k = 4 : v = [inf,0.92,0.66]     : cexp = 0.665N
k = 5 : v = [inf,inf,0.82,0.63] : cexp = 0.6683N
4

3 回答 3

3

它是最优停止理论中“秘书问题”的众多修改之一。对于您的具体问题，我没有现成的答案，但我强烈建议您阅读这个“秘书问题”。有很多关于它的论文，我相信你会为此找到一些东西。

于 2012-08-08T08:01:31.630 回答
2

请注意，您可以做得比N/2for更好k=2：

  • 猜测N/2并调用它m。
  • 如果r1 > m接受它作为c，否则拒绝并选择r2作为c。

这是该策略的预期。

  • 如果m ≥ N, 那么它总是拒绝r1和接受r2, 的期望值c为N/2.
  • 如果m < N，那么它接受：
    • r1有概率(N-m)/N
    • r2剩余概率概率m/N

在第二种情况下，期望r1是Σ_{m<i≤N} i / (N-m) > N/2，而期望r2是N/2。在第二种情况下，整体策略的期望值大于N/2。

如果你能很好地猜测 ，这个策略会更好N/2，但可爱的事实是你不会出错：即使你错了，这个策略至少会产生N/2预期。

于 2012-08-08T08:43:05.450 回答
1

为什么最好的解决方案只涉及将 r i与 Max(r 1 , r 2 , ..., r i ) 进行比较，这可能是有充分理由的：德国坦克问题。

假设您刚刚看到倒数第二个数字 r k-1。考虑一下你当时的决定是什么。您可以选择 r k-1或等待查看尚未公开的 r k。什么时候应该选择 r k-1？当你认为 r k-1大于 r k = N/2 的期望值时。但是，如果你不知道 N，你如何估计rk的期望值呢？好吧，你可能会做的是估计 N。你是怎么做的？您使用仅依赖于观测值的最大值（和计数）的德国坦克问题的解决方案之一。

计算i < k-1的 ri 的情况不太简单。例如，当您查看 r k-2时，您需要弄清楚您会做什么，因为您还有两个数字要查看并且（可能）还有一个选择要做。但是，我怀疑在每种情况下，您正在做的关键事情是对 N 进行一些估计，这仅涉及迄今为止观察到的值的最大值和计数。

于 2012-08-09T15:53:39.907 回答