¿Por qué es imposible producir números verdaderamente aleatorios?

Estaba tratando de resolver un problema de pasatiempo que requería generar un millón de números aleatorios. Pero rápidamente me di cuenta de que cada vez es más difícil hacerlos únicos. Cogí Algoritmo Manual de diseño para leer acerca de la generación de números aleatorios.

Tiene el siguiente párrafo que no puedo entender completamente.

Desafortunadamente, generar números aleatorios parece mucho más fácil de lo que realmente es. De hecho, es fundamentalmente imposible producir números verdaderamente aleatorios en cualquier dispositivo determinista. Von Neumann [Neu63] lo dijo mejor: "Cualquiera que considere métodos aritméticos para producir dígitos aleatorios está, por supuesto, en un estado de pecado". Lo mejor que podemos esperar son los números pseudoaleatorios, un flujo de números que aparecen como si fueron generados al azar.

¿Por qué es imposible producir números verdaderamente aleatorios en cualquier dispositivo determinista? ¿Qué significa esta oración?

Se debe buscar un generador de números pseudoaleatorio criptográficamente seguro . La mayoría de los PRNG son generadores de congruencia lineal (por lo que next numberes una función lineal de previous number), por lo que si traza next numbervs previous numberobtendrá un gráfico de líneas paralelas. Un CSPRNG no hará eso. La compensación es que son lentos.

Agrupo los generadores de números aleatorios en 3 categorías :

1. Lo suficientemente bueno para la tarea.
2. Lo suficientemente bueno como para apostar a su empresa.
3. Lo suficientemente bueno como para apostar a tu país.

¿Por qué es imposible producir números verdaderamente aleatorios en cualquier dispositivo determinista?

Un dispositivo determinista siempre producirá la misma salida cuando se le den las mismas condiciones y entradas iniciales, eso es lo que significa ser deterministic. El "número verdaderamente aleatorio" es más un punto de vista filosófico, ya que lo que significa ser randomes el quid de la mirada filosófica del ombligo (la gente ni siquiera está segura de si la desintegración atómica es aleatoria o sigue algún patrón que simplemente no podemos entender) todavía). Un generador de números aleatorios criptográficamente seguro tomará alguna fuente externa de entropía para que el dispositivo no sea determinista.

La verdadera aleatoriedad implica no determinismo. Si es determinista, se puede predecir con precisión (esto es lo que significa determinismo); si puede predecirse, no es aleatorio.

Lo mejor que puede obtener de un generador de números pseudoaleatorio determinista es un flujo de números que tiene un ciclo muy largo (no es posible repetirlo a menos que su dispositivo RNG tenga almacenamiento ilimitado) que, durante la duración del ciclo, produce un números de flujo que cumplan con todas las otras propiedades de una secuencia aleatoria (una distribución uniforme de valores es la más interesante).

Para resolver este problema, muchos UNIX modernos y Me gusta de Unix tienen RNG de kernel que utilizan fuentes de ruido físico para generar una aleatoriedad real.

Otro enfoque común es tomar el tiempo actual como semilla para un RNG determinista ( srand(time(NULL));en C); criptográficamente hablando, esto no tiene valor, ya que el tiempo actual no es un secreto, pero para cosas como simulaciones físicas o videojuegos, es lo suficientemente bueno.

El segundo capítulo del libro Simulación de eventos discretos: un primer curso de Lawrence Leemis ofrece una fantástica introducción a los generadores de números aleatorios (o más exactamente, los generadores de números psuedo-aleatorios).

Un extracto de su libro lo explica bien en mi opinión:

Históricamente, se han recomendado tres tipos de generadores de números aleatorios para aplicaciones computacionales: (a) generadores de búsqueda de tablas estilo 1950 como, por ejemplo, la tabla de corporaciones RAND de un millón de dígitos aleatorios; (b) generadores de hardware como, por ejemplo, dispositivos térmicos de "ruido blanco"; y (c) generadores algorítmicos (software). De estos tres tipos, solo los generadores algorítmicos han logrado una aceptación generalizada. La razón de esto es que solo los generadores algorítmicos tienen el potencial de satisfacer todos los siguientes criterios de generación de números aleatorios generalmente aceptados. Un generador debe ser:

• aleatorio: capaz de producir resultados que pasan todas las pruebas estadísticas razonables de aleatoriedad;
• controlable: capaz de reproducir su salida, si lo desea;
• portátil: capaz de producir la misma salida en una amplia variedad de sistemas informáticos;
• eficiente: rápido, con requisitos mínimos de recursos informáticos;
• documentado - teóricamente analizado y ampliamente probado.

Entonces, si bien podría ser posible usar un generador de ruido blanco para obtener "mejores" números aleatorios, no han ganado aceptación porque no siguen la mayoría de los criterios anteriores.

Le recomendaría que tenga en sus manos una copia de ese libro (o algo similar). Comprender exactamente cómo el trabajo de PRNG definitivamente lo ayudará en sus esfuerzos.

Porque necesita escribir código para generar los números aleatorios y el código NO es aleatorio. (Es determinista)

Entonces terminas comenzando con un "Valor (es) de semilla" que se selecciona en "Aleatorio" (generalmente la marca de tiempo actual) y luego lo usas en un algoritmo para comenzar a generar números. ¡Pero todo el conjunto se basa en el valor original de Seed!

