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

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我们可以计算出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)