算法 | 如何根据不相等概率[0,1]设计出相等概率的[0,1]？

柔情只为你懂 2023-10-03 22:30 11阅读 0赞

### 前言 ###

本文主要介绍如何根据不相等概率`[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`这个方法，通过这个方法我们可以得出几个信息：

1.  方法不可更改，只能被调用。
2.  方法只返回`0` 和 `1`，我们并不知道`0`和`1`的概率是多少。
3.  要想办法从`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)`。

由此可以得出，我们只要调用两次`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`是不是等概率的呢？

验证思路如下：

1.  初始化一个数组`arr`，用来存放 `0`和`1` 被调用的次数。
2.  设置一个循环1千万次，来调用`func2()`这个方法。
3.  对比数组`arr`中`0`和`1`元素的个数。
4.  如果`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`。

当然，解决方法不可能只有这一种，如果你有更好的方法，欢迎在评论区留言交流~。