c# - repetir - Los números aleatorios no parecen muy aleatorios

propiedad random c#

Question

Intento generar números base32 aleatorios de 6 caracteres o menos. Esto debería dar aproximadamente 1,000 millones de combinaciones diferentes.

Creé un programa para generar estos números "aleatorios". Sin embargo, parece que genera un duplicado en promedio cada 40,000 generaciones.

¿Por qué estos números "aleatorios" se duplican con tanta frecuencia cuando hay más de mil millones de combinaciones diferentes?

Aquí está mi código:

static void Main(string[] args)
{
    int seed = Environment.TickCount;
    Random r = new Random(seed);

    Dictionary<int, int> resultDictionary = new Dictionary<int, int>();
    for (int x = 1; x <= 1000; x++)
    {
        Dictionary<string, int> dictionary = new Dictionary<string, int>();
        try
        {
            while (true)
            {
                int rand = r.Next(0, 1073741823);
                CrockfordBase32Encoding encoding = new CrockfordBase32Encoding();
                string encodedRand = encoding.Encode((ulong)rand, false);
                dictionary.Add(encodedRand, rand);
            }
        }
        catch (Exception)
        {
        }
        Console.WriteLine(string.Format("{0} - {1}", x, dictionary.Count));
        resultDictionary.Add(x, dictionary.Count);
        x++;
    }

    Console.WriteLine();
    Console.WriteLine("Average Number Before Duplicate: " + resultDictionary.Average(x => x.Value));
    Console.ReadLine();
}

Answer 1

El generador de números aleatorios incluido en el Marco es pseudoaleatorio sin garantía de distribución de números aleatorios. Si le preocupan los patrones de distribución, considere este artículo: http://www.codeproject.com/Articles/15102/NET-random-number-generators-and-distributions

Sin embargo, mis profesores de estadística (no uno) solían decir: "Hay una pequeña mentira, una gran mentira, y hay estadísticas".

