播种多个随机数生成器 [英] Seeding Multiple Random Number Generators

问题描述

我最近在另一篇文章的评论中讨论了相同类型的多个随机数生成器的初始化，在该讨论中，我们提出了以下问题：

1）用不同的种子创建同一随机数生成器的多个实例，并在程序的不同部分中使用这些随机数生成器是一个好主意吗？

2）特别地，使用.Net Random类（如下所述）创建随机数生成器并在不同程序上下文中使用每个RNG的技术是否会引起问题：

  int的大小= 64; //使用
 int种子的RNG数量； //使用某种常规技术获取种子
 Random [] r = new Random [size]; 
 
 for（int i = 0; i  {
 r [i] = new Random（seed + i）; 
} 
  

3）如果需要多个随机数流，您会怎么建议？

4）在需要线程安全的情况下，您如何建议生成随机数？

解决方案

1）创建具有不同种子的同一随机数生成器的多个实例，并在程序的不同部分中使用这些随机数生成器是一个好主意吗？

否。通常不建议使用上述方案。

在他的书《计算机编程的艺术》，第2卷：半数值算法中。 Addison-Wesley，马萨诸塞州雷丁，第三版，1997年，Knuth博士指出

发明一个万无一失的

在这种情况下，我指出从随机序列中获取子序列的随机性可能小于原始随机序列数字：

• 
  
  

  这些类型的随机数发生器也严重依赖于他们最初的55号状态的初始化。不良的初始化可能会导致不良的随机数。在上述情况下，相似的状态可能会导致来自每个不同随机数生成器的相关随机数。 Microsoft甚至在其有关System.Random的MSDN帖子中建议对此：

  
  
  

  请注意突出显示的列：

  
  
  

  我还希望添加另一条注释，即创建一个随机数列表并从每一行的列表中获取一个随机数也会产生看起来很差的随机数（众所周知，此处使用的RNG毕竟在统计上失败了！）。

  
  
  

  3 ）所使用的RNG的类型取决于您的上下文。有些人可能对上面的输出感到满意。在其他情况下，使用的RNG可能无法使用（Monte Carlo Simulation和Cryptography是两种情况，即使对于一个随机数流，也不应永远使用System.Random）。

  
  
  

  如果需要提取随机数的多个子序列，请找到为此目的而设计的RNG：

  
  
  
  
  
  • PCG
  
  
  
  
  

  4）最后，如果要在多个线程中使用System.Random怎么办？
  Microsoft MSDN在我上面提到的同一链接中有答案：

  
  
  
  
  
  • MSDN System.Random类和线程安全
  
  
  
  

  I have recently been discussing the initialisation of multiple random number generators of the same type in the comments of another post and in that discussion we asked the following questions:

  1) Is it a good idea to create multiple instances of the same random number generator with different seeds and use these random number generators in different parts of the program?

  2) In particular, can the technique of creating random number generators using the .Net Random class, seeded as below, and using each RNG in different program contexts cause problems:

  int size = 64;  // The number of RNGs to use
  int seed;       // Get seed using some normal technique
  Random[] r = new Random[size];
  
  for (int i = 0; i < size; i++)
  {
      r[i] = new Random(seed + i);
  }
  

  3) What would you recommend instead if multiple streams of random numbers are required?

  4) How would you recommend generating random numbers when thread safety is required?

  解决方案

  1) Is it a good idea to create multiple instances of the same random number generator with different seeds and use these random number generators in different parts of the program?

  No. The above scheme is in general not recommended.

  In his book, The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley, Reading, MA, third edition, 1997, Dr. Knuth states that

  It is not easy to invent a foolproof source of random numbers.

  In this case, I point out that taking subsequences from a random sequence may be less random than the original sequence of random numbers:

  • Random Numbers
  • PCG

  Notice that Micosoft's Random implementation is based on a subractive lagged-fibonacci generator:

  • Reference Source - System.Random

  This kind of random number generator is known for an inbuilt three-point correlation, after all, we're generating the next random number:

  These kinds of Random Number Generators also depend heavily on the initialisation of their initial 55 number state. Poor initialisation may lead to poor random numbers. In the above case, similar states, may result in correlated random numbers from each of the different random number generators. Microsoft even recommends against this in their MSDN post about System.Random: MSDN The System.Random class and thread safety:

  Instead of instantiating individual Random objects, we recommend that you create a single Random instance to generate all the random numbers needed by your app.

  We shall look at an example where a particular initialisation creates strong correlation between the different random number generators and look for alternatives.

  2) I have implemented a program that attempts to initialise 64 instances of Random as described above so that we observe any visible flaws. I chose a particular initialisation as a proof of concept:

  int size = 64;    // The number of random numbers generators
  int length = 20;  // The number of random numbers from each generator
  int steps = 18;   // Move 18 steps forward in the beginning to show a particular phenomenon
  
  Random[] r = new Random[size];
  
  for (int i = 0; i < size; i++)
  {
       r[i] = new Random(i + 1);
  
       // move RNG forward 18 steps
       for (int j = 0; j < steps; j++)
       {
            r[i].Next(3);
       }
  }
  
  
  for (int i = 0; i < size; i++)
  {
       for (int j = 0; j < length; j++)
       {
            Console.Write(r[i].Next(3) + ", ");  // Generate a random number, 0 represents a small number, 1 a medium number and 2 a large number
       }
  
       Console.WriteLine();
  }
  

  This program generates the output shown here, each row represents the output from another RNG:

  Notice that the highlighted columns: at particular places the RNGs seem to synchronise and produce output that does not look independent from each other.

  I also wish to add another note, that creating a single list of random numbers and taking one random number from the list of each row also produces poor looking random numbers (the RNG being used here is known to have fail some statistical after all!).

  3) The type of RNG used depends on your context. Some may be happy with the above output. In other cases, the RNG used may be unusable (Monte Carlo Simulation and Cryptography are two scenarios where System.Random should never be used, even for one stream of random numbers).

  If you need to extract multiple subsequences of Random Numbers, find an RNG that has been designed for that purpose:

  • PCG

  4) Finally, what if I want to use System.Random in multiple threads? Microsoft MSDN has the answer in the same link I referred to above:

  • MSDN The System.Random class and thread safety

  这篇关于播种多个随机数生成器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！