sizheng
一个整数样本空间,比如32位无符号整数空间,其中有若干值作为有效值,比如比例为15%的值,但是这些值都是哪些并不清楚,而且分布不均匀。
为了对这些有效值进行随机采样,现把整个32位整数空间均匀划分为N个区间。由于有效值的分布不均匀,所以各个区间中的有效值比例不同,对各个区间随机采样的命中率也就不同。那么就可以根据各区间的命中率,自适应地调节在各区间的采样概率,再将各区间中的不重复采样次数考虑进来,就能避免局部最优。
那么整个过程,总体命中率的期望值,应该就是整个样本空间中的有效值比例,比如前面提到的15%。但是通过这种自适应的采样方法,可以在采样前期尽快地采样到更多的有效值。
但是考虑N=1和N=2^32两种极端情况,实际上两种情况均退化为在整个样本空间的随机采样。
那么我们考虑,或许N值有一个或多个最优值,能够在尽量少的采样次数中采样到尽量多的有效值,也就是在前期得到尽量高的总体命中率。
想来应该是个N和采样次数S的函数F(N,S)的最优化问题?
目前只能通过实验来观察、验证,但是不知该怎么用数学推导来讨论这个问题?