假如一个网站的userid是从1开始依次递增,如何估计这个网站的用户数?

假设有这么一个网站,它的userid是从1开始依次递增(step=1),我们想知道这个网站有多少用户,那么最简单的方式就是,马上去注册一个新用户,然后看看userid是多少。假设这个方法不可行,比如,这是一个需要邀请才能注册的论坛。我们只能从这个论坛的帖子中,提取userid,来估计。那么该怎么估计?

假设用户的总数为N,那么userid的取值范围就是[1,N]。假设我们取到n个样本,这n个样本的userid的最大值是maxU,最小值是minU,那么用maxU估计N行不行?当然可以。但是毫无疑问,maxU肯定是小于等于N的,那么到底小多少呢?如何从样本中把这个差值估计出来?假如我们把样本的userid按照从小到大排列,可以得到下面这个公式:

result=maxU + (相邻两个userid的间隔)的均值。

例如样本是: 1,3,5,8,那么result= 8 + {(8-5)+(5-3)+(3-1)}/3。

上面那个公式,化简后可以得到:result=max+(max-min)/(n-1)-1。

可以证明,上面这个式子的数学期望恰好就是N。

北大数院的郑忠国教授,给出了另一个公式,result2=(n+1)*max/n -1,这个式子的数学期望恰好也是N,但是是所有估计公式中,方差最小的一个。

我写了一段程序试了一下,让N=1000万左右,然后取1000个样本做估计,结果如下:

总体=10007351,样本=1000,估计方式1=10016532,估计方式2=10016523,max=10006518,min=962
总体=10005331,样本=1000,估计方式1=9994145,估计方式2=9994140,max=9984157,min=4534
总体=10008413,样本=1000,估计方式1=10005253,估计方式2=10005248,max=9995254,min=4678
总体=10003869,样本=1000,估计方式1=10005421,估计方式2=10005413,max=9995419,min=1482

如果把样本数减少到10:

总体=10001094,样本=10,估计方式1=10669213,估计方式2=10608249,max=9643864,min=415708
总体=10002488,样本=10,估计方式1=10456242,估计方式2=10419921,max=9472657,min=620381
总体=10008942,样本=10,估计方式1=8520014,估计方式2=8437255,max=7670233,min=22194
总体=10008863,样本=10,估计方式1=10996233,估计方式2=10928271,max=9934793,min=381823

肉眼可见,得到的结果要比未修正之前,好很多。

程序如下:

public class TestN {
    static public void main(String[] args){
        java.util.Random rand=new java.util.Random();
        int N=rand.nextInt(10000)+10000000;
        java.util.LinkedList<Integer> numbers=new java.util.LinkedList<Integer>();
        for(int i=0;i!=N;++i){
            numbers.add(i);
        }
        int n=10;
        long max=-1;
        long min=Integer.MAX_VALUE;
        for(int i=0;i!=n;++i){
            //随机抽取一个样本
            int p=numbers.remove(rand.nextInt(numbers.size()));
            max=Math.max(p, max);
            min=Math.min(p, min);
        }
        long result1=max+(max-min)/(n-1)-1;
        long result2=(n+1)*max/n -1;
        System.out.println(String.format("总体=%d,样本=%d,估计方式1=%d,估计方式2=%d,max=%d,min=%d\n", N,n,result1,result2,max,min));
    }
}

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