mercredi 17 juin 2015

Lengths of cycles in random sequence

The following LINQPad code generates random sequence of unique integers from 0 to N and calculates the length of cycle for every integer starting from 0. In order to calculate cycle length for a given integer, it reads value from boxes array at the index equal to that integer, than takes the value and reads from the index equal to that value, and so on. The process stops when the value read from array is equal to original integer we started with. The number of iterations spent to calculating the length of every cycle gets saved into a 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");

Typical result looks as follows:

Result from LINQPad

The results I am getting seem weird to me:

  • The lengths of all cycles can be grouped into only few buckets (usually 3 to 7). I was hoping to see more distinct buckets.
  • The number of elements in every bucket most of the time grows together with the bucket value they belong to. I was hoping that it would be more random.

I have tried several different randomize functions, like .NET's Random and RandomNumberGenerator classes, as well as random data generated from random.org. All of them seem to produce similar results.

Am I doing something wrong? Are those results expected from mathematical point of view? Or, perhaps, the pseudo nature of randomizing functions that I used have side effects?




Aucun commentaire:

Enregistrer un commentaire