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

47

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

Tiene el siguiente párrafo que no puedo entender.

  

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 al azar está, por supuesto, en un estado de pecado". Lo mejor que podemos esperar son los números pseudoaleatorios, una serie 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?

    
pregunta Vinoth Kumar C M 09.12.2011 - 16:54

9 respuestas

65

Uno debe buscar un generador de números pseudoaleatorios criptográficamente seguro . La mayoría de los PRNG son generadores de congruencia lineal (por lo tanto, next number es una función lineal de previous number ), por lo tanto, si traza next number vs previous number obtendrá 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 al azar en 3 categorías :

  1. Suficientemente bueno para la tarea.
  2. Lo suficientemente bueno como para apostar en tu compañía.
  3. Lo suficientemente bueno como para apostar en 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 de inicio y entradas, eso es lo que significa ser deterministic . "Verdaderamente un número aleatorio" es más un punto de vista filosófico, ya que lo que significa ser random es 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 un patrón que simplemente podemos " t averiguar todavía. Un generador de números aleatorios criptográficamente seguro tomará alguna fuente externa de entropía para hacer que el dispositivo no sea determinista.

    
respondido por el Tangurena 09.12.2011 - 17:09
22

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

Lo mejor que puede obtener de un generador determinista de números pseudoaleatorios es un flujo de números que tiene un ciclo muy largo (la repetición es imposible a menos que su dispositivo RNG tenga almacenamiento ilimitado) que, durante la duración del ciclo , produce un número de flujo que cumple con todas las demás 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 kernel RNG que usan fuentes de ruido físico para generar una verdadera aleatoriedad.

Otro enfoque común es tomar la hora actual como semilla para un RNG determinista ( srand(time(NULL)); en C); Hablando criptográficamente, esto no vale nada, ya que la hora actual no es un secreto, pero para cosas como simulaciones físicas o videojuegos, es lo suficientemente buena.

    
respondido por el tdammers 09.12.2011 - 17:29
10

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

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

  

Históricamente, tres tipos de generadores de números aleatorios han sido   abogó por aplicaciones computacionales: (a) Mesa estilo años 50   generadores de búsqueda como, por ejemplo, la tabla de corporaciones RAND de un   millones de dígitos aleatorios; (b) generadores de hardware como, por ejemplo,   dispositivos térmicos de "ruido blanco"; y (c) algorítmica (software)   generadores De estos tres tipos, solo los generadores algorítmicos tienen   Alcanzado aceptación generalizada La razón de esto es que solo   Los generadores algorítmicos tienen el potencial de satisfacer todos los   Siguiendo los criterios de generación de números aleatorios generalmente bien aceptados. UNA   El generador debe ser:

     
  • aleatorio - capaz de producir resultados que pasan todas las pruebas estadísticas razonables de aleatoriedad;
  •   
  • controlable: puede reproducir su salida, si se 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 probado exhaustivamente.
  •   

Entonces, aunque 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 consiga una copia de ese libro (o algo similar). Comprender exactamente cómo el trabajo de PRNG definitivamente lo ayudará en sus esfuerzos.

    
respondido por el riwalk 09.12.2011 - 17:15
7

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

Así que terminas comenzando con un "valor (es) de semillas" 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 de se basa en el valor original de la semilla!

Por lo tanto, si ejecuta su código nuevamente con exactamente el mismo valor de Seed, ¡obtendrá el mismo CONJUNTO DE NÚMEROS EXACTOS! ¿Cómo puede una persona razonablemente llamar al azar? Pero seguro que MIRA al azar.

Respecto a hacerlos únicos, después de generar un número, simplemente verifica si ya tienes ese número, si es así, tíralo y genera uno nuevo.

    
respondido por el Morons 09.12.2011 - 17:02
5

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

    
respondido por el James McLeod 09.12.2011 - 17:09
5

Tengo una definición muy simple de pseudoaleatoriedad :

Hay 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 dar a la computadora un valor semilla pseudoaleatorio, que generalmente se basa en una variable que no podemos predecir (como la hora exacta).

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

    
respondido por el Scott Rippey 10.12.2011 - 01:15
3

La generación de números verdaderamente aleatorios en el software no es posible, como han señalado otros, sin embargo, es posible con el hardware construir un dispositivo que pueda generar números verdaderamente aleatorios *. Existen bastantes ejemplos de esto en Internet, y se utilizan diversos métodos, desde la lectura del tiempo entre los tics en el contador Geiger hasta el muestreo del ruido blanco (principalmente radiación de fondo del universo) de un receptor sin sintonizar. Yo mismo he creado algunos utilizando un Algunos de los métodos disponibles.

* Cualquier buen geek de la física señalará que, dado el modo en que funciona el universo, ninguno de ellos es hiperactivo y realmente aleatorio, pero no hay una forma razonable para predecir el resultados, por el bien de esta discusión son suficientes.

    
respondido por el Unkwntech 09.12.2011 - 21:54
2

No hay forma de que puedas 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 de AM y sintonizado a 4 canales diferentes, obtengo la entrada en un convertidor de A a D y los agregue todos (modulo 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 un gran número de números aleatorios desde el convertidor A2D, propusimos que este podría ser un buen generador. Por supuesto, incluso esto no es verdaderamente aleatorio en un sentido filosófico, aunque para la mayoría de los propósitos prácticos esto podría funcionar.

    
respondido por el Balaji Viswanathan 10.12.2011 - 07:45
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 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 llame a 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 multihilo en la ecuación. El aporte humano también causa el no determinismo.

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

  

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

La nota Von Neumann afirma, "métodos aritméticos de producción [...]". Esto no se refiere a la entrada humana, la concurrencia, las velocidades de viento de muestra leídas desde un instrumento preciso u otras formas no algorítmicas de producir entrada aleatoria a una función determinista.

Esto simplemente indica que una función o sistema de funciones no se convertirá repentinamente en no determinista. En otras palabras, Add (2,3) no devolverá de alguna manera 6 o nada más que 5 dadas las mismas entradas . Eso es imposible.

El autor de la cita va un paso más allá.

  

Lo mejor que podemos esperar son los números pseudoaleatorios, una serie de números que aparecen como si se hubieran generado de forma aleatoria.

El contexto se define previamente como "en cualquier dispositivo determinista". Podría terminar la discusión aquí. Pero, ¿qué pasa si cambiamos el contexto al introducir 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 reducimos 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.

Uno podría discutir sobre el significado del no-determinismo. Una vez más, tangetenial. Recuerda el contexto.

Así que él tiene razón. En cualquier dispositivo determinista es imposible que un sistema determinista produzca un verdadero resultado aleatorio.

    
respondido por el P.Brian.Mackey 10.12.2011 - 03:47

Lea otras preguntas en las etiquetas