随机序列的周期长度

Question

以下 LINQPad 代码生成从 0 到 N 的唯一整数的随机序列，并计算从 0 开始的每个整数的循环长度。为了计算给定整数的循环长度，它读取值从索引等于该整数的 boxes 数组中获取值并从等于该值的索引中读取，依此类推。当从数组中读取的值等于我们开始使用的原始整数时，该过程停止。用于计算每个循环长度的迭代次数被保存到 Dictionary.

const int count = 100;

var random = new Random();
var boxes = Enumerable.Range(0, count).OrderBy(x => random.Next(0, count - 1)).ToArray();
string.Join(", ", boxes.Select(x => x.ToString())).Dump("Boxes");

var stats = Enumerable.Range(0, count).ToDictionary(x => x, x => {
  var iterations = 0;
  var ind = x;
  while(boxes[ind] != x)
  {
    ind = boxes[ind];
    iterations++;
  }
  return iterations;
});

stats.GroupBy(x => x.Value).Select(x => new {x.Key, Count = x.Count()}).OrderBy(x => x.Key).Dump("Stats");
stats.Sum(x => x.Value).Dump("Total Iterations");

典型结果如下：

我得到的结果对我来说很奇怪：

所有周期的长度只能分为几个桶（通常是 3 到 7 个）。我希望看到更多不同的桶。
大多数时候每个桶中的元素数量随着它们所属的桶值一起增长。我希望它会更随机。

我尝试了几种不同的随机化函数，例如 .NET 的 Random 和 RandomNumberGenerator 类，以及从 random.org 生成的随机数据。所有这些似乎都产生了相似的结果。

我是不是做错了什么？从数学的角度来看，这些结果是预期的吗？或者，也许我使用的随机化函数的伪特性有副作用？

Answer 1

您正在做的是生成大小为 count 的随机排列。然后检查排列的属性。如果你的随机数生成器很好，那么你应该观察 random permutations.

的统计数据

长度为k的平均循环数为1/k，k<count。平均而言，有 1 个固定点、1/2 个长度为 2 的循环、1/3 个长度为 3 的循环，等等。因此，任何长度的平均循环数为 1+1/2+1/3+... +1/计数 ~ ln 计数 + gamma. There are a lot of neat properties of the distribution of the number of cycles。很少有很多循环，但是 2^# 个循环的平均值是 count+1。

你的buckets对应的是不同循环长度的个数，最多是循环个数，但可能会因为重复的循环长度而变小。平均而言，重复的周期长度很少。即使计数增加到无穷大，并且平均循环数增加到无穷大，重复循环长度的平均数仍然是有限的。

统计学中的排列检验，通常是bootstrapping的例子，分析某些类型的数据，你把它看成一个排列的例子。例如，您可能观察到两个数量，x_i 和 y_i。您可以通过对 xs 和 ys 进行排序并查看 y 值的索引与第 k 个 x 值配对来获得排列。然后将此排列的统计数据与随机排列的属性进行比较。这并没有对底层分布做出太多假设，但它仍然可以检测到 x 和 y 似乎相关的时间。因此，了解从随机排列中得到什么是很有用的。

随机序列的周期长度

Lengths of cycles in random sequence

c#

arrays

algorithm

random

cycle