随机函数变换示例

随机函数变换示例

作者：Grey

原文地址:随机函数变换示例

说明

本示例中基于 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，代码如下

package snippet;public class Code_0004_RandToPow2 {    // 将`[0,x)`中的数出现的的概率调整成`x^2`    public static double randToPow2() {        return Math.max(Math.random(), Math.random());    }}

我们可以通过如下测试代码来验证问题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.02886030.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()

和问题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 01 10 11 0

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

0 11 0

概率一定一样

所以得到 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;    }}

更多

算法和数据结构笔记