随机函数变换示例

浅浅的花香味﹌ 2024-04-08 11:34 88阅读 0赞

### 说明 ###

本示例中基于 Java ，其他语言也有类似的 API

### 解决的问题 ###

问题1

Java 中 `Math.random()` 函数是等概率返回区间 `[0,1)` 中的任意一个小数。

即 `x < 1` 情况下， `[0,x)` 中的数出现的的概率是 `x` ，

如果我们要将

`x < 1` 情况下， `[0,x)` 中的数出现的的概率调整成 `x^2` ，应该如何做？

问题1思路

由于 `[0,x)` 的概率是 `x` ，那么调用两次 `Math.random()` ，如果较大的那个值也要在 `[0,x)` 区间内，那么两次调用都必须在 `[0,x)` 区间内（因为任意一次在 `[x,1)` 都会导致返回值不在 `[0,x)` 上），即概率是 `x^2` ，代码如下

我们可以通过如下测试代码来验证问题1的解法：

package snippet;
    
    public class Code_0004_RandToPow2 {
        // 将`[0,x)`中的数出现的的概率调整成`x^2`
        public static double randToPow2() {
            return Math.max(Math.random(), Math.random());
        }
    
        // 测试用例
        public static void main(String[] args) {
            int count = 0;
            int testTimes = 10000000;
            double x = 0.17;
            for (int i = 0; i < testTimes; i++) {
                if (randToPow2() < x) {
                    count++;
                }
            }
            System.out.println((double) count / (double) testTimes);
            System.out.println(Math.pow(x, 2));
        }
    }

打印的结果如下

0.0288603
    0.028900000000000006

接近目标要求。

问题2

假设我们有一个随机函数 `f()` ，这个函数可以等概率返回 `[1,5]` 中的一个数，如何 **只利用 `f()` 函数** 而不引入其他随机函数，得到一个等概率返回 `[1,7]` 中任意一个数的函数 `g()` 。

思路

由于目标是求 `[1,7]` 等概率返回一个，如果我们能加工得到一个 `x()` 函数，这个函数是等概率返回 `[0,6]` 范围内的任意一个数，那么目标函数 `g()` 只需要调用这个 `x()` 函数再加上1，即是 `g()` 函数要求

public static int g() {
        return x() + 1;
    }

要得到 `[0,6]` 等概率返回一个数，我们 **需要先得到一个0和1等概率返回的随机函数 `m()`**，我们可以通过 `f()` 函数来得到，即

// 通过[0,5]等概率返回的随机函数f()
    // 加工出等概率得到0和1
    // 1,2,3,4,5 五个数
    // 得到1，2的时候，返回0
    // 得到4，5的时候，返回1
    // 得到3的时候，弃而不用，再次尝试
        public static int m() {
            int ans = 0;
            do {
                ans = f();
            } while (ans == 3);
            return ans < 3 ? 0 : 1;
        }

有了等概率返回 0 和 1 的随机函数 `m()` ， 我们可以很方便的生成 `[0,6]` 随机等概率返回一个数的方法，因为 `[0,6]` 需要三个二进制数表示，那么我们可以调用三次 `m()` 函数，可以等概率得到 `[0,7]` 范围内任意一个数，我们可以在得到 7 的时候，重试上述过程，只有结果在 `[0,6]`才返回，这样就加工出了 `x()` 函数。

// 等概率返回0~6
        public static int x() {
            int ans = 0;
            do {
                ans = (m() << 2) + (m() << 1) + m();
            } while (ans == 7);
            return ans;
        }

最后，目标函数 `f()` 通过如下方式

// 等概率返回1~7
        public static int g() {
            return x() + 1;
        }

即可得到。完整代码如下

package snippet;
    
    public class Code_0005_Rand5ToRand7 {
    
        // 此函数只能用，不能修改
        // 等概率返回1~5
        public static int f() {
            return (int) (Math.random() * 5) + 1;
        }
    
        // 通过[0,5]等概率返回的随机函数f()
    // 加工出等概率得到0和1
    // 1,2,3,4,5 五个数
    // 得到1，2的时候，返回0
    // 得到4，5的时候，返回1
    // 得到3的时候，弃而不用，再次尝试
        public static int m() {
            int ans = 0;
            do {
                ans = f();
            } while (ans == 3);
            return ans < 3 ? 0 : 1;
        }
    
        // 等概率返回0~6
        public static int x() {
            int ans = 0;
            do {
                ans = (m() << 2) + (m() << 1) + m();
            } while (ans == 7);
            return ans;
        }
    
        // 等概率返回1~7
        public static int g() {
            return x() + 1;
        }
    
        
    }

问题3

见： [LeetCode 470. Implement Rand10() Using Rand7()][LeetCode 470. Implement Rand10_ Using Rand7]

和问题2思路一致，核心都是 **要先实现一个等概率返回 0 和 1 的随机函数 `m()` 。** ，然后看目标函数区间需要几个二进制位，来决定调用几次 `m()` 函数，不赘述，完整代码见

/**
     * The rand7() API is already defined in the parent class SolBase.
     * public int rand7();
     * @return a random integer in the range 1 to 7
     */
    class Solution extends SolBase {
        public int rand10() {
            return rand(10);
        }
    
        public int rand(int N) {
            int bit = 1;
            int base = 2;
            while (base <= N) {
                base = 2 << bit;
                bit++;
            }
            int v = build(bit);
            while (v < 1 || v > N) {
                v = build(bit);
            }
            return v;
        }
    
        private int build(int bit) {
            int v = 0;
            for (int i = 0; i < bit; i++) {
                v += (m() << i);
            }
            return v;
        }
    
        // 核心：生成 0 和 1 等概率返回的随机函数
        public int m() {
            int i = rand7();
            while (i == 7) {
                i = rand7();
            }
            return (i == 1 || i == 2 || i == 3) ? 0 : 1;
        }
    }

问题4

有一个函数 `f()` ，不等概率（但是是固定概率）返回0和1，如何只通过 `f()` 函数，得到等概率返回 0 和 1 的随机函数 `g()` ，

思路，

调用两次 `f()` 函数，可以得到如下情况

当两次都是0，或者两次都是1的时候，舍弃，虽然 0 和 1 的概率不一样，但是

概率一定一样

所以得到 `0 1` 就返回 0 ，得到 `1 0` 就返回1，即 `g()` 函数

完整代码如下

package snippet;
    
    // 不等概率随机函数变成等概率随机函数
    public class Code_0005_EqualProbabilityRandom {
    
        // 不等概率函数，
        // 内部内容不可见
        public static int f() {
            return Math.random() < 0.8 ? 0 : 1;
        }
    
        // 等概率返回0和1
        public static int g() {
            int first;
            do {
                first = f(); // 0 1
            } while (first == f());
            return first;
        }
    
    }

[LeetCode 470. Implement Rand10_ Using Rand7]: https://leetcode.cn/problems/implement-rand10-using-rand7/