Primero, el código completo, para que la gente no tenga que buscar en Internet buscando implementaciones de clase para probar:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            var r = RandomProvider.GetThreadRandom();

            Dictionary<int, int> resultDictionary = new Dictionary<int, int>();
            for (int x = 1; x <= 1000; x++)
            {
                Dictionary<string, int> dictionary = new Dictionary<string, int>();
                try
                {
                    while (true)
                    {
                        int rand = r.Next(0, 1073741823);
                        CrockfordBase32Encoding encoding = new CrockfordBase32Encoding();
                        string encodedRand = encoding.Encode((ulong)rand, false);
                        dictionary.Add(encodedRand, rand);
                    }
                }
                catch (Exception)
                {
                }
                Console.WriteLine("{0} - {1}", x, dictionary.Count);
                resultDictionary.Add(x, dictionary.Count);
                x++;
            }

            Console.WriteLine();
            Console.WriteLine("Average Number Before Duplicate: " + resultDictionary.Average(x => x.Value));
            Console.WriteLine("Minimum Number Before Duplicate: " + resultDictionary.Min(x => x.Value));
            Console.WriteLine("Maximum Number Before Duplicate: " + resultDictionary.Max(x => x.Value));
            Console.WriteLine(" Median Number Before Duplicate: " + resultDictionary.Select(x=>x.Value).Median());
            Console.ReadLine();
        }


    }

    public static class Extensions
    {
        public static double Median<T>(this IEnumerable<T> list)
        {
            List<double> orderedList = list.Select(s=>Convert.ToDouble(s))
                .OrderBy(numbers => numbers)
                .ToList();

            int listSize = orderedList.Count;
            double result;

            if (listSize % 2 == 0) // even
            {
                int midIndex = listSize / 2;
                result = ((orderedList.ElementAt(midIndex - 1) +
                           orderedList.ElementAt(midIndex)) / 2);
            }
            else // odd
            {
                double element = (double)listSize / 2;
                element = Math.Round(element, MidpointRounding.AwayFromZero);

                result = orderedList.ElementAt((int)(element - 1));
            }

            return result;
        } 
    }


    public static class RandomProvider
    {
        private static int seed = Environment.TickCount;

        private static ThreadLocal<Random> randomWrapper = new ThreadLocal<Random>(() =>
            new Random(Interlocked.Increment(ref seed))
            );

        public static Random GetThreadRandom()
        {
            return randomWrapper.Value;
        }
    }

    public class CrockfordBase32Encoding
    {
        const int Base = 32;
        const int CheckDigitBase = 37;

        static readonly IDictionary<int, char> valueEncodings;
        static readonly IDictionary<int, char> checkDigitEncodings;
        static readonly IDictionary<char, int> valueDecodings;
        static readonly IDictionary<char, int> checkDigitDecodings;
        static CrockfordBase32Encoding()
        {
            var symbols = new SymbolDefinitions();
            valueEncodings = symbols.ValueEncodings;
            checkDigitEncodings = symbols.CheckDigitEncodings;
            valueDecodings = symbols.ValueDecodings;
            checkDigitDecodings = symbols.CheckDigitDecodings;
        }

        public string Encode(ulong input, bool includeCheckDigit)
        {
            var chunks = SplitInto5BitChunks(input);
            var characters = chunks.Select(chunk => valueEncodings[chunk]);

            if (includeCheckDigit)
            {
                var checkValue = (int)(input % CheckDigitBase);
                characters = characters.Concat(new[] { checkDigitEncodings[checkValue] });
            }

            return new string(characters.ToArray());
        }

        internal static IEnumerable<byte> SplitInto5BitChunks(ulong input)
        {
            const int bitsPerChunk = 5;
            const int shift = (sizeof(ulong) * 8) - bitsPerChunk;
            var chunks = new List<byte>();
            do
            {
                var lastChunk = input << shift >> shift;
                chunks.Insert(0, (byte)lastChunk);
                input = input >> bitsPerChunk;
            } while (input > 0);
            return chunks;
        }

        public ulong? Decode(string encodedString, bool treatLastCharacterAsCheckDigit)
        {
            if (encodedString == null)
                throw new ArgumentNullException("encodedString");

            if (encodedString.Length == 0)
                return null;

            IEnumerable<char> charactersInReverse = encodedString.Reverse().ToArray();

            int? expectedCheckValue = null;
            if (treatLastCharacterAsCheckDigit)
            {
                var checkDigit = charactersInReverse.First();
                if (!checkDigitDecodings.ContainsKey(checkDigit)) return null;
                expectedCheckValue = checkDigitDecodings[checkDigit];

                charactersInReverse = charactersInReverse.Skip(1);
            }

            ulong number = 0;
            ulong currentBase = 1;
            foreach (var character in charactersInReverse)
            {
                if (!valueDecodings.ContainsKey(character)) return null;

                var value = valueDecodings[character];
                number += (ulong)value * currentBase;

                currentBase *= Base;
            }

            if (expectedCheckValue.HasValue &&
                (int)(number % CheckDigitBase) != expectedCheckValue)
                return null;

            return number;
        }
    }

    internal class SymbolDefinitions : List<SymbolDefinition>
    {
        readonly List<SymbolDefinition> extraCheckDigits = new List<SymbolDefinition>();

        public SymbolDefinitions()
        {
            AddRange(new[]
            {
                new SymbolDefinition { Value = 0, EncodeSymbol = ''0'', DecodeSymbols = new[] { ''0'', ''O'', ''o'' } },
                new SymbolDefinition { Value = 1, EncodeSymbol = ''1'', DecodeSymbols = new[] { ''1'', ''I'', ''i'', ''L'', ''l'' } },
                new SymbolDefinition { Value = 2, EncodeSymbol = ''2'', DecodeSymbols = new[] { ''2'' } },
                new SymbolDefinition { Value = 3, EncodeSymbol = ''3'', DecodeSymbols = new[] { ''3'' } },
                new SymbolDefinition { Value = 4, EncodeSymbol = ''4'', DecodeSymbols = new[] { ''4'' } },
                new SymbolDefinition { Value = 5, EncodeSymbol = ''5'', DecodeSymbols = new[] { ''5'' } },
                new SymbolDefinition { Value = 6, EncodeSymbol = ''6'', DecodeSymbols = new[] { ''6'' } },
                new SymbolDefinition { Value = 7, EncodeSymbol = ''7'', DecodeSymbols = new[] { ''7'' } },
                new SymbolDefinition { Value = 8, EncodeSymbol = ''8'', DecodeSymbols = new[] { ''8'' } },
                new SymbolDefinition { Value = 9, EncodeSymbol = ''9'', DecodeSymbols = new[] { ''9'' } },
                new SymbolDefinition { Value = 10, EncodeSymbol = ''A'', DecodeSymbols = new[] { ''A'', ''a'' } },
                new SymbolDefinition { Value = 11, EncodeSymbol = ''B'', DecodeSymbols = new[] { ''B'', ''b'' } },
                new SymbolDefinition { Value = 12, EncodeSymbol = ''C'', DecodeSymbols = new[] { ''C'', ''c'' } },
                new SymbolDefinition { Value = 13, EncodeSymbol = ''D'', DecodeSymbols = new[] { ''D'', ''d'' } },
                new SymbolDefinition { Value = 14, EncodeSymbol = ''E'', DecodeSymbols = new[] { ''E'', ''e'' } },
                new SymbolDefinition { Value = 15, EncodeSymbol = ''F'', DecodeSymbols = new[] { ''F'', ''f'' } },
                new SymbolDefinition { Value = 16, EncodeSymbol = ''G'', DecodeSymbols = new[] { ''G'', ''g'' } },
                new SymbolDefinition { Value = 17, EncodeSymbol = ''H'', DecodeSymbols = new[] { ''H'', ''h'' } },
                new SymbolDefinition { Value = 18, EncodeSymbol = ''J'', DecodeSymbols = new[] { ''J'', ''j'' } },
                new SymbolDefinition { Value = 19, EncodeSymbol = ''K'', DecodeSymbols = new[] { ''K'', ''k'' } },
                new SymbolDefinition { Value = 20, EncodeSymbol = ''M'', DecodeSymbols = new[] { ''M'', ''m'' } },
                new SymbolDefinition { Value = 21, EncodeSymbol = ''N'', DecodeSymbols = new[] { ''N'', ''n'' } },
                new SymbolDefinition { Value = 22, EncodeSymbol = ''P'', DecodeSymbols = new[] { ''P'', ''p'' } },
                new SymbolDefinition { Value = 23, EncodeSymbol = ''Q'', DecodeSymbols = new[] { ''Q'', ''q'' } },
                new SymbolDefinition { Value = 24, EncodeSymbol = ''R'', DecodeSymbols = new[] { ''R'', ''r'' } },
                new SymbolDefinition { Value = 25, EncodeSymbol = ''S'', DecodeSymbols = new[] { ''S'', ''s'' } },
                new SymbolDefinition { Value = 26, EncodeSymbol = ''T'', DecodeSymbols = new[] { ''T'', ''t'' } },
                new SymbolDefinition { Value = 27, EncodeSymbol = ''V'', DecodeSymbols = new[] { ''V'', ''v'' } },
                new SymbolDefinition { Value = 28, EncodeSymbol = ''W'', DecodeSymbols = new[] { ''W'', ''w'' } },
                new SymbolDefinition { Value = 29, EncodeSymbol = ''X'', DecodeSymbols = new[] { ''X'', ''x'' } },
                new SymbolDefinition { Value = 30, EncodeSymbol = ''Y'', DecodeSymbols = new[] { ''Y'', ''y'' } },
                new SymbolDefinition { Value = 31, EncodeSymbol = ''Z'', DecodeSymbols = new[] { ''Z'', ''z'' } },
            });

            extraCheckDigits.AddRange(new[]
            {
                new SymbolDefinition { Value = 32, EncodeSymbol = ''*'', DecodeSymbols = new[] { ''*'' } },
                new SymbolDefinition { Value = 33, EncodeSymbol = ''~'', DecodeSymbols = new[] { ''~'' } },
                new SymbolDefinition { Value = 34, EncodeSymbol = ''$'', DecodeSymbols = new[] { ''$'' } },
                new SymbolDefinition { Value = 35, EncodeSymbol = ''='', DecodeSymbols = new[] { ''='' } },
                new SymbolDefinition { Value = 36, EncodeSymbol = ''U'', DecodeSymbols = new[] { ''U'', ''u'' } },
            });
        }

        public IDictionary<int, char> ValueEncodings
        {
            get
            {
                return this.ToDictionary(s => s.Value, s => s.EncodeSymbol);
            }
        }

        public IDictionary<int, char> CheckDigitEncodings
        {
            get
            {
                return this
                    .Union(extraCheckDigits)
                    .ToDictionary(s => s.Value, s => s.EncodeSymbol);
            }
        }

        public IDictionary<char, int> ValueDecodings
        {
            get
            {
                return this
                    .SelectMany(s => s.DecodeSymbols.Select(d => new { s.Value, DecodeSymbol = d }))
                    .ToDictionary(s => s.DecodeSymbol, s => s.Value);
            }
        }

        public IDictionary<char, int> CheckDigitDecodings
        {
            get
            {
                return this
                    .Union(extraCheckDigits)
                    .SelectMany(s => s.DecodeSymbols.Select(d => new { s.Value, DecodeSymbol = d }))
                    .ToDictionary(s => s.DecodeSymbol, s => s.Value);
            }
        }
    }

    internal class SymbolDefinition
    {
        public int Value { get; set; }
        public IEnumerable<char> DecodeSymbols { get; set; }
        public char EncodeSymbol { get; set; }
    }
}

