实验报告
1.球与箱子
有b个箱子，每一次投球，球等概率落在每个箱子中，即球落在任何一个箱子中的概率为1/b 。
如果我们把投球过程视为一串伯努利试验。投球成功行为指球投入指定箱子，每次有1/b的成功概率，这个模型也适用于哈希，我们能用投球试验回答一系列有趣的问题。
有多少个球落入指定的箱子中?
由于每一次投球都是彼此独立的，所以我们可以知道每一次投球即每一次实验都是独立的，并且每一次都是在同样条件下重复进行试验，所以这显然是一个伯努利试验。所以说如果要进行n次投球，有n/b个球落入指定的箱子中。在平均意义下，你必须要投出多少球，才能在给定的箱子中投中一个球?
因为球落入该给定箱子的概率为1/b，所以要实现平均意义的投中一个球，则需要投1/（1/b）=b个球。
你需要至少投出多少球，使得每个箱子中至少有一个球?
设第i阶段为第i-1次命中到第i次命中之间的投球，第i阶段的每一次投球，i-1个箱子有球, b-i+1个箱子是空的，命中空箱子的概率为(b-i+1)/b 。所以说从第i-1次命中到第i次命中至少需要进行b/(b-i+1)次投球。因为总共b个桶，所以要实现b个桶至少每个桶内含有一个球，需要进行从第一次命中到第b次命中的累加。所以由下式可知大概需要进行blnb次投球才能使得每个箱子至少有一个球。
$$
E[n]=E\left[\sum_{i=1}^b n_i\right]=\sum_{i=1}^b E\left[n_i\right]=\sum_{i=1}^b \frac{b}{b-i+1}=b \sum_{i=1}^b \frac{1}{i}=b(\ln b+O(1))
$$
2.硬币问题
假设你抛硬币n次，最长连续正面的期望长度有多长?
首先要明确知道每次掷硬币时是一次正面的概率为1/2，且每次掷硬币是相互独立的。
设
$$
A_{i_{k}}
$$
为：长度至少为k的正面特征序列开始于第i次投掷，且第k次投掷是正面的概率是：
$$
\operatorname{Pr}\left{A_{ik}\right}=\frac{1}{2^{k}}
$$
定义指示器随机变量
$$
X_{i_{k}}
$$
表示从第i次开始的任意一次的取值，其范围1<i<i-k+1：
$$
X_{i k}=\mathrm{I}{\text { 从 } i \text { 开始，第 } k \text { 个为正面 }}= \begin{cases}1 & \text { 如果从第 } i \text { 开始第 } k \text { 个为正面 } \ 0 & \text { 其他 }\end{cases}
$$
$$
X=\sum_{i=1}^{n-k+1} X_{i k}
$$
两边取期望并化简得到：
$$
\mathrm{E}[X]=\mathrm{E}\left[\sum_{i=1}^{n-k+1} X_{i k}\right]=\sum_{i=1}^{n-k+1} \mathrm{E}\left[X_{i k}\right]=\sum_{i=1}^{n-k+1} \operatorname{Pr}\left{A_{i k}\right}=\sum_{i=1}^{n-k+1} 1 / 2^k=\frac{n-k+1}{2^k}
$$
我们分析一下期望的意义，可以总结出期望算出来的为长度为k的特征序列的数目期望。如果这个数大，意味着长度为k的序列出现的次数多，即出现一个的概率很高；如果这个期望小，则意味着一个长度为k的序列次数小，即出现一个的概率很小。如果对于结果是一个常数c，可以得到k的取值为clgn。所以综上所述，我们可以得出结论：最长特征序列的长度期望是O(lgn)。
