Estaba mirando una pregunta que hablaba de una mala implementación del algoritmo de barajado de Fisher-Yates y me quedé perplejo de que había un sesgo cuando se implementaba incorrectamente.

Los dos algoritmos son estos:

 private Random _random = new Random(); public int[] FisherYates(int[] source) { int[] output = source.ToArray(); for (var i = 0; i < output.Length; i++) { var j = _random.Next(i, output.Length); (output[i], output[j]) = (output[j], output[i]); } return output; } public int[] FisherYatesBad(int[] source) { int[] output = source.ToArray(); for (var i = 0; i < output.Length; i++) { var j = _random.Next(0, output.Length); (output[i], output[j]) = (output[j], output[i]); } return output; }

Una diferencia realmente sutil, pero suficiente para causar un sesgo masivo.

Buena implementación:

Mala implementación:

Para ser claro acerca de estos gráficos, empiezo con los números del 0 al 99, creo 10_000_000 mezclas utilizando cualquier algoritmo y luego hago un promedio de los valores en cada una de las mezclas para obtener un único conjunto de cifras. Si la mezcla es aleatoria, las 100 figuras pertenecerían a la misma distribución normal.

Ahora, todo está bien, pero pensé en verificar si estos métodos producen resultados válidos:

 public int[] OrderByRandomNext(int[] source) => source.OrderBy(x => _random.Next()).ToArray(); public int[] OrderByRandomNextDouble(int[] source) => source.OrderBy(x => _random.NextDouble()).ToArray();

Ambos son agradables y ordenados, pero ¿son una mezcla justa?

OrderByRandomNext :

OrderByRandomNextDouble :

¿Observe que las cifras 1 y 100 son significativamente más bajas en cada una?

Bueno, pensé que podría ser un artefacto de cómo funciona OrderBy . Así que lo probé con otro generador de números aleatorios, uno traído para usar por Eric Lippert en su serie Random mejorada.

 public int[] OrderByBetterRandomNextDouble(int[] source) => source.OrderBy(x => BetterRandom.NextDouble()).ToArray(); public static class BetterRandom { private static readonly ThreadLocal<RandomNumberGenerator> crng = new ThreadLocal<RandomNumberGenerator>(RandomNumberGenerator.Create); private static readonly ThreadLocal<byte[]> bytes = new ThreadLocal<byte[]>(() => new byte[sizeof(int)]); public static int NextInt() { crng.Value.GetBytes(bytes.Value); return BitConverter.ToInt32(bytes.Value, 0) & int.MaxValue; } public static double NextDouble() { while (true) { long x = NextInt() & 0x001FFFFF; x <<= 31; x |= (long)NextInt(); double n = x; const double d = 1L << 52; double q = n / d; if (q != 1.0) return q; } } }

Bueno, aquí está el gráfico:

¡No hay prejuicios!

Aquí está mi código para generar los datos (ejecutar en LINQPad):

 void Main() { var n = 100; var s = 1000000; var numbers = Enumerable.Range(0, n).ToArray(); var algorithms = new Func<int[], int[]>[] { FisherYates, OrderByRandomNext, OrderByRandomNextDouble, OrderByBetterRandomNextDouble, }; var averages = algorithms .Select(algorithm => Enumerable .Range(0, numbers.Length) .Select(x => Enumerable .Range(0, s) .Select(y => algorithm(numbers)) .Aggregate(0.0, (a, v) => a + (double)v[x] / s)) .ToArray()) .Select(x => new { averages = x, distribution = Accord.Statistics.Distributions.Univariate.NormalDistribution.Estimate(x.Skip(1).SkipLast(1).ToArray()), first = x.First(), last = x.Last(), }) .Select(x => new { x.averages, x.distribution, x.first, x.last, first_prob =x.distribution.DistributionFunction(x.first), last_prob = x.distribution.DistributionFunction(x.last), }) .ToArray(); var d = averages.Dump(); } private Random _random = new Random(); public int[] FisherYates(int[] source) { int[] output = source.ToArray(); for (var i = 0; i < output.Length; i++) { var j = _random.Next(i, output.Length); (output[i], output[j]) = (output[j], output[i]); } return output; } public int[] OrderByRandomNext(int[] source) => source.OrderBy(x => _random.Next()).ToArray(); public int[] OrderByRandomNextDouble(int[] source) => source.OrderBy(x => _random.NextDouble()).ToArray(); public int[] OrderByBetterRandomNextDouble(int[] source) => source.OrderBy(x => BetterRandom.NextDouble()).ToArray(); public static class BetterRandom { private static readonly ThreadLocal<RandomNumberGenerator> crng = new ThreadLocal<RandomNumberGenerator>(RandomNumberGenerator.Create); private static readonly ThreadLocal<byte[]> bytes = new ThreadLocal<byte[]>(() => new byte[sizeof(int)]); public static int NextInt() { crng.Value.GetBytes(bytes.Value); return BitConverter.ToInt32(bytes.Value, 0) & int.MaxValue; } public static double NextDouble() { while (true) { long x = NextInt() & 0x001FFFFF; x <<= 31; x |= (long)NextInt(); double n = x; const double d = 1L << 52; double q = n / d; if (q != 1.0) return q; } } }

Aquí están los datos que generé:

distribucion | primero | último | primer_prob | último_prob            
-------------------------------------------------- ------ | ------------------ | ------------------ | ------------------------------------- | ---------------------
N(x; μ = 49,50267467345823, σ² = 0,0008896228453062147) | 49.505465999987585 | 49.49833699998965 | 0.5372807100387846 | 0.44218570467529394  
N(x; μ = 49,50503062243786, σ² = 0,0009954477334487531) | 49.36330799998817 | 49.37124399998651 | 3.529550818615057E-06 | 1.115772521409486E-05
N(x; μ = 49,505720877539765, σ² = 0,0008257970106087029) | 49.37231699998847 | 49.386660999990106 | 1.7228855271333998E-06 | 1.712972513601141E-05
N(x; μ = 49,49994663264188, σ² = 0,0007518765247716318) | 49.50191999998847 | 49.474235999989205 | 0.5286859991636343 | 0.17421285127499514  

Aquí está mi pregunta. ¿Qué pasa con System.Random y el sesgo que introduce?