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

47

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?

Vinoth Kumar CM
fuente
86
¿ Realmente te preguntas por qué no puedes producir un número verdaderamente aleatorio en un dispositivo determinista ? ¿La pregunta ya no incluye la respuesta?
herby
37
Si todos los números que genera tienen que ser únicos, no son realmente aleatorios. Es completamente posible que un verdadero generador de números aleatorios dé el mismo resultado diez veces seguidas.
TMN
28
Hay una falla en la búsqueda de números aleatorios que son únicos . Si está restringiendo los números para que sean únicos , entonces no son aleatorios ya que el azar exige la posibilidad de repetición, sin importar cuán improbable sea.
Mark Booth
13
Fuera de la computadora, ¿algún número aleatorio es realmente aleatorio? Lanza un dado, es física con solo muchos vectores.
MPelletier
99
@MPelletier: No del todo. La mecánica cuántica podría (una vez que los científicos hayan descubierto más de esto) implicar la existencia de una aleatoriedad verdadera, dependiendo de su definición de aleatoriedad.
Brian

Respuestas:

65

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.

Tangurena
fuente
1
Por eso es imposible obtener un número verdaderamente aleatorio. Incluso si la secuencia nunca se repite, que no está garantizado por azar los números, Otra ejecución del programa con las mismas entradas se producen los mismos resultados. Entonces, alguien más puede reproducir sus números aleatorios en un momento posterior, lo que significa que no fue realmente aleatorio en absoluto.
Spencer Rathbun
2
@ user973810 El problema con esa definición de la teoría de la información es que no puede exhibir una instancia real de una secuencia aleatoria. Podemos probar, para cualquier lenguaje de definición razonable, que casi todas las secuencias infinitas (en un sentido técnico) son aleatorias, porque no pueden describirse en absoluto en el lenguaje. Lo que es más útil es el concepto de un generador de secuencias aleatorias: no uno que produce una secuencia aleatoria, sino uno que produce una secuencia al azar.
Gilles 'SO- deja de ser malo'
13
Un pequeño inconveniente: algunas personas, a saber, los físicos nucleares y de partículas, están bastante seguros de que procesos como la desintegración atómica son verdaderamente aleatorios.
David Z
99
@David: Incluso podemos ir un poco más allá. Los diversos experimentos sobre la desigualdad de Bell muestran que ciertos procesos cuánticos son definitivamente impredecibles . Pueden ser aleatorios en algún sentido filosófico o pueden depender de variables ocultas no locales, pero cualquier caso impide una predicción confiable.
dmckee
77
@dmckee: sí, pensé que sería más fácil evitar tratar de explicar la conexión entre la desigualdad de Bell y el colapso de la función de onda en los comentarios sobre prog.SE. Las personas siempre pueden visitar nuestro sitio si tienen curiosidad ;-) Tangurena: cierto, Einstein dijo eso, pero eso solo significaba que realmente quería que el universo fuera determinista. Sin embargo, no lo es. Los experimentos realizados después de la muerte de Einstein mostraron eso de manera bastante concluyente (salvo variables ocultas no locales, también conocidas como rarezas ). El hecho de que sea Einstein no significa que tuviera razón en todo.
David Z
22

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.

tdammers
fuente
Tenga en cuenta que la no repetición también es imposible para cualquier generador con valor de salida limitado (número limitado de bits). Pero, por supuesto, la duración del ciclo de un generador determinista es muy probablemente más corta que el máximo teórico, que es todas las permutaciones posibles.
9000
@ 9000: Por supuesto, esto no es cierto. Tome un número irracional de usar los dígitos (cualquier base) como su secuencia "aleatoria". ¡Auge! secuencia no repetitiva (por definición) y aún limitada (a su base).
ThePopMachine
@ThePopMachine: puede generar una secuencia no repetitiva de bits de cualquier longitud, equivalente a una secuencia no repetitiva de números de longitud ilimitada. No puede generar una secuencia no repetida de números enteros de magnitud limitada (por ejemplo, 32 bits); una vez que haya generado todas las permutaciones de valores de 32 bits, se debe repetir una secuencia. Tienes razón; solo estamos hablando de cosas diferentes.
9000
@ 9000: sin comadrejas. Hiciste una declaración general que es falsa. Si realmente está tratando de que no haya más de n ^ k secuencias diferentes de longitud k para n valores diferentes, y por lo tanto debe repetirse, entonces esto es bastante obvio y no interesante.
ThePopMachine
2
@ThePopMachine: Te agradecería si te atenuaras un poco. Para citar, «la no repetición también es imposible para cualquier generador con valor de salida limitado (número limitado de bits)». De lo que habla explícitamente es de un número ilimitado de bits, como una secuencia de dígitos [binarios] de un número irracional. Su afirmación, si bien es cierta, no está relacionada con el problema.
9000
10

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.

Riwalk
fuente
7

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.

Imbéciles
fuente
13
En el lado positivo, los números pseudoaleatorios repetibles pueden ser excelentes para la depuración.
David Thornley
5

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.

James McLeod
fuente
1
Esto es realmente un comentario en lugar de una respuesta, ya que en realidad no responde la pregunta .
Mark Booth
5

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!

Scott Rippey
fuente
1
Bueno, el "tiempo" es un mal ejemplo de algo que no se puede predecir. El movimiento del mouse, la entrada del micrófono, etc., por otro lado, son entradas que no son predecibles.
HoLyVieR
3

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.

Unkwntech
fuente
55
Como geek de la física a tiempo parcial, los generadores basados ​​en eventos cuánticos son (hasta donde hemos podido decir) verdaderamente aleatorios. Las personas a las que no les gusta la aleatoriedad han estado tratando de eliminar la aleatoriedad de la mecánica cuántica desde que comenzó, y todo lo que se hace es acumular más evidencia de que es realmente aleatoria.
David Thornley
@DavidThornley, ... hasta que alguien descubra la fórmula.
CaffGeek
1
@Chad: No existe una fórmula en el sentido habitual; eso fue descartado por los experimentos EPR. Ciertamente es concebible que todo sea determinista, pero no de una manera fácilmente comprensible.
David Thornley
@DavidThornley, sabía que esa era la palabra incorrecta para usar. Creo que sabemos lo que estaba tratando de decir. Casi siempre que alguien dice que algo es imposible, otra persona finalmente demuestra que está equivocado. Es la naturaleza humana.
CaffGeek
2
Es como decir que eventualmente alguien va a hacer una máquina que pueda resolver el problema de detención porque alguien dijo que era imposible. No se trata de encontrar la ecuación, en realidad es aleatoria de acuerdo con todos los experimentos que se han ejecutado y las matemáticas que la respaldan.
Alex
2

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.

Balaji Viswanathan
fuente
2

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.

P.Brian.Mackey
fuente