长尾数学问题悬赏

阿北 03-08-2006

今天豆瓣小组里说梦痴·的的慢提了这样一个问题:

现在人数在50人以下的小组大约占了全部4000+个小组的90%,那么按照豆瓣的分布,这后90%的小组全部加起来一共有多少的出现几率?(在全部六个位置中)即我们有多大机会在“15分钟名组”看到一个不到50人的小组?10%?5%?1%?还是更少?

提的比较清楚的是后一个问题。重述在此:

在”15分钟名组”里看到(至少)一个不到50人的小组的几率有多少?

这其实是一个统计的问题。可以去做一个模拟,不过我想看看有没有更聪明的答案. 所以在这里公开征解。

先看看”15分钟名组”是怎么来的。豆瓣的FAQ说:

[6个"15分钟名组"]从所有小组里随机挑选。每15分钟更新一次。这个列表是为了打破以前“最受欢迎的6个小组”造成的贫富分化日巨问题。

但是不是所有小组都机会均等(这样的话,选中的小组基本上会只有一个成员)。小组成员越多,选中的机会越多。挑选是由豆瓣系统自动用随机数进行。所有小组按人气排队以后,选中的几率遵从一个长尾分布。所以即使只有一个人的小组也可能上榜,但极有可能是一个月里某一天的凌晨3点52分。

这个“长尾分布”, 豆瓣的程序里是用Pareto分布计算的。学统计的,或者看过Linked这本书的人应该知道。定义在这里:

http://www.answers.com/topic/pareto-distribution

豆瓣现在用的k=0.5 (就是Pareto Index, 也叫alpha). 排序(x)从1开始。此刻现在共有4154个小组,第421个小组以后成员数就小于50了.

第一个模拟出来的正确答案的,我请喝酒。第一个给出解析正解(就是用公式算出来)的,我送超女之一的亲笔签名T-Shirt (空白T-Shirt自备)。我还不知道正确答案,所以可能需要两个以上正解。

没准这个问题有一天会出现在研究生入学考试题里。:)

欢迎转发。