He agregado un par de líneas de salida adicionales:

Average Number Before Duplicate: 41043.954
Minimum Number Before Duplicate: 2498
Maximum Number Before Duplicate: 127683
 Median Number Before Duplicate: 37860

No es tan interesante, mientras que el promedio es de aproximadamente 40 k, mire el mínimo y el máximo, dos órdenes de magnitud aparte.

La aleatoriedad no garantiza una distribución uniforme. En dos tiradas consecutivas de un dado, obtener el número 4 en ambos lanzamientos sigue siendo aleatorio. Ganar el gran premio de la lotería dos veces o más en una vida se ha hecho antes.

Si necesita una distribución más única por hilo, he incluido una muestra de RandomProvider del libro más excelente de Jon Skeet (sí, soy un fanático).

ACTUALIZAR

Una pequeña reescritura para la ejecución paralela, porque es divertido torturar las formas de vida basadas en silicio:

    static void Main(string[] args)
    {

        ConcurrentDictionary<int, int> resultDictionary = new ConcurrentDictionary<int, int>();
        Parallel.For(0, 1000, x =>
        {
            var r = RandomProvider.GetThreadRandom();
            ConcurrentDictionary<string, int> dictionary = new ConcurrentDictionary<string, int>();
                while (true)
                {
                    int rand = r.Next(0, 1073741823);
                    CrockfordBase32Encoding encoding = new CrockfordBase32Encoding();
                    string encodedRand = encoding.Encode((ulong) rand, false);
                    if (!dictionary.TryAdd(encodedRand, rand)) break;
                }
            Console.WriteLine("{0} - {1}", x, dictionary.Count);
            resultDictionary.TryAdd(x, dictionary.Count);
        });

        Console.WriteLine();
        Console.WriteLine("Average Number Before Duplicate: " + resultDictionary.Average(x => x.Value));
        Console.WriteLine("Minimum Number Before Duplicate: " + resultDictionary.Min(x => x.Value));
        Console.WriteLine("Maximum Number Before Duplicate: " + resultDictionary.Max(x => x.Value));
        Console.WriteLine(" Median Number Before Duplicate: " + resultDictionary.Select(x=>x.Value).Median());
        Console.ReadLine();
    }

