平面点集的平均距离估算方法

KeyTo9_Fans

平面上有$n$个点，

它们的坐标分别是$(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$，

它们的平均距离等于$\sum_{i=1}^{n-1}\sum_{j=i+1}^n\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}/{{n(n-1)}/2}$。

当$n$很大的时候，例如：$n=10^8$，

上述式子需要花很长时间（$O(n^2)$）计算。

我现在有$2$种快速计算方法。

方法$1$：

在$n$个点里等概率地随机抽取的$k$个点，

然后以这$k$个点的平均距离来估算$n$个点的平均距离，

于是这个估算结果只需要$O(k^2)$的时间就能得到。

问题$1$：

这个估算结果是不是无偏估计（期望值与真实结果相同）？

如果是无偏估计，那么它的方差是多少？

方法$2$：

在$C_n^2$对点里等概率地随机抽取$k$对点，

然后对这$k$对点分别求距离，一共求出$k$个距离，

然后以这$k$个距离的平均值来估算$n$个点的平均距离，

于是这个估算结果只需要$O(k)$的时间就能得到。

问题$2$：

这个估算结果是不是无偏估计（期望值与真实结果相同）？

如果是无偏估计，那么它的方差是多少？

问题$3$：

在$k$个单位时间内（假设取点不花时间，求$1$次距离花$1$个单位时间），

有没有方差更小的无偏估计方法？

hujunhua

--

lsr314

这些点怎么分布？

wayne

楼上说的有道理，点的分布的数学模型 直接决定了 估算方法的模型。

mathe

无偏估计是显然的，但是方差会很难算。
比如第一种方案，实际上n个点里面选择k个点有$C_n^k$中选择方案，而这$C_n^k$种选择方案都是等概率选择的。
而这$C_n^k$种方案计算出来的结果在求平均显然还是原先的平均值。第二种方案也类似。
从直觉上看，方案二显然优于方案一

mathe

第二种方案相对比较好评估，我们只需要直到任意选择两个点，假设两点之间距离的平均值为a,均方差为b,那么取k对数据求平均后均值还是a,而均方差会变为$b/{\sqrt{k}}$,所以在对所有数据的范围有个大概了解的情况下面，可以非常容易估算出大概需要挑选多少对数据就可以达到需要的精度