algorithm - 从 4 或 5 个范围未知的均匀分布随机数中进行最佳选择

Question

考虑一组隐藏的 k 随机数 {r1,r2...rk} 从范围 [0..N ]，我不知道 N。在每个时间间隔内，数字 ri 都会显示给我，我可以选择 ri 作为我的最终数字 c，如果我还没有为 c 做出选择，或者继续下一个时间间隔。当 ri 显示给我时，我不能再选择 r1,r2..r(i-1) 中的任何一个。如果在显示 rk 时我还没有选择数字，那么默认情况下，它将变为 c。

我想优化 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])是一个预先选择的实数数组。秘书问题的标准解决方案仅使用 V V=[inf,...inf,1,...,1] 中的 inf 和 1 的值，而我可以通过使用实数做得更好(至少对于小 k) 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

Answer 1

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