y los resultados:

Average Number Before Duplicate: 41826.375
Minimum Number Before Duplicate: 1655
Maximum Number Before Duplicate: 134671
 Median Number Before Duplicate: 39119

ACTUALIZACIÓN 2

Entonces, el autor del artículo de CodeProject publicó su trabajo como un paquete NuGet:

Install-Package Troschuetz.Random

He usado el mismo código de muestra para probar diferentes generadores:

StandardGenerator

Average Number Before Duplicate: 40434.148
Minimum Number Before Duplicate: 978
Maximum Number Before Duplicate: 136248
 Median Number Before Duplicate: 38845

ALFGenerator

Average Number Before Duplicate: 40395.845
Minimum Number Before Duplicate: 828
Maximum Number Before Duplicate: 125705
 Median Number Before Duplicate: 38042

MT19937Generator

Average Number Before Duplicate: 40478.174
Minimum Number Before Duplicate: 2723
Maximum Number Before Duplicate: 121367
 Median Number Before Duplicate: 38279

XorShift128Generator

Average Number Before Duplicate: 41463.732
Minimum Number Before Duplicate: 878
Maximum Number Before Duplicate: 111206
 Median Number Before Duplicate: 39013.5

Entonces, ahí lo tienes. Disfruta por lo que vale la pena ...

Answer 2

Esto es similar al en.wikipedia.org/wiki/Birthday_problem . Dado un grupo de n personas, ¿cuál es la probabilidad de que dos compartan el mismo cumpleaños ¹ ? Es más alto de lo que piensas

En su caso, ¿cuáles son las probabilidades de que elegir aleatoriamente un número entre 0 y 1,073,741,823 n veces le dé un duplicado?

Una aproximación del enlace de arriba es 1-exp(-(n*n)/(2*d)) . Si n=40,000 eso equivale a aproximadamente un 52.5% de probabilidad de que se elija un duplicado, entonces ver duplicados después de 40,000 selecciones en promedio parece razonable.

¹ suponiendo que los cumpleaños se distribuyan de manera uniforme universalmente, lo que no es el caso en realidad, pero es "lo suficientemente cerca" y hace que las matemáticas sean más fáciles

Answer 3

Esto se conoce como el en.wikipedia.org/wiki/Birthday_problem del en.wikipedia.org/wiki/Birthday_problem y es solo una teoría de probabilidad básica.

La probabilidad de que N números aleatorios en el rango de 1 a K no dé un duplicado es:

Para calcular la posibilidad de obtener al menos un duplicado, reste el valor de 1.

En tu caso, se evalúa

P(40000, 1073741823) = 1 - p(40000, 1073741823)

Al usar Wolfram Alpha para hacer el cálculo, el resultado es

0.5252888122305790

lo que significa que es un poco más del 50% de probabilidad de obtener un duplicado. A medida que produzca más números, obtendrá duplicados más y más a menudo.

Aquí hay algunas evaluaciones más de N:

   N      Result
 40000    0.5253
100000    0.9905
200000    0.9999