随机生成极低概率结果

Question

我正在为一个科学项目尝试在C#中获取随机布尔值。问题是，布尔值为真的几率必须在10^-12到10^-14左右; 默认的随机函数只生成整数，并且0和[u]int.max之间的值远远不够大。

如何生成具有如此低的真实几率的随机布尔值？

- Sebb

---

如果使用NextBytes，您可以获得更大的值范围 - Panagiotis Kanavos

Answer 1

编辑

Random.NextDouble() 无法给出预期的结果！

正如Kyle在下面的评论中建议的那样，Random.NextDouble() 的实现将一个 int 映射到区间 [0.0 , 1.0)，这实际上使我的代码等价于 r.Next(0, Int32.MaxValue) == 0。添加更多的零不会影响结果为假的概率。

使用其他答案之一，或使用此代码从 System.Random 生成一个 ulong（范围为 0-18446744073709551615）。

var r = new Random();
var bytes = new byte[8];
r.NextBytes(bytes);
ulong result = BitConverter.ToUInt64(bytes, 0);

---

警告：不会按预期工作，请勿使用！仅供参考。

---

请使用 Random.NextDouble() 替代：其结果为介于 0.0 和 1.0 之间的 double 类型数值。

var r = new Random();
var probablyFalseBool = r.NextDouble() < 0.0000000000001;

如有必要，请更改零的数量。

- Rik

---

选择了这个答案，因为它是最简单的方法。感谢您的贡献，您将在参考文献中被提及;) - Sebb

我认为这不会按照你的期望运作。基于.NET 4.5中System.Random的源代码，此处给出的代码将导致与var probablyFalseBool = r.Next(0,Int32.MaxValue) == 0相同的结果，因为Random.Next调用与Random.NextDouble调用相同的受保护的Sample方法。 - Kyle

我同意 @Kyle 的观点，NextDouble 方法的分辨率为 1/Int32.MaxValue（约 1/20亿），因此在需要更高分辨率时不足以使用。 - Matthew

@Kyle 很好的发现！我编辑了我的答案，以引导未来的用户不要使用 NextDouble() 来实现这个目的。 - Rik

@Rik 感谢您的测试和编辑，我现在无法检查它 :) - Sebb

Answer 2

尝试将多个随机选择结合起来：

if(rnd.Next(0,10000) == 0 && rnd.Next(0,10000) == 0 && rnd.Next(0,10000) == 0){
}

我不确定C#语法是否正确，但这个if块有10^-12的概率会被执行。

- Antonio Ragagnin

---

你比我快了12秒。 - Matthew

我认为Rik的答案是最简单和最优化的方法。多次使用这个解决方案既不美观，也不太优化。 - Nathan A

@PanagiotisKanavos，接着就变得有点复杂了，要根据十进制的概率来提取值。 - Antonio Ragagnin

@NathanA 顺便说一句，除非OP有某种超级计算机，否则我怀疑他不会看到概率为10^-14的任何结果。 - Antonio Ragagnin

@AntonioRagagnin 这很正确，但它不在问题的范围之内。我只是在可能的情况下更喜欢漂亮和优化过的代码。 - Nathan A

Answer 3

你可以使用NextBytes方法来获取大的随机数。

例如，这将使得布尔值为true的概率为2.842e-14：

Random r = new Random();
byte[] buffer = new byte[6]; // make an array with 48 bits
r.NextBytes(buffer);
buffer[0] &= 0xf8; // mask out three bits to make it 45
bool occured = buffer.Sum(b => b) == 0;

- Guffa

Answer 4

正如Nathan所建议的那样，您可以使用Next方法来指定结果的范围。

然后，您可以使用&&运算符来确保它达到您的精度要求。

// 1 in a million
var result = random.Next(0, 1000) == 0 && random.Next(0, 1000) == 0; 

你可以随后更改它们以获得你想要的汇率。

- Matthew

Answer 5

您可以像这样轻松地控制赔率：

var result = rnd.Next(0,100) == 0;

这将使得result为真的概率为100分之1。您可以轻松地将值调整为所需的任何概率。

- Nathan A

---

