最近遇到这样一个问题，需要在微信群里抓壮丁，找一小程序抓阄，但必须要所有人都点开小程序才行。偶有时间紧迫，有人不怎么看手机，抓阄结果不出，四下焦急。
目前想法是能否以投骰子来定人，但骰子点数有限，所以如何能把骰子点数扩展？于是建模如下：
有一随机变量$X$均匀分布，取值域为1...n，能否拓展其为$Y$，使值域为1...m？（m>n）
换成实际情况，就是群有$45$人，骰子能投$1-6$，能否用骰子随机投出$45$人中一位呢？
午间睡前思忖片刻，想出一套方案。
- 骰子投一次可以得到1-6共6位随机数
- 骰子投两次可以得到1-36共36位随机数
- 骰子第三次按照奇数偶数划分，可以得到72位随机数。
即只需要三次骰子就能唯一指定一人，每人选中概率为$\frac{1}{72}$，选额超出45时或重复选中重新投即可。
例如分别投出了3,3,6，那么就是3x3x2=18号同学。分别投出了6,5,3，那么就是6x5x1=30号同学。分别投出了5,5,4，那么就是5x5x2=50，超出了45人的范围，重投即可。
抽空谷歌一二，原来此法称为拒绝抽样，也就是说首先生成大于$m$的一个均匀分布，让$m$范围内每一个数值出现概率相同，然后把额外的值拒绝掉即可。虽然这样取得的概率小于$\frac{1}{m}$，但是问题不大，能保证每个取值概率均等。
这里第三次之所以采用奇偶，是因为再以6来拓展的话，那么取值域太大了。在骰子小于等于6的情况下，取奇偶可以得到$\frac{1}{2}$的均匀分布，取12，34，56可以得到$\frac{1}{3}$的均匀分布，因此可以减小问题扩张的规模。
而如果放弃这样的idea，回到问题：
有一随机变量$X$均匀分布，取值域为1...n，能否拓展其为$Y$，使值域为1...m？（m>n）
解答就是：
重复取随机变量$X$共$\lfloor\frac{n}{m}\rfloor$次（可以根据实际情况取$n$的公因数，不一定要取$\lfloor\frac{n}{m}\rfloor$次），设$\lfloor\frac{n}{m}\rfloor=a$，则可以够造均匀分布$X_a$，每个值概率为$\frac{1}{m^a}$。
对$X_a$进行拒绝取样，对于所有取样大于$m$的值抛弃即可，就得到了$Y$
于是很自然地就回到了一个现实的问题：
在当前的情况下，期望是扔几次骰子就能找到一个人呢？因为并不希望每次扔出去都要重新扔，而且因为在这个情况下，每确定一个人都要扔三次骰子，还是比较累的。
设$\lfloor\frac{n}{m}\rfloor=a$，可以很容易写出来投次数的期望$E(x)$：
$$ E(x)= \frac{n}{m^a} \times 1 + \frac{m^a-n}{m^a} \times \frac{n}{m^a} \times 2 + (\frac{m^a-n}{m^a})^2 \times \frac{n}{m^a} \times 3 ..... $$
即：
$$ E(x)= \frac{n}{m^a} \times [1 + \sum_{k=1}^{\infty}k \times (1-\frac{n}{m^a})^k] $$
$m^a$表示$X_a$取值范围，在这里就是72，而人数$n$为45，代入可以求得：
$$ E(x)= \frac{45}{72} \times [1 + \sum_{k=1}^{\infty}k \times (1-\frac{45}{72})^k] = \frac{49}{40} = 1.225 $$
也就是说期望扔1.225次（注意每次都是投3次骰子）就可以找到人了，嗯，基本满意。
那很快就有新的现实的问题了，我们不能每次都选一个人，因此这次选定某人后，下次他就不需要再参加了。实现起来很简单，把他加入到拒绝采样的范围中即可。但是去掉一个人之后对我们扔骰子的期望有什么变化呢？
假设我们减掉$x$人，那么上式就变成了：
$$ E(x)= \frac{45-x}{72} \times [1 + \sum_{k=1}^{\infty}k \times (1-\frac{45-x}{72})^k] $$
x取值在$[0, 45)$，很显然，当x逼近45的时候，值趋近于无穷大。画出图像是这个样子：
可以看出来，在x等于20的时候，求得的值为2.22。因此投骰子的期望递增速度尚可。就这个方法还是可以用的。
另外除了拒绝采样，还有其它解决方案，待我最近有空再研究好了~随缘
写在后面：
本来是想用wolfram alpha画图的，不知道为啥画不出来。。。。最后麻烦明林用matlab帮我画的，看来还是得装个matlab才行。感谢明林！