【资料图】

上面的标题只是用来吸引读者的极简特殊场景，本文真正要讨论的问题其实更普遍：如何只用单个二分之一概率发生器(对半分概型)，模拟出任意有理数概率？

先把问题具体化：设用n次硬币模拟概率p；其中n∈Z+，即为正整数，n>0；p=q/r，而其中q,r∈Z+∧q<r，即q和r都是正整数，而q小于r，0<q<r，r≥2，还有q和r互质，q⊥r；这样就保证了p∈Q∩(0,1)，即p是非零暨非一的有理概率，0<p<1。应该指出，这个概率问题可以有两种分支情况，一种是排列，而另一种是组合。在排列分支中，硬币的每次投掷都有自己的独特位置，互相之间并不等价，结果也不能互相替换。投掷后假设能立即读取出当前次数的特定结果，对结果的统计加和反而需要耗费时间和精力。而在组合分支中，每次投掷都是等价的。假设能得到的结果只有正反两面的总数，而且有很方便的统计机器可以自动立即得到，而无法清点得到特定次数的信息。换句话说，单次的信息在统计后，因为缺少记录已经损失，无法再得到了。再比较自主地理清以下三组概念：一、n次的随机试验，其所有基本结果的集合称为样本空间，定义为全集E。二、可以按照选择的一个指定标准，对特定的基本结果，在承认和排斥中二选一。对基本结果来说，前者属于统计样本，定义为母集M；而后者属于无效样本，定义为补集U。这样就将全集划分成了两块，即E=M⊕U，也可以说是U=E\M。三、与二同理，可以再选择一个指定标准，将统计样本划分成事件发生，定义为子集S；和事件不发生，定义为偏集D；即对应M=S⊕D，和D=M\S。默认以上集合都非空。综上所述，主要就是构造E=S⊕D⊕U，还有S⊂M⊂E这种结构，最详细的示意请看下图：

（1）若为排列分支，则可以给n次投掷按时间从前到后的顺序，从1,2,...到...,n各自编号。在默认已经规定好正反面的前提下，用正面结果对应1，用反面结果对应0，用硬币编号对应从大到小的位次，生成一个n位二进制数B(n)。由此可得，全集为所有可能的n位二进制数，即E={B(n)|0≤B≤2^n}，∴Card(E)=2^n。

那么对于问题给定的p=q/r，就很方便生成实验方法了。选取任意一个满足2^n≥r，即n≥log(2,n)的正整数n（若要最节省时间，则应选取该系列n中最小值）。然后规定选择标准：S={B(n)|0≤B≤q-1}，D={B(n)|q≤B≤r-1}，D={B(n)|r≤B≤2^n}，∴Card(S)=q，M=S⊕D={B(n)|0≤B≤r-1}，Card(M)=r。这时已经可以统计出子集在母集中的占比是P(S|M)=Card(S)/Card(M)=q/r=p，但为了用古典概型将其转化为事件概率，还需要一个递归发生机制，如下图：

很简单的做法，在得到补集中的结果后，直接判定为无效样本，重复实验直到再次得到统计样本为止。这样排除了之后，就能宣布在统计中事件的概率为p。

还可以计算进行一次有效随机所需的平均投掷次数是：单次实验的硬币投掷次数除以该次实验有效的概率，即为o=n/[Card(M)/Card(E)]=(n*2^n)/r。若n取得最为节省，则有 2^(n-1)＜r ≤ 2^n，故 n ≤ o＜2n，其中o当且仅当r为2^n时取n，即 o=n ⇔ r=2^n 。在这种线性双倍内的节省中，时间复杂度的代价基本可以忽略不计。

（2）若为组合分支，则实验加和服从二项分布，定义得更清晰即为s~B(n,1/2)。则每个s的取值m对应的基本情况数都可以表示为Card{s=m}=C(m,n)=(m!)/[n!(m-n)!]（其中m=1,2,...,n），故其概率可表示为P{s=m}=C(m,n)/2^n=(m!)/[n!(m-n)!(2^n)]。而对E={s=m,∀m=1,2,...,n}，有P(E)=Σ(m)P{s=m}=1。

对于足够大的甚至趋于无限的n→∞来说，能否在E中划分出合适的M和S，使得P(S|M)=p，可能是一个非常难的大问题（也许在数学界中已经有人发现、尝试甚至解决了，只是孤陋寡闻的我搜不到）。

但至少已知一种非常粗暴的方法去模拟任意q=1的p=1/r型概率：令n=r-1，取S={s=0}，D={s=1}，则由C(0,n)=1，C(1,n)=r-1，M={s∈{0,1}}得，Card(M)=C(0,n)+C(1,n)=r，故P(S|M)=1/r=p。这种简单方法的代价就是成本也很大，尤其是在n随r变大的时候。由o=(n*2^n)/r=(2^n)*n/(n+1)=2^n (n→∞)得，这时讨论时间复杂度呈指数形式增长是有意义的，即o=O(2^n)。

这为接下来处理∀p=q/r，打下了引入更野蛮狂暴方法的基础：令n1=r-1，n2=C([n1/2],n1) (其中易得C([n1/2],n1)=max{C(m,n1)} )，再用n1枚和n2枚这两组硬币分别做两系列平行的实验。设E1=M1，子集族{T1(m)}⊂M1^r是其一个r元划分 (其中m=0,1,...,n1) ，令T1(m)={s=m|E1}；又设子集族{T2(m)}⊂M2^r是其一个r元划分，令T2(m)={s∈{0,1}|前[C(m,n1)-1]枚硬币}；再设子集族{T3(m)}⊂S2^r是其一个r元划分，令T3(m)={s=0|前[C(m,n1)-1]枚硬币}。这样对于任意一个E1中取值的s=m，都能将无穷多场E2中符合T2(m)⊂M2的场数挑出来，再从中抽取符合T3(m)⊂S2的场次，这就相当于一个1/C(m,n1)概率发生器，能把Card[T1(m)]=C(m,n1)除回1，这样就能定义出子集族{T1(m)}⊂S1^r是其一个q元划分 (其中m=0,...,q-1)，即S1={s=0,...,q-1|E1}⊂E1=M1={s=0,...,n1|E1}。通过这种复杂的归一化操作，就能由古典概型得到p=q/r，不严谨的示意图如下：