问题描述
假设现在一个楼栋共有M层，有一个电梯一次性最多能装N个人。问题是，假如说现在该电梯在一楼进入了N个乘客，不考虑从中间楼层上的乘客问题，那么该电梯大概需要停留几次才能将所有的乘客送到目的地。也就是说，这N个乘客选出不同楼层的数量X的期望是多少？
按照定义求解
首先，我们可以分析出随机变量X可能的取值为$[1,min(M,N)]$，对于每一个可能的取值$x$，我们分析一下有多少种可能性。也就是说要分析N个人在M个楼层里面选，最终选出$x$个不同的楼层有几种情况。
错误的解法
N个人在M个楼层里面选，最终选出$x$个不同的楼层，则我们先选出$x$个不同的楼层，然后在N个人里面选出$x$人，让每个人都选不同的楼层。接下来，对于剩下$N-x$个人，随便选择楼层即可。因此，按照这种思路，我们可以得到可能性的数量为
$$
N_x = C_M^x C_N^x A_x^x M^{N-x}
$$
然而，这样求出来的结果是不对的，原因是对于$C_N^x A_x^x M^{N-x}$来说它是存在重复的。也就是说，你一开始选出来的$x$个人和后面剩余的$N-x$个人的选择不能分开考虑。
正确的解法
我们先来求$N_1$，也就是说N个人在M个楼层里面选，最终选出1个不同的楼层。这个很简单，既然大家都选择同样的楼层，由于楼层总共也就M层，所以$N_1 = C_M^1 \cdot Y(N,1,1)$。其中$Y(N,1,1)$代表N个人在只有1个选择的情况下，选出了1个不同的值的情况数量。
接下来，我们再来分析$N_2$，也就是说N个人在M个楼层里面选，最终选出2个不同的楼层。首先，同样的，我们任意选择出来两个楼层。所以我们可以得到$N_2 = C_M^2 \cdot Y(N,2,2)$。这个问题的重点就在于$Y(N,2,2)$怎么求。
首先我们知道N个人在2中选择里面选，最多可能的选择可能性为$2^N$，所以$Y(N,2,2) < 2^N$。这是因为这N个在2个选择里面选，可能出现全选一样的情况，我们需要在$2^N$里面把这一部分情况剪掉，才能得到$Y(N,2,2)$。那么N个在2个选择里面选，选出了一个不同的值有几种可能性呢，也就是说我们要求$Y(N,2,1)$的值。
求解$Y(N,2,1)$和上面基本一样，也就是说，我们先选择一个值，则接下来的问题就变成了$Y(N,1,1)$，换句话说$Y(N,2,1) = C_2^1 Y(N,1,1)$，因此我们可以得到
$$
N_2 = C_M^2 \cdot Y(N,2,2) = C_M^2 \cdot (2^N - Y(N,2,1)) \
= C_M^2 \cdot ( 2^N - C_2^1 Y(N,1,1)) = C_M^2 \cdot ( 2^N - 2)
$$
同理，我们可以求得
$$
N_3 = C_M^3 \cdot Y(N,3,3) = C_M^3 \cdot (3^N - Y(N,3,2) - Y(N,3,1)) \
= C_M^3 \cdot (3^N - C_3^2 Y(N,2,2) - C_3^1 Y(N,1,1))
$$
由于$Y(N,2,2),Y(N,1,1)$都是已知的，所以$N_3$就可以求出来了。到了这里，我们不难发现对于$N_x$，我们有
$$
N_x = C_M^x Y(N,x,x) =C_M^x (x^N - \sum_{i=1}^{x-1} {C_x^{i} \cdot Y(N,i,i)})
$$
有了$N_x$之后，随机变量X的值为$x$的概率$p_x$即为$\frac{N_x}{M^N}$，所以随机变量$X$的期望为
$$
E(X) = \sum_{x=1}^{min(N,M)} \frac{N_x}{M^N} \cdot x
$$
简单的求解方法
可以看到上面的求解方式非常复杂，事实上我们只要利用期望的线性性质对随机变量进行拆分即可很快的求解该问题。定义随机变量$Z_i$代表在电梯在第$i$个楼层停留的次数，则随机变量$Z_i$只有0和1两个取值，且$Z_i$取0的概率就是N个人没有一个人选到该楼层的概率，即$q = (\frac{M-1}{M})^N $。因此，$Z_i$的期望就是$1 -(\frac{M-1}{M})^N$。
由于随机变量$X$和$Z_i$有如下关系，
$$
X = Z_1 + Z_2 + …. +Z_M
$$
因此，$E(X) = M*E(X_1) = M - M(\frac{M-1}{M})^N$。这两种方式求出来的结果是一样的，我在python里面进行了验证。从上式也可以看出，当楼层数量趋于无穷大的时候，E(X) 趋向于N，也就是说大家选的楼层基本上都是不同的，这也和我们的直觉相符。
