投骰子的一个问题

最近遇到这样一个问题,需要在微信群里抓壮丁,找一小程序抓阄,但必须要所有人都点开小程序才行。偶有时间紧迫,有人不怎么看手机,抓阄结果不出,四下焦急。

目前想法是能否以投骰子来定人,但骰子点数有限,所以如何能把骰子点数扩展?于是建模如下:

有一随机变量$X$均匀分布,取值域为1...n,能否拓展其为$Y$,使值域为1...m?(m>n)

换成实际情况,就是群有$45$人,骰子能投$1-6$,能否用骰子随机投出$45$人中一位呢?

午间睡前思忖片刻,想出一套方案。

  1. 骰子投一次可以得到1-6共6位随机数
  2. 骰子投两次可以得到1-36共36位随机数
  3. 骰子第三次按照奇数偶数划分,可以得到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才行。感谢明林!

updatedupdated2021-08-292021-08-29