算法 | 如何根据不相等概率[0,1]设计出相等概率的[0,1]？
开启掘金成长之旅！这是我参与「掘金日新计划 · 12 月更文挑战」的第29天，点击查看活动详情
前言
本文主要介绍如何根据不相等概率[0,1]设计出相等概率的[0,1]。
给定一个方法func1，这个方法返回0的概率为p，返回1的概率为1-p。
现在要根据func1这个方法，设计出一个新的方法func2，该方法返回0和1的概率都为50%。
func1代码如下：
public static int func1() {
return Math.random() < 0.7 ? 0 : 1;
}
思路解析
先来看一下func1这个方法，通过这个方法我们可以得出几个信息：
- 方法不可更改，只能被调用。
- 方法只返回
0和1，我们并不知道0和1的概率是多少。 - 要想办法从
func1中，得出2个概率相等的数字。
func1方法中的内容我们不能更改，而且方法里面的 0.7也有可能是其他的，只知道是固定的，但具体多少也无法得知，只能得到0和1。
要设计的func2方法也是返回0和1，但是0和1的概率是相同的，都为50%。
那怎么利用func1方法来实现呢？
组合概率
其实实现方法也很简单，只需要调用两次func1方法方法就能得到两个相同的概率数字，我们一起来分析一下。
func1方法可以得到0和1，调用两次func1方法可以得到哪些组合呢？
调用两次func1方法得到的数据组合为：00、01、10、11。
再来看下00、01、10、11这四组数的概率分别为：pp、p*(1-p)、(1-p)*p、(1-p)*(1-p)。
可以看到，虽然我们不知道概率p到底是多少，但至少01、10这两组数的概率是相同的都是p*(1-p)。
| 组合 | 概率 |
|---|---|
| 00 | pp |
| 01 | p*(1-p) |
| 10 | (1-p)*p |
| 11 | (1-p)*(1-p) |
由此可以得出，我们只要调用两次func1方法，如果生成的是00或11，就让他重新生成，如果生成的是01或10直接返回即可。
代码实现
经过上面的分析，对func2方法的实现如下：
public static int func2() {
int res, tmp;
do {
res = func1();
tmp = func1();
} while (res == tmp);
return res;
}
概率验证
怎么验证一下func2方法返回的0和1是不是等概率的呢？
验证思路如下：
- 初始化一个数组
arr，用来存放0和1被调用的次数。 - 设置一个循环1千万次，来调用
func2()这个方法。 - 对比数组
arr中0和1元素的个数。 - 如果
0和1元素的个数大致相同的话，说明func2()方法返回的0和1是等概率的。
验证代码如下：
public static void main(String[] args) {
int times = 10000000;
int[] arr = new int[2];
for (int i = 0; i < times; i++) {
int res = func2();
arr[res]++;
}
System.out.println("元素: 0, 出现的次数为: " + arr[0]);
System.out.println("元素: 1, 出现的次数为: " + arr[1]);
}
多运行几次验证方法，可以发现0和1的次数是差不多的，也就是说func2()方法返回的0和1是等概率的。
运行结果如下：
元素: 0, 出现的次数为: 5002123
元素: 1, 出现的次数为: 4997877
总结
本文主要介绍如何根据不相等概率[0,1]设计出相等概率的[0,1]。
其中主要思想就是根据不相等概率的[0,1]通过组合来生成包含相同概率的两组数的结果00、01、10、11，然后从这4组数中只返回相同概率的01和10，如果生成的是00和11就让他重新再生成直到生成01和10。
当然，解决方法不可能只有这一种，如果你有更好的方法，欢迎在评论区留言交流~。