随机函数变换示例

随机函数变换相关技巧

作者：Grey

原文地址:

说明#

本示例中的语言使用的是 Java ，其他语言也有类似的 API。

问题一#

Java 中 Math.random() 函数是等概率返回区间 [0,1) 中的任意一个小数，即 x < 1 情况下，[0,x) 中的数出现的的概率是 x，如果我们要将 x < 1 情况下，[0,x) 中的数出现的的概率调整成 $x^{2}$ ，应该如何做？

主要思路

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

代码如下

// [0,1)中任何一个值x出现的概率是x的平方
public static double randToPow2() {
    return Math.max(Math.random(), Math.random());
}

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

public class Code_RandToPow2 {
  public static double randToPow2() {
    return Math.max(Math.random(), Math.random());
  }
  public static void main(String[] args) {
    int count = 0;
    int testTimes = 30000000;
    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.028884233333333332
0.028900000000000006

接近目标要求。

问题二#

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

主要思路

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

// 等概率返回 [1,7] 中任意一个数
public static int g() {
    // x() 函数是等概率返回 [0,6] 中的任意一个数
    return x() + 1;
}

接下来问题就变成了 x() 这个函数的实现，要 [0,6] 等概率返回一个数，思路如下

先得到一个 0 和 1 等概率返回的随机函数 m()，

可以通过题目中给的 f() 函数来加工得到 m()，

f() 是 [1,5] 等概率返回的一个数，也就是说，调用 f() 会等概率返回 1,2,3,4,5 中的一个数，

当调用 f() ，得到 1 或者 2 的时候，返回 0；

当调用 f() ，得到 4 或者 5 的时候，返回 1;

当调用 f() , 得到 3 的时候，弃而不用，再次尝试调用 f()。

代码如下

    // 利用[1,5]随机函数f() 生产等概率返回 0 和 1 的函数 m()
    public static int m() {
        int ans = 0;
        do {
            ans = f();
        } while (ans == 3);
        return ans < 3 ? 0 : 1;
    }

这样就得到了 0 和 1 等概率返回的随机函数m()，

由于 6 的二进制表示是 110, 所以区间 [0,6] 的所有整数只需要 3 个二进制位就可以表示，

调用三次m()函数，可以等概率得到[0,7]范围内任意一个数（因为区间[0,7]用二进制表示就是 000~111)，即 [0,1,2,3,4,5,6,7] 等概率返回一个，

在得到 7 的时候，重试上述过程，只有结果在 [0,6] 才返回，这样就加工出了 x() 函数，即等概率返回 [0,6]。

    // 等概率返回0~6
    public static int x() {
        int ans = 0;
        do {
            // 三个二进制位 M N Y
            ans = (m() << 2) // 得到 M
            + (m() << 1) // 得到 N
            + m(); // 得到 Y
        } while (ans == 7);
        return ans;
    }

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

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

完整代码和测试方法如下


public class Code_Rand5ToRand7 {

    // 此函数只能用，不能修改
    // 等概率返回1~5
    public static int f() {
        return (int) (Math.random() * 5) + 1;
    }

    public static int m() {
        int ans = 0;
        do {
            ans = f();
        } while (ans == 3);
        return ans < 3 ? 0 : 1;
    }

    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;
    }

    public static void main(String[] args) {
        final int testTimes = 100000000;
        int[] count = new int[8];
        for (int i = 0; i < testTimes; i++) {
            count[g()]++;
        }
        for (int i = 0; i < count.length; i++) {
            System.out.println(i + " 出现的次数是：" + count[i]);
        }
    }
}

测试 100000000 次，每次记录随机生成的数字，得到每个数字出现的次数

输出（参考）

0 出现的次数是：0
1 出现的次数是：14286835
2 出现的次数是：14287329
3 出现的次数是：14287207
4 出现的次数是：14286037
5 出现的次数是：14285675
6 出现的次数是：14282222
7 出现的次数是：14284695

可以看到 1 到 7 这些数字出现的次数都差不多，接近等概率，满足题目要求。

和问题二一样，本题也有同样思路的解法

  public static int g2() {
    return (f() + f() + f() + f() + f() + f() + f()) % 7 + 1;
  }

调用 7 次 f() 之和，得到的结果 % 7以后，一定是等概率返回 0~6 中任意一个整数的，再加1，就变成等概率返回 1~7 任意一个。

问题三#

见：LeetCode 470. Implement Rand10() Using Rand7()

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

class Solution extends SolBase {
    public int rand10() {
        return rand(10);
    }
    // 等概率返回任意一个`[1,N]`区间的整数
    public int rand(int N) {
        // bit 表示 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;
    }
}

