江苏龙网

  1. 首页 > 生活 > >

投b个球到b个盒子，盒子中最大球数的期望

上个星期看到这个问题，挺想回答的。谷歌搜索一下 Balls into bins , 挺多论文的，静下心来慢慢看就行了。
题主提供的两篇论文都不错。
本回答主要以模拟仿真的角度去验证，没有太多分析。不搬运证明过程。
前提: 盒子与球的数量相等均为b，每次投球互相独立，且对于特定一个球落入任一盒子的概率相等为1/b.仿真结果1、b从1递增至1000, 重复次数t=1000：
投b个球到b个盒子，盒子中最大球数的期望

仿真结果2、b从1递增至10000, 重复次数t=100：
投b个球到b个盒子，盒子中最大球数的期望

大概思路：定义：
一次仿真：对于给定的b，完成将b个球投入b个盒子的动作，并得出所有盒子中球数最多的盒子的球数x.
简单仿真：对于给定的b和t，重复t次一次仿真，得到投b个球到b个盒子，盒子中最大球数的期望
，得出对于给定的b，盒子中最大球数的估计值为投b个球到b个盒子，盒子中最大球数的期望
.
完整仿真：给定b的起始值 投b个球到b个盒子，盒子中最大球数的期望
、结束值 投b个球到b个盒子，盒子中最大球数的期望
、以及t，进行 投b个球到b个盒子，盒子中最大球数的期望
次简单仿真。
代码：
import numpy as npimport matplotlib.pyplot as pltdef simulation_simple(balls, bins, times): """ Throw m balls into n bins by placing each ball into a bin chosen independently and uniformly at random t times. Output the mean of "maximum number of balls in any bin" over t times. :param balls: the number of balls, type int :param bins: the number of bins, type int :param times: the number of replication, type int :return: the mean of "maximum number of balls in any bin" over t times, tpye float """ total = np.zeros(times) for t in range(times): l = np.random.randint(0, bins, balls) total = np.bincount(l).max() return total.mean()def simulation_all(begin, end, times): sequence = np.arange(begin, end+1, 1) sim_y = np.zeros(end) for i in range(end): sim_y = simulation_simple(i+1, i+1, times) return sequence, sim_yif __name__ == \u0026#39;__main__\u0026#39;: # b从1增加到1000，对于给定的b，每次模拟1000次 x, sim_y = simulation_all(1, 1000, 1000) plt.plot(x, sim_y) plt.xlabel(\u0026#39;b\u0026#39;) plt.ylabel(\u0026#39;maximum number of balls in any bin\u0026#39;) plt.title(\u0026#39;Simulation\u0026#39;) plt.show()以上代码运行时间复杂度： 【投b个球到b个盒子，盒子中最大球数的期望】 投b个球到b个盒子，盒子中最大球数的期望
， 其中n为球数b的结束值，m为重复次数t.

■网友
这个论文可以的https://www.cs.cmu.edu/~avrim/Randalgs11/lectures/lect0202.pdf


    推荐阅读


    上一篇：\＂Propositions as Types\＂ 是啥意思?

    下一篇：邓超|邓超：父亲尿毒症去世，大姐患癌，自己尿血，发文“息影退圈”？