时间戳

首页 > 解决方案 > 均匀分布的随机数从一个范围到另一个范围的节俭转换

algorithm - 均匀分布的随机数从一个范围到另一个范围的节俭转换

问题描述

有没有办法节俭地将一个范围的均匀分布的随机数转换为另一个范围的均匀分布的随机数？

让我解释一下我所说的“节俭”是什么意思。

在给定范围内生成随机数的典型方法（例如 r ∈ [0..10) ）是采用一些固定的随机位，比如 31，这会产生小于 2147483648 的非负随机数。然后确保该值小于 2147483640（因为 2147483648 不能被 10 整除，因此可能导致分布不均）。如果该值大于或等于 2147483640，请将其丢弃并重试（获取接下来的 31 个随机位，依此类推）。如果值小于 2147483640，则只返回除以 10 的余数。这种方法每个十进制数字至少消耗 31 位。由于理论上的限制是 log 2 (10) = 3.321928...，这是相当浪费的。

我们可以改进这一点，如果我们使用 4 位而不是 31。在这种情况下，我们将消耗 4 × 1.6 = 6.4 位每个十进制数字。这更节俭，但仍远非理想。

    public int nextDit() {
        int result;
        do {
            result = next4Bits();
        } while (result >= 10);
        return result;
    }

我们可以尝试一次生成 3 个十进制数字。由于 1024 非常接近 1000，因此原始源随机数被拒绝的概率比以前的情况要小。一旦我们生成了 3 个十进制数字，我们返回 1 个数字并保留其余 2 个数字。

像下面的东西

    private int _decDigits = 0;
    private int _decCount = 0;

    public int nextDit() {
        if (_decCount > 0) {
            // take numbers from the reserve
            int result = _decDigits % 10;
            _decDigits /= 10;
            _decCount -= 1;
            return result;
        } else {
            int result;
            do {
                result = next10Bits();
            } while (result >= 1000);
            // reserve 2 decimal digits
            _decCount = 2;
            _decDigits = result % 100;
            result /= 100;
            return result;
        }
    }

这种方法更加节俭：每个十进制数字消耗 10 × 1.024 / 3 = 3.41(3) 位。

如果我们尝试重复使用我们之前丢弃的数字，我们甚至可以走得更远。随机数 r ∈ [0, 1024) 属于以下 3 个范围之一：[0, 1000)、[1000, 1020)、[1020, 1024)。

如果它落入[0, 1000)，我们像以前一样，保留2个十进制数字（十进制数字保留）并返回1个十进制数字。

如果它落入 [1000, 1020)，我们减去 1000 转换为范围 [0, 20)。然后我们通过将其除以 10 获得 1 位，通过将除以 10 的余数获得 1 个十进制数字。我们将该位放入二进制数字保留并返回十进制数字。

如果它落入 [1020, 1024)，我们减去 1020 转换为范围 [0, 4)。在这里，我们只得到 2 位，我们将其放入二进制数字储备中。

    // decimal digit reserve
    private int _decDigits = 0;
    private int _decCount = 0;
    // binary digit reserve
    private int _binDigits = 0;
    private int _binCount = 0;

    private int nextBits(int bits, int n) {
        for (int i = 0; i < n; i += 1) {
            bits = (bits << 1) + _bitRandomDevice.nextBit();
        }
        return bits;
    }

    private int next10Bits() {
        // take bits from the binary reserve first, then from _bitRandomDevice
        int result;
        if (_binCount >= 10) {
            result = _binDigits >> (_binCount - 10);
            _binDigits = _binDigits & (1 << (_binCount - 10) - 1);
            _binCount -= 10;
        } else {
            result = nextBits(_binDigits, 10 - _binCount);
            _binCount = 0;
            _binDigits = 0;
        }
        return result;
    }

    public int nextDit() {
        if (_decCount > 0) {
            // take numbers from the decimal reserve
            int result = _decDigits % 10;
            _decDigits /= 10;
            _decCount -= 1;
            return result;
        } else {
            int result;
            while (true) {
                result = next10Bits();
                if (result < 1000) {
                    assert result >= 0 && result < 1000;
                    // reserve 2 decimal digits
                    _decCount = 2;
                    _decDigits = result % 100;
                    result /= 100;
                    // return 1 decimal digit
                    return result;
                } else if (result < 1020) {
                    result -= 1000;
                    assert result >= 0 && result < 20;
                    // reserve 1 binary digit
                    _binCount += 1;
                    _binDigits = (_binDigits << 1) + (result / 10);
                    // return 1 decimal digit
                    return result % 10;
                } else {
                    result -= 1020;
                    assert result >= 0 && result < 4;
                    // reserve 2 binary digits
                    _binCount += 2;
                    _binDigits = (_binDigits << 2) + result;
                }
            }
        }
    }

这种方法每个十进制数字消耗大约 3.38... 位。这是我能找到的最节俭的方法，但它仍然会浪费/丢失随机源的一些信息。

因此，我的问题是：是否有任何通用方法/算法可以将一个任意范围 [0, s) 的均匀分布的随机数（后来称为源数）转换为另一个任意范围 [0, t) 的均匀分布的随机数（稍后称为目标编号），每个目标编号仅消耗 log s (t) + C 源编号？其中 C 是某个常数。如果没有这种方法，为什么？是什么阻止了达到理想的极限？

节俭的目的是减少对 RNG 的调用次数。当我们使用吞吐量有限的 True RNG 时，这样做尤其值得。

至于“节俭优化”，它们基于以下假设：

标签： algorithmrandom

解决方案

您的目标最终是在不浪费随机性的情况下，仅在给定p面骰子的情况下掷出k面骰子。

在这个意义上， B. Kloeckner在“用骰子模拟骰子”中引理 3指出，这种浪费是不可避免的，除非“每个除k的素数也除p ”。因此，例如，如果p是 2 的幂（并且任何随机位块都与以 2 面数的幂掷骰子相同）并且k的质因数不是 2，那么您能做的最好的事情就是任意接近不浪费随机性。

此外，除了批处理位以减少“位浪费”（另请参见数学论坛）之外，还有随机提取技术，在Devroye 和 Gravel 2015-2020以及我的关于随机性提取的注释中进行了讨论。

另请参阅问题：如何在不浪费位的情况下从随机位流中生成 [0,n] 范围内的随机整数？，尤其是我的回答。

推荐阅读