注：这里实现了一个更为通用的rand(int N)函数，这个函数表示等概率返回任意一个[1,N]区间的整数。

此外，本题还有另外一种解法，代码如下

  public int rand10() {
    return (rand7() + rand7() + rand7() + rand7() + rand7() + rand7() + rand7() + rand7() + rand7()
        + rand7()) % 10 + 1;
  }

原理也很简单，由 10 个 rand7() 之和得到的值 % 10 以后，一定是等概率返回[0,9]中任何一个数，再加 1，就是等概率返回[1,10]。

问题四#

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

主要思路

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

情况1：0 0
情况2：1 1
情况3：0 1
情况4：1 0

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

0 1
1 0

即情况 3 和情况 4，概率一定一样

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

完整代码和测试代码如下

public class Code_0003_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;
    }


    public static void main(String[] args) {
        final int testTimes = 10000000;
        // count[0] 统计0出现的次数
        // count[1] 统计1出现的次数
        int[] count = new int[2];
        for (int i = 0; i < testTimes; i++) {
            count[g()]++;
        }
        System.out.println("0 出现的次数:" + count[0]);
        System.out.println("1 出现的次数:" + count[1]);
    }
}

调用 10000000 次，记录 1 和 0 出现的次数，

输出结果为（参考）

0 出现的次数:4999698
1 出现的次数:5000302

可以看到 1 和 0 实际出现的次数差不多，近似等概率，满足题目要求。

问题五#

如何用一个生成区间 a~b 的随机函数加工并生成 c~d 的随机函数。

核心思路和之前问题的思路一样，都是构造等概率生成 0 和 1 的rand01()函数，然后通过 rand01()函数加工出随机生成 c~d 的函数。

假设生成区间 a~b 的随机函数是f(a,b)，

如果 a~b 的区间元素个数是偶数，那么将区间分两半，如果得到的是前面一半的数，则返回 0 ，如果得到后面一半的数，则返回 1；

如果 a~b 的区间元素个数是奇数，那么把将区间分两半，如果得到的是前面一半的数，则返回 0 ，如果得到后面一半的数，则返回 1，得到中点位置的数，则继续重试；

这样一来，就加工出一个等概率随机生成 0 或 1 的函数 rand01()，然后判断 1 ~ d - c + 1 这个区间需要几个二进制，即上述rand(int N)方法，就可以得到随机生成 c ~ d 的函数。

完整代码如下

    // 底层依赖一个等概率返回a~b的随机函数f，
    // 如何加工出等概率返回c~d的随机函数
    public static int g(int a, int b, int c, int d) {
        int range = d - c; // 0～range c~d -> 0 ~ d-c
        int num = 1;

        while ((1 << num) - 1 < range) { // 求0～range需要几个2进制位
            num++;
        }
        int ans; // 最终的累加和，首先+0位上是1还是0，1位上是1还是0，2位上是1还是0...
        do {
            ans = 0;
            for (int i = 0; i < num; i++) {
                ans += (rand01(a, b) << i);
            }
        } while (ans > range);
        return ans + c;
    }

    // 底层依赖一个等概率返回a~b的随机函数f，
    // 如何加工出等概率返回0和1的随机函数
    public static int rand01(int a, int b) {
        // a = 4, b = 8
        // size = 5
        int size = b - a + 1;
        // odd = true
        // 是否为奇数
        boolean odd = size % 2 != 0;
        // mid = 2
        int mid = size / 2;
        int ans;
        do {
            // 如果是奇数，那么中点位置弃用，< 中点 位置 和 > 中点位置的数字返回概率一样，一个定为0，一个定为1
            // 如果是偶数，那么这里的中点是上中点，< 上中点 位置 和 >= 上中点位置的数字出现的概率一样，一个定为0，一个定为1即可
            ans = f(a, b) - a;
        } while (odd && ans == mid);
        // 来到这步的时候，
        // 如果是偶数，ans可能会等于mid
        // 如果是奇数，ans必不等于mid
        return ans < mid ? 0 : 1;
    }

    // 构造一个等概率返回a~b的随机函数
    public static int f(int a, int b) {
        // Math.random() -> [0, 1)
        // [a, b] -> a + [0,b-a] -> a + (int)(Math.random() * (b-a+1))
        return a + (int) (Math.random() * (b - a + 1));
    }

随机函数变换示例

随机函数变换相关技巧

说明#

问题一#

问题二#

问题三#

问题四#

问题五#

更多#