使用以下算法找到近似最小值的预期更新次数

Question

考虑以下代码：

public int find_exponent(array) {
    int count = 0;
    double min = epsilon;
    for (int i=0; i<array.length; i++) {
      if (array[i] < min) {
        count++;
        min = min/2;
      }
    }
    return count;
}

假设输入数组的长度为 n 并且从某个未知密度 f 随机生成（并且条目是 iid 并且范围 [0, 1]）。 count 的期望值是多少？我知道由于底层密度是未知的，所以不可能得到一个明确的解决方案，但我想要的是一个根据 f（或相应的 CDF：F）和 min 的初始猜测即 epsilon 的解决方案。

注意：我对在给定数组中找到确切的最小值不感兴趣

Answer 1

您可以通过以下方式解决这个问题。

首先，我认为 min 的类型应该是 float/double，因为您的数组 array 的值在 [0, 1] 范围内。现在，将 F 定义为

F(x) = P(X <= x)

即累积密度函数和 G(i, c) 是 i-th 迭代后我们得到 count == c

的概率

你可以看到：

G(x, c) = P(X >= eps/2^c)*G(x, c) + P(X <= eps/2^(c-1))*G(x, c-1) =
(1-F(eps/2^c))*G(x, c) + F(eps/2^(c-1))*G(x, c-1)

请注意，由于 G(0, 0)=1 我们可以使用 bottom-up 方法计算 G(x, c), for 0<=x<=n, 0<=c<=n。

这是 G 的前几个值：

G(0, 0) = 1

G(1, 0) = 1-F(e)
G(1, 1) = F(e)

G(2, 0) = (1-F(e))^2
G(2, 1) = F(e)(1-F(e)) + F(e)(1-F(e/2))
G(2, 2) = F(e)F(e/2)

预期的 count 将是：

E[count] = 0*G(n,0)+1*G(n,1)+...+n*G(n,n)

使用以下算法找到近似最小值的预期更新次数

Expected number of updates to find approximate minimum using the following algo

algorithm

probability

min