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

Question

有没有办法将一个范围的均匀分布随机数转换为另一个范围的均匀分布随机数节俭 ?
让我解释一下我所说的“ 节俭”是什么意思。
在给定范围内生成随机数的典型方法(例如 r ∈ [0..10) )是采用一些固定的随机位，比如说 31，这会产生小于 2147483648 的非负随机数。然后确保该值小于 2147483640(因为 2147483648 不能被 10 整除，因此可能导致分布不均)。如果该值大于或等于 2147483640，则将其丢弃并重试(获取接下来的 31 个随机位等)。如果 value 小于 2147483640，则只返回除以 10 的余数。这种方法每个十进制数字至少消耗 31 位。由于理论极限是log2(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) 的均匀分布随机数(稍后称为目标编号)，每个目标编号仅消耗日志(t)+ C 源编号？其中 C 是某个常数。
如果没有这种方法，为什么？是什么阻止了达到理想极限？
节俭的目的是减少对 RNG 的调用次数。当我们使用通常吞吐量有限的 True RNG 时，这尤其值得做。
至于“节俭优化”，它们基于以下假设:

给定均匀随机数 r ∈ [0,N)，在检查 r < M (if M <= N) 之后，我们可以假设它均匀分布在 [0,M) 中。传统的拒绝方法实际上就是基于这个假设。类似地，在检查 r >= M 之后，我们可以假设它在 [M,N) 中均匀分布。

给定均匀随机数 r ∈ [A,B)，导出的随机数 (r+C) 均匀分布于 [A+C,B+C)。 IE。我们可以将任何常数与随机数相加或相减以改变其范围。

给定均匀随机数 r ∈ [0,N)，其中 N=P × Q，导出的随机数 (r%P) 均匀分布于 [0,P) 且 (r/P) 均匀分布于 [0,问)。 IE。我们可以将一个统一的随机数拆分成几个。

给定均匀随机数 p ∈ [0,P) 和 q ∈ [0,Q)，导出的随机数 (q× P + p) 均匀分布于 [0,P × Q)]。 IE。我们可以将统一的随机数合二为一。

Answer 1

您的目标最终是在仅给定 p 面骰子的情况下掷出 k 面骰子，而不会浪费随机性。
从这个意义上说，根据 B. Kloeckner 的“Simulating a dice with a dice”中的引理 3，这种浪费是不可避免的，除非“每个除 k 的质数也整除 p”。因此，例如，如果 p 是 2 的幂(并且任何随机位块都与掷骰子的面数为 2 的幂相同)并且 k 的质因数不是 2，那么您能做的最好的事情是随意接近不浪费随机性。
此外，除了批量位以减少“位浪费”(另见 Math Forum)，还有随机性提取技术，在 Devroye and Gravel 2015-2020 中讨论过。在我的 Note on Randomness Extraction 中.
另见问题:How to generate a random integer in the range [0,n] from a stream of random bits without wasting bits? ，尤其是我在那里的回答。