以下是相关回应

  1. 试着解”长尾数学问题悬赏”

    “长尾数学问题悬赏“是豆瓣的问题.概率从来都不是我的强项,不过试着解一下吧.
    求解之前先明确两个问题:
    1.我看分布公式应该是Pareto分布的离散形式zeta distribution.毕竟人数和时间…

    美人她爹 Says: 三月 9th, 2006 at 3:17 上午
  2. 1/n^0.5

    n 是序号,比如 n=421 的时候大约 4.87%

    anonymous Says: 三月 9th, 2006 at 9:44 上午
  3. 其实没必要用Pareto分布,或者任何分布。

    这些分布的目的是当不了解实际分布的时候,用来作为一种近似。对网站来说,实际各组的人数分布是已知的,直接用人数比率作为随机选择的概率就可以了。

    在这种情况下,所关心的概率就是所有”50人以下的小组”的总人数在总用户中的百分比。

    anonymous Says: 三月 9th, 2006 at 9:55 上午
  4. 某一个时间点的人数是已知的,但小组人数也是随时变化的哦,用不用Pareto分布,不是关键问题啊

    yuxiangrousi Says: 三月 9th, 2006 at 10:04 上午
  5. 模拟了一下,机会很渺茫,在抽样984621之后,只有大约0.034%的可能会出现50人一下小组:

    0$ python2.4 pareto.py
    0: 0.05102%(5, 98)
    1000: 0.03474%(3421, 98482)
    2000: 0.03427%(6751, 196986)
    3000: 0.03420%(10105, 295462)
    4000: 0.03416%(13455, 393880)
    5000: 0.03432%(16898, 492362)
    6000: 0.03409%(20146, 590923)
    7000: 0.03401%(23449, 689418)
    8000: 0.03394%(26736, 787827)
    9000: 0.03384%(29987, 886254)
    Result: 0.03372%, exceed: 33201, total: 984621

    模拟的程序:
    #!/usr/bin/env python
    import random
    def pareto_count(divide, maximum, alpha, times):
    samples = [int(random.paretovariate(alpha)) for i in range(times)]
    samples = [i for i in samples if i divide])
    return (exceed, len(samples))
    def longtail(divide, maximum, alpha):
    total = 0
    exceed = 0
    _tick = 1000
    for i in range(10000):
    e, t = pareto_count(divide, maximum, alpha, 100)
    total += t
    exceed += e
    if (i%_tick) == 0:
    print “%8d: %02.5f%%(%d, %d)” % (i,
    float(exceed)/total, exceed, total)
    print “Result: %02.5f%%, exceed: %d, total: %d” % (
    float(exceed)/total, exceed, total)
    ALPHA=0.5
    MAXIMUM=4154
    DIVIDE=421
    longtail(DIVIDE, MAXIMUM, ALPHA)

    xyb Says: 三月 9th, 2006 at 10:59 上午
  6. 对不起,上面忘了换算成百分数,实际上应该是3.3%+的出现概率。
    另外,python程序的缩进被html藏起来了,直接看html源代码,就可以看到正确的缩进格式了。

    xyb Says: 三月 9th, 2006 at 11:03 上午
  7. 如果把alpha值调整到0.1,大概就有刚刚不到20%的出现概率了。

    xyb Says: 三月 9th, 2006 at 11:05 上午
  8. 补充一下:

    这个 p=1/n^0.5 是任意一次被选到的概率。如果考虑每次选六个,至少被选到一个的概率,应该是 1 – (1-p)^6。

    对于n=421,这个值是大约 25.90%。也就是说,大约每个小时(4次),可以期望看到至少有一个小于50人的组,出现在列表上。

    不知道是否与实际看到的相吻合。

    anonymous Says: 三月 9th, 2006 at 11:38 上午
  9. 上面的模拟程序,不考虑大于4154的情况,这部分的概率大约是1.55%。从4.87%减去这个值后,得到3.32%。

    不知道网站的程序是怎么处理的。如果抽到大于4154的数就重新抽的话,实际概率应该是 3.32%/(1-1.55%) = 3.37%。

    anonymous Says: 三月 9th, 2006 at 11:52 上午
  10. 楼上说的应该差不多了

    说梦痴 Says: 三月 9th, 2006 at 12:12 下午
  11. Pareto distribution’s CDF is 1-(x_m/x)^k.
    Let,
    x_m=1, k=0.5.
    Hence, groups above rank 421 occurs for 1 time in a probability of, (1-1/421^0.5)/(1-1/4154^0.5)
    Groups above rank 421 occurs for 6 times: ((1-1/421^0.5)/(1-1/4154^0.5))^6.
    Hence, groups below rank 421 occurs for at least 1 time: 1-((1-1/421^0.5)/(1-1/4154^0.5))^6=0.186=18.6%

    Felix Says: 三月 9th, 2006 at 1:19 下午
  12. anonymous, 能给一个联系方式吗?豆油或者email: webmaster@douban.com .

    用Pareto最主要的原因是程序计算比用实际人数方便,而且实际小组人数的分布的确最像一个Pareto分布。本来就是一个概念性的作法,所以方便就可以了。实际用的就是xyb程序里的random.paretovariate, 一个python函数。

    xyb, 请豆油给我你的程序,网页上显示有问题。还有,再仔细看一下问题。:)

    阿北 Says: 三月 9th, 2006 at 1:21 下午
  13. According to the statement above, the probability of groups below rank 421 appearing in every 15 alteration is 1-(1-18.6%)^15=95.4%, which means those groups appears in every 3.5 hours.

    Felix Says: 三月 9th, 2006 at 1:30 下午
  14. Felix, 你和anonymous所见略同。

    阿北 Says: 三月 9th, 2006 at 1:31 下午
  15. Felix, 和你理解的有不同。”15分钟名组”是每15分钟更新一次。每次更新的时候重新随机挑选。

    阿北 Says: 三月 9th, 2006 at 1:38 下午
  16. :) 其实我就是这个意思。大概每15次有95%的可能性出现一次50人以下的小组。那就是3个半钟头了。

    ps. ubuntu dapper下的opera打中文有点问题…刚中文打中文

    Felix Says: 三月 9th, 2006 at 1:45 下午
  17. 恩,谢谢阿北提醒,又仔细看了一下题面,发觉我模拟的只是一次抽样抽到50人以下小组的概率;而我们要找的是出现在15分钟名小组中的概率,也就是6次抽样中包含一个50人以下小组的概率。这样把程序改了一下,结果确实是在18.5%-18.7%之间,如以上各位所言 :)

    xyb Says: 三月 9th, 2006 at 1:48 下午
  18. Felix, 有意义的不是95%肯定几率。是“平均每隔多长时间会出现一次50人一下的小组”? 我怎么觉得是80分钟的样子啊。

    阿北 Says: 三月 9th, 2006 at 1:53 下午
  19. 概率论里是没法算平均多长时间的吧?一般置信率达到95%的,就可算作“一定会发生”的事件了。所以1-(1-0.186)**15是0.954,刚好超过95%。15*15m=3h45m,基本上就可以肯定不到四个小时应该就会出现一次了。

    xyb Says: 三月 9th, 2006 at 2:09 下午
  20. 当然有平均时间了。比如,一分种扔一次硬币,平均多长时间出现一次头? 这个和95%没有什么关系吧。:)

    阿北 Says: 三月 9th, 2006 at 2:28 下午
  21. 不是很明白问题,:)
    假设从N个人中随机抽取,小组人数为x,抽取次数为t,那么被抽取的概率为:
    1-((N-x)/N)^t
    每次抽取6个小组,其实可以简化为:
    1-((N-x)/N)^(6t)
    我用Excel计算的结果是50人的小组被抽取的概念是21%,大概2-3天有机会出现一次。

    Mars Says: 三月 9th, 2006 at 3:16 下午
  22. 嗯,如果每次出现的概率是0.186,那么这个期望就是1/0.186。15分钟一次大约就是80分钟了,阿北说的就是这个数学期望。

    平均起来,大约80分钟能看到一次。但如果你想保证看到,还是拿出4个小时来观察更靠得住。

    说梦痴 Says: 三月 9th, 2006 at 3:20 下午
  23. 18.6%是正解。

    xyb, 请你喝酒。

    要是”anonymous”今天不自报姓名,T-shirt就归Felix了。

    阿北 Says: 三月 9th, 2006 at 3:39 下午
  24. 哦,呵呵,知道这个平均的意思了,就是说1000次出现186次,所以可以平均一下就是1000*15/186=80分钟。
    谢谢阿北,那我就不客气了,有空去找你哦。

    xyb Says: 三月 9th, 2006 at 3:45 下午
  25. >要是”anonymous”今天不自报姓名,T-shirt就>归Felix了。

    呵呵,没问题。俺不会喝酒,对超女的热情也不够。

    将来有机会见面的话请我吃饭吧。祝你的网站越办越好。

    anonymous Says: 三月 9th, 2006 at 5:37 下午
  26. :) 超女不太感兴趣 无所谓啦
    兄台不报姓名 深藏不露诶..

    Felix Says: 三月 9th, 2006 at 8:25 下午
  27. 随即出现 解决了部分问题。但却没有利用好。人的需求。
    利用好长尾的优势. 也没有利用好 douban 的优势.
    douban 的书都是智能推荐了。那如果前提 人的需求是千奇百怪的。那小组也是可以根据个人的需求 智能的推荐.
    建议推荐的是小组里面的文章.这样更有利于小组的发展.吸引加入. 因为人看文章是不会因为人的多少来判断是否看的。而是文章的内容.

    xiaoju Says: 三月 10th, 2006 at 1:55 下午
  28. 自备T-Shirt?阿北是不是随时能拿到某超女签名…
    阿北在和某超女拍拖

    Samuel Says: 三月 27th, 2006 at 11:04 上午
  29. Felix,你是不是newsfan c++的felix?

    Samuel Says: 三月 27th, 2006 at 11:06 上午
  30. 我手工对豆瓣1到10人的小组进行数量统计,人数为n,小组数为x,由幂次定律n=a*x^(-k),取对数:lg(n)=lg(a)-k*lg(x),再经excel手工拟合得k=0.5(确切一点是0.55)。

    那么,只要按小组人数平均分配出现几率(1人小组权值为1,10000人小组权值为10000),最终得到的自然是k=0.5的“长尾分布”,阿北不会是把所有小组按人数排序,再设一个0.5的系数计算每个小组的权值吧。。你会发现计算的结果和人数成正比例。。

    老袁 Says: 十二月 12th, 2006 at 3:46 下午
  31. n x lg(n) lg(x) lg(n)=lg(a)-0.5*lg(x)
    1 216750 0 5.335959106 2.667979553
    2 51750 0.301029996 4.713910354 2.657985173
    3 29400 0.477121255 4.46834733 2.71129492
    4 18900 0.602059991 4.276461804 2.740290893
    5 13275 0.698970004 4.12303453 2.760487269
    6 10275 0.77815125 4.011781831 2.784042166
    7 8175 0.84509804 3.912487761 2.801341921
    8 6675 0.903089987 3.82445127 2.815315622
    9 4350 0.954242509 3.638489257 2.773487138
    10 3000 1 3.477121255 2.738560627

    老袁 Says: 十二月 12th, 2006 at 3:46 下午
  32. n x lg(n) lg(x) lg(n)=lg(a)-0.55*lg(x)
    1 216750 0 5.335959106 2.934777508
    2 51750 0.301029996 4.713910354 2.89368069
    3 29400 0.477121255 4.46834733 2.934712286
    4 18900 0.602059991 4.276461804 2.954113984
    5 13275 0.698970004 4.12303453 2.966638996
    6 10275 0.77815125 4.011781831 2.984631257
    7 8175 0.84509804 3.912487761 2.996966309
    8 6675 0.903089987 3.82445127 3.006538186
    9 4350 0.954242509 3.638489257 2.955411601
    10 3000 1 3.477121255 2.91241669

    老袁 Says: 十二月 12th, 2006 at 3:47 下午
  33. 不知道10人以上的那些小组分布系数是不是还是0.5…

    老袁 Says: 十二月 12th, 2006 at 3:48 下午
  34. 果然还是0.5..

    按小组的人数正比例分配出现的几率是最佳手段。这样使推荐的9个组保持了原有的分布,合乎道理;用人头来说话合乎情理。

    老袁 Says: 十二月 13th, 2006 at 1:06 上午
  35. 你有英语和语文,还有数学,在一起怎样搞呀?

    地方彻底个 Says: 五月 5th, 2007 at 11:49 下午
  36. 上面这些发言里数老袁最二了,人家阿北早说了用实际的麻烦,用数学的方便。

    IT小兵 Says: 十一月 1st, 2007 at 4:42 下午
  37. 我想不出来。

    雪山青松 Says: 二月 15th, 2008 at 3:27 下午
  38. 楼上说的应该差不多了

    123 Says: 八月 17th, 2008 at 5:29 下午
  39. 楼上说的应该差不多了

    123 Says: 八月 17th, 2008 at 5:29 下午
  40. 楼上说的应该差不多了

    123 Says: 八月 17th, 2008 at 5:29 下午
  41. 楼上说的应该差不多了

    123 Says: 八月 17th, 2008 at 5:30 下午