Entonces, si ejecuta su código nuevamente con los mismos valores de Semilla, ¡obtendrá el mismo CONJUNTO de números EXACTAMENTE! ¿Cómo puede una persona razonable llamar a eso al azar? Pero seguro que hace MIRADA azar.

Con respecto a hacerlos únicos, después de generar un número, simplemente verifique si ya tiene ese número, si lo tiene, deséchelo y genere uno nuevo.

Como está generando números aleatorios, debe esperar que los valores generados no sean únicos. Esta es una propiedad de aleatoriedad: no se puede decir que una secuencia de números verdaderamente aleatorios (o incluso pseudoaleatorios) es única, porque ese requisito permitiría predecir el valor final en el rango, así como cambiar la probabilidad de todos los números no elegidos cada vez que se selecciona uno nuevo.

Tengo una definición muy simple de Pseudo Random :

Demasiadas variables desconocidas para predecir.

También tengo una definición simple de True Random :

Infinitas variables desconocidas.

El problema con una computadora es que siempre conoce TODAS las variables. El número aleatorio es simplemente una función matemática de algún valor semilla .
Lo mejor que podemos hacer es darle a la computadora un valor semilla pseudoaleatorio, que generalmente se basa en una variable que no podemos predecir (como el tiempo exacto).

A pesar de que una computadora es absolutamente incapaz de crear un número aleatorio, ¡es bueno para introducir demasiadas variables para predecir!

De hecho, no es posible generar números verdaderamente aleatorios en el software , como han señalado otros, sin embargo, es posible con el hardware construir un dispositivo que pueda generar números verdaderamente aleatorios *. Hay bastantes ejemplos de esto en Internet, y hay una variedad de métodos utilizados, desde leer el tiempo entre ticks en el contador Geiger hasta muestrear el ruido blanco (principalmente radiación de fondo del universo) de un receptor no sintonizado. Yo mismo he construido algunos utilizando algunos de los métodos disponibles.

* Cualquier buen experto en física señalará que, dada la forma en que funciona el universo, ninguno de estos es hiper-técnicamente verdaderamente aleatorio, pero no hay una forma razonable de predecir los resultados, por lo que en aras de esta discusión son suficientes.

No hay forma de que pueda producir un número aleatorio sin un hardware especial. En mi primer año, un par de compañeros de clase y yo propusimos un generador de números aleatorios que tiene básicamente un receptor AM y sintonizado en 4 canales diferentes, obtener la entrada en un convertidor A a D y agregarlos todos (módulo su número máximo). Dado que la combinación de entrada analógica de cualquier número arbitrario de estaciones es aleatoria y podríamos producir una gran cantidad de números aleatorios del convertidor A2D, propusimos que este podría ser un buen generador. Por supuesto, incluso esto no es realmente aleatorio en un sentido filosófico, aunque para la mayoría de los propósitos prácticos esto podría funcionar.

El determinismo es esencialmente una función. Recuerde de Álgebra que una función es una correspondencia entre un dominio y un rango de tal manera que cada miembro del dominio corresponde exactamente a un miembro del rango.

Entonces, si f (x) = z, f (x)! = Y a menos que y sea z. Esa es una función. Imagina JavaScript:

function Add(A, B) {
      return A + B;
}

var addedNumber = Add(2,3);//returns 5
addedNumber = Add(2,3);//still 5

No importa cuántas veces lo llame Add(2,3), siempre devolverá 5. En otras palabras, Add () es una función determinista.

Los factores externos pueden hacer que Add se comporte de una manera no determinista. Por ejemplo, si introduce múltiples subprocesos en la ecuación. El aporte humano también causa no determinismo.

Ahora, aquí es donde las cosas se ponen interesantes.

"Cualquiera que considere métodos aritméticos para producir dígitos aleatorios está, por supuesto, en un estado de pecado".

Nota: Von Neumann afirma, "métodos aritméticos de producción [...]". Esto no se refiere a la entrada humana, la concurrencia, la velocidad del viento de muestra leída de un instrumento preciso u otras formas no algorítmicas de producir una entrada aleatoria a una función determinista.

Esto simplemente establece que una función o sistema de funciones no se volverá repentinamente no determinista. En otras palabras, Agregar (2,3) de alguna manera no devolverá 6 o cualquier otra cosa que no sea 5 dadas las mismas entradas . Eso es imposible.

El autor citando va un paso más allá.

Lo mejor que podemos esperar son los números pseudoaleatorios, un flujo de números que aparecen como si fueran generados aleatoriamente.

El contexto se definió previamente como "en cualquier dispositivo determinista". Podría terminar la discusión aquí. Pero, ¿qué pasa si cambiamos el contexto introduciendo un nuevo elemento en el sistema? Un elemento no determinista agregado como entrada hace que el sistema sea un sistema no determinista. Aunque, al eliminar el elemento no determinista, nos vemos reducidos a un sistema determinista. Si de alguna manera podemos rastrear o reproducir las entradas, podemos reproducir un resultado. Pero todo este párrafo es tangencial a lo que dice el autor. Recuerda el contexto.

Se podría discutir sobre el significado del no determinismo. Una vez más, tangencial. Recuerda el contexto.

Entonces él está en lo correcto. En cualquier dispositivo determinista es imposible que un sistema determinista produzca un verdadero resultado aleatorio.