我认为仅使用 Next 方法不具有足够的精度。 - Matthew

这似乎不符合1/10,000,000,000,000的概率。 - Stefan

他的要求明确说明了为什么他不能这样做。 - Jonesopolis

@paqogomez 这里的100是不包含在内的，所以值为0-99，意味着每100次中只有1次机会。 - Nathan A

@NathanA 人们所说的是 Next() 方法不包含足够的精度 - 参数类型不足以容纳值为10,000,000,000,000。 - qJake

是的，我错过了那部分。抱歉。 - Nathan A

Answer 6

多维度的Go！一个正常的随机数在一维（即沿着一条线）。通过将两个随机数相乘，您使用了两个维度，依此类推。

如果您取6个1到100之间的随机整数，然后将它们相乘，得到结果为1的概率是10^12中的1。同样，对于4个1到1000之间的随机整数或3个1到10000之间的随机整数也是如此。

如果您想要像10^12中的30这样的结果，则使用1到1,000,000之间的两个随机数，并且您希望其中一个是1，另一个小于等于30。

如果您想要10^12中的x（<1,000,000）这样的结果，则使用1到1,000,000之间的两个随机数，并且您希望其中一个是1，另一个小于等于x。

- user1228123

Answer 7

生成两个相邻的整数表示

(target_value div int_max, target_value mod int_max)

检查第一个参数是否为0，第二个参数是否小于desired_precison * int_max。

如果您对引入偏差有疑虑，请在测试前随机交换一对整数的顺序。

下面是示例代码，展示了这种技术（已经在这里进行过测试）：

using System.IO;
using System;

class Program
{
    static void Main(string[] args)
    {
        bool   flip, strike;
        int    eps, lo, hi;
        Random rnd;

        eps = Int32.Parse(args[0]); // whatever is appropriate

        rnd = new Random();
        lo = rnd.Next(Int32.MaxValue);
        hi = rnd.Next(Int32.MaxValue);
        flip = (rnd.Next() > 0.5); 
        if (flip) { int swap; swap = lo; lo = hi; hi = swap; }

        strike = (hi == 0) && (lo < eps);

        Console.Write("[hi lo] = ");
        Console.Write(hi);
        Console.WriteLine(lo);
        if (strike) {
            Console.WriteLine("strike");
        }
    }
}

- collapsar

---

不错的想法，但是它的性能很差。执行十亿次花费了38807毫秒，几乎是标记方法的两倍（19630毫秒）。 - Sebb

是的，对 prng 的调用应该占据执行时间的主导地位。 - collapsar

不行，肯定是其他地方的问题，因为四次随机函数仍然比两次快。我已经删除了控制台输出和变量声明，但还是没有改善。测试的源代码在这里。 - Sebb

在你的测试代码中，建议的方法被触发的概率约为1/2^-(31+31-4) ~ 3.5*10^-18；因此，您的目标阈值下限低了大约2个数量级！ - collapsar

是的，但这只是测试代码。我将在一个具有动态机会计算的大型框架中使用它，实际代码是 chance = 2.5 * Math.Pow(10, -12) * (((tdx21+tdx12)/2)*(30/3.6)) + ((2949768/(5.1*(Math.Pow(10, -14))))*(157766400^-1)) * (((tdx21+tdx12)/2)*(30/3.6));；不适用于基准测试。 - Sebb

当然，但你在测试代码时假设它的触发概率为10^-16，而实际上它小于10^-17。因此，预期运行时间应该比竞争实现长10倍以上，但实际上只慢了2倍。这让我感到困惑，因为今天的浮点硬件效率表明Riks的解决方案确实应该更快。 - collapsar

Answer 8

你可以使用Round.NextDouble或Round.NextBytes来获取更广泛的范围，而不是使用Round.Next。

使用NextBytes，你可以使用4-5字节的缓冲区来获取所需的范围。大致上，你可以像这样做：

var buffer=new byte[5];
rnd.NextBytes(buffer);
return buffer.All(b=>b>0);

使用BitArray可能可以让这个过程更快。

如果使用NextDouble，则需要检查结果是否小于1 / 10^12。

- Panagiotis Kanavos