如何抛双面硬币模拟三分之一的概率？

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

先把问题具体化：设用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，打下了引入更野蛮狂暴方法的基础：将实验E分为E1和E2两种，使用两者的贝叶斯后验概率之积来平衡。令E1的n1=r-1，M1=E1即任何基本结果都能被承认，也即{s1=m}中可以取遍m=0,1,...,r-1，而把S1收窄到取m=0,...,q-1。由M1=E1={s1=0,1,...,r-1}，和S1={s1=0,...,q-1}，得Card(s1,M1)=Card(s1,E1)=r，Card(s1,S1)=q，而要对s1使用古典概型，还需要E2从中插入，使其分布平均化。无论E1的结果{s1=m}中取什么值，都令E2的n2=Card{s1=m}-1=C(m,n1)-1=(m!)/[n1!(m-n1)!]-1，再指定S2={s2=0}和D2={s2=1}，则易得其事件概率为p2=P(S2|M2)=1/C(m,n1)=[n!(m-n1)!]/(m!)。

现在规定具体的插入流程为，做完一个E1，除非m=0的情况下不用做E2直接划分M1，否则要不停地做其对应的E2(m)，直到遇到第一次符合的M2(m)为止，这样一系列可统计估计o(m)≈o2(m)=O[2^C(m,n1)]；如果是其中的S2(m)，则再检查M1中是否为S1，若都是才能以S=S1×S2，平行交叉出一次成功的事件，若到这里了不是才能以D=D1×S2，记作一次生成器整体的真正失败；要若为其中的D2(m)，则直接跳到下一次E1，不必再检查M1的划分；做完了这些才能回到下一个E1及其相应的下一批E2。又由p1(m)=C(m,n1)/2^n1，p2(m)=1/C(m,n1)，得p(m)=p1(m)*p2(m)=1/2^n1=2^(-n1),∀m=0,1,...,r-1，即抵消到互相均等，p{s1=m}平均化分布，这样才能使得从m中筛选满足p=q/r。粗糙的示意图如下：