考虑以下代码:
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 的解决方案。
注意:我对在给定数组中找到确切的最小值不感兴趣
最佳答案
您可以通过以下方式解决此问题。
首先,我假设 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)
关于algorithm - 使用以下算法找到近似最小值的预期更新次数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35044578/