Algoritmo de generación de números aleatorios para cerebros humanos? [cerrado]

37

¿Conoces o has ideado algún algoritmo práctico "fácil de aprender" que permita a los humanos generar números aleatorios (algo "verdaderos")? Por "en la cabeza" quiero decir ... preferiblemente sin herramientas o dispositivos externos. Además, es deseable un alto rendimiento (muchos números aleatorios por minuto).

Le pregunté esto a SO, pero no obtuvo mucho interés. Tal vez esto sea más adecuado para programadores.

Magnus Wolffelt
fuente
77
@ S.Lott No creo que sea absurdo en absoluto. ¿Unpráctico? Por qué por supuesto. ¿Absurdo? Ciertamente no. E incluso si lo fuera, el absurdo puede allanar el camino para nuevos y útiles pensamientos.
biziclop
21
9 .... 9 .... 9 .... 9 - No puedes probar que no es aleatorio.
13
S.Lott: La idea de un generador de números pseudoaleatorio fácil de calcular no es absurda en absoluto. Creo que el OP quiere una forma de evitar el prejuicio humano aquí ...
Jens
8
Encuentro divertido (y al mismo tiempo un poco deprimente) cuántas personas parecen apreciar un argumento de ignorancia. "No puedo imaginarlo, por lo tanto, no puede existir", o respuestas que están perdiendo completamente el punto.
biziclop
44
Esta pregunta parece estar fuera de tema porque se trata de la capacidad cognitiva de un individuo y no de la programación.

Respuestas:

36

Aquí hay un algoritmo de George Marsaglia :

Elija un número de 2 dígitos, digamos 23, su "semilla".

Forme un nuevo número de 2 dígitos: el dígito de 10 más 6 veces el dígito de las unidades.

La secuencia de ejemplo es 23 -> 20 -> 02 -> 12 -> 13 -> 19 -> 55 -> 35 -> ...

y su período es el orden del multiplicador, 6, en el grupo de residuos relativamente primos al módulo, 10. (59 en este caso).

Los "dígitos aleatorios" son los dígitos de las unidades de los números de 2 dígitos, es decir, 3,0,2,2,3,9,5, ... la secuencia mod 10. La aritmética es lo suficientemente simple como para llevar a cabo en su cabeza.

Davo
fuente
Esto suena muy bien.
biziclop
44
Esto puede no ser un problema para las necesidades de una persona en particular, pero esto solo le proporciona 90 transmisiones diferentes.
Compman
55
79, 79, 79, 79, 79, 79, 79, 79, 79, 79, ¡oh no! Supongo que se supone que debes permanecer <= 60, lo que funciona bien porque puedes usar el reloj para una semilla si no tienes una.
eds
44
@eds Um, ¿qué? 79 -> 61 -> 15 -> ...
Izkata
1
Quizás @eds significaba 59. Todos los números del 1 al 58 parecen ser un juego justo.
Erhannis
26

Echa un vistazo a este artículo sobre geomancia . Específicamente la sección sobre generación de cartas geománticas . Implica una técnica de generación de números pseudoaleatorios que utiliza dígitos binarios y algunos cálculos recursivos simples. Parece que podrías hacer esto en tu cabeza con bastante facilidad (aunque un trozo de papel ayudaría).

Descargo de responsabilidad: no lo he probado yo mismo; cuando necesito un número lo suficientemente aleatorio, obtengo algún resultado /dev/random, lo uso randen cualquier idioma que tenga a mano o utilizo mi confiable d20.

Si eres un prodigio de las matemáticas, el método del cuadrado medio es un método computacionalmente ligero, aunque notablemente poco confiable.

Inaimathi
fuente
3
+1 Creo que esta es la primera respuesta seria a esta pregunta. Un poco triste.
Jens
@Magnus Wolffelt - Recordé que fue mencionado en una charla TED por Ron Eglash sobre el significado cultural de la geometría fractal en África; "Adivinación de arena de Bamana". Es bastante interesante, aunque todavía no tengo idea de por qué usarías esta técnica por ahora que ya no necesitamos adivinos. ted.com/talks/ron_eglash_on_african_fractals.html
Inaimathi
1
Hasta donde puedo ver, ese método geomántico simplemente le permite 'mejorar' (supongo que 'debias' sería un mejor término) una fuente de aleatoriedad. No se debe estornudar, pero no es realmente lo que estaba buscando el OP. Lo que no quiere decir que no sea bonito ...
Norman Gray
@ Norman Gray: los cerebros humanos pueden tener números arbitrarios sesgados de forma predeterminada.
Inaimathi
@Inaimathi Precisamente: esa es la razón por la cual debiaing números sería importante, y por qué el método que señaló es útil. O te estoy malentendiendo.
Norman Gray
10

Creo que una suposición razonable es que debe confiar en la gran cantidad de información verbal que almacena en su cerebro. La fuente puede ser cualquier cosa, letras de canciones, poemas, bocetos de Monty Python, pero tiene que ser algo que se sepa de memoria.

Luego, debe seleccionar una parte bastante aleatoria, eliminando el sesgo inconsciente tanto como sea posible. Una forma de hacer esto, por ejemplo, sería seleccionar una canción, elegir un número kentre 10 y 20 y luego encontrar la kletra th en su letra.

Obviamente, esto no le dará una distribución uniforme en sí misma, ya que la frecuencia de las letras es diferente, pero sin embargo es una letra aleatoria, o al menos tan cercana como creo que es posible sin una fuente externa.

Actualización: Por cierto, cuando se le pide a la gente que escriba una secuencia aleatoria de decir lanzamientos de monedas, el error más común es hacer que su secuencia sea "demasiado aleatoria": las series de resultados idénticos serán demasiado cortas, lo que implica una duración de ejecución simple El análisis revelará. Este método está dirigido principalmente a evitar esta trampa. Por supuesto, pueden surgir otras anomalías a la sombra de este sesgo de longitud de ejecución, pero necesitaría experimentos adecuados para encontrarlas. Irónicamente, no se puede encontrar un algoritmo para generar números aleatorios pensando solo pensando solo.

biziclop
fuente
Incluso entonces, esperaría que usted fuera parcial en varias formas sutiles. (IE tiende a elegir el mismo grupo de canciones)
Zachary K
@Zachary K Sin duda, pero también tendrías que elegir un número, que lo difunde un poco. Aunque el sesgo nunca podría eliminarse, este método casi seguramente le impide saber qué letra elegirá (aunque con el tiempo seguramente memorizará algunas).
biziclop
Eini mini miny moe, como solíamos hacer cuando éramos niños.
Zachary K
2
"elige un número k entre 10 y 20". 17. El número menos aleatorio.
S.Lott
@ S.Lott No importa cuán aleatorio sea este número. La única razón por la que lo necesita es que tiende a recordar las primeras letras de las cosas con mayor facilidad.
biziclop
9

Muestra tu reloj.

Hago esto si necesito un número aleatorio que sea un factor de 60 (segundos). Tome el módulo apropiado de la hora que sea. 4:17:23 PM, simulando una tirada de dados, se convierte en 5.

Mark Canlas
fuente
¿Y por un gran número por minuto?
Gary Rowe
No estoy seguro de seguir. ¿Estás diciendo que el grupo de números 3600 incluye minutos? Supongo, pero cuanto mayor sea el número, menos aleatorio sería. Como si no pudieras tomar muestras rápidamente tan fácilmente.
Mark Canlas
1
@Gary Rowe Me temo que este criterio debe eliminarse, simplemente porque, independientemente del método utilizado, el cerebro humano es demasiado lento.
biziclop
Lo siento, me preguntaba cómo funciona su enfoque si necesita más de 60 números por minuto. En retrospectiva, pedirle a un cerebro humano que produzca tantos números por minuto lo maximizará de todos modos, así que no se preocupe.
Gary Rowe
@biziclop Sin problemas. Parece que tuve una colisión de comentarios al considerar la situación con el enfoque de @ Mark.
Gary Rowe
5

Excelente pregunta Me temo que una buena respuesta puede resultar muy difícil.

Pero para empezar, es bastante fácil generar aleatoriedad "verdadera" cuando dos personas están involucradas: simplemente deje que una de las personas cuente en silencio en su módulo de cabeza algún número, y la otra diga "detenerse" después de un intervalo arbitrario. Posteriormente, este número puede transformarse en otras distribuciones utilizando métodos estándar.

Para hacer que este método sea robusto, el módulo no debe ser demasiado grande, de lo contrario habrá un fuerte sesgo contra los números pequeños. Realmente me interesaría ver si existe algún trabajo que analice las propiedades estocásticas de este método.

Konrad Rudolph
fuente
Creo que es importante que el conteo se haga rápido: la persona que cuenta debe tener cuidado de no contar rítmicamente, a solo 1 o 2 pasos por segundo. Porque debe haber un número significativo de ciclos (intuitivamente ≥4) a través de todos los números para lograr suficiente entropía.
Aaron Thoma
Sugerencia de mejora para una mejor aleatoriedad : la persona que cuenta elige una semilla aleatoria secreta X₀ entre 0 y el módulo primero; en combinación con el conteo, eso debería proporcionar una aleatoriedad decente con un esfuerzo de pensamiento todavía mínimo (incluso cuando se cuenta lentamente, en relación con la duración del conteo; es decir, un número bajo de ciclos; intuitivamente ≥2 estaría bien; <2 estaría bien).
Aaron Thoma
4

Esta es una pregunta compleja; Trataré de explicar un poco sin adentrarme demasiado en la maleza.

Primero, tenemos que preguntarnos "¿qué es el verdadero azar"? Tales discusiones rápidamente degeneran en aguas filosóficas, pero la esencia es esta: "¿el universo es verdaderamente aleatorio"? En otras palabras, si cuantificas el tiempo y la materia, ¿puedes calcular el siguiente estado del universo a partir del actual? En caso afirmativo, entonces el universo es determinista y no hay aleatoriedad verdadera (¿entiendes lo que quiero decir sobre "filosófico"?)

Debido a que la "aleatoriedad verdadera" es difícil de definir, a menudo nos conformamos con la "pseudoaleatoriedad". Esto generalmente se requiere cuando se generan números "aleatorios" en una computadora, por supuesto.

El generador de números pseudoaleatorio más simple sería algo así como el famoso algoritmo "9 .. 9 .. 9 .." de Dilbert. Pero intuitivamente no parece muy bueno (que por supuesto es el chiste). Los estadísticos han desarrollado una gran cantidad de pruebas para determinar si una secuencia de resultados supuestamente aleatorios son "buenos". Comience con la página de Wikipedia para "prueba de chi cuadrado" y podría pasar una tarde leyendo sobre estas pruebas.

Un algoritmo informático simple como un "generador congruencial lineal" produce números lo suficientemente buenos para una prueba de chi-cuadrado (sin embargo, aún debe "sembrar" este algoritmo a partir de algo).

El siguiente paso en "bondad" es "aleatoriedad criptográficamente fuerte", lo que significa que dada una secuencia a1, a2, ... no puede predecir el siguiente número en la secuencia con "probabilidad razonable" a menos que use muchos cálculos. Estos números a veces se denominan "computacionalmente pseudoaleatorios". Una forma común de obtener una secuencia de este tipo es a través de una "cadena hash" como esta: a1 = SHA512 (a2), a2 = SHA512 (a3), ... Dado que creemos (en base a la experiencia, no a la prueba matemática) que SHA512 es computacionalmente difícil de invertir, creemos que a2 es "imposible" de predecir dado a1.

Entonces, ahora surge la pregunta, ¿qué es lo mejor que los humanos pueden hacer bajo las reglas estipuladas en su pregunta? Los humanos son notoriamente malos para generar aleatoriedad; solía haber un sitio web en el que intentaba generar lanzamientos de monedas escribiendo "al azar" H, T, T, H, H, T, T, etc. como si estuviera lanzando una moneda (pero lo hace en tu cabeza). Después de un tiempo, el sitio web comenzaría a predecir sus lanzamientos mejor que el 50% del tiempo (usando un Modelo de Markov Oculto). Simplemente somos malos en esto.

Hay maneras de mejorar la situación utilizando varias técnicas de mezcla que probablemente sean factibles en su cabeza. E incluso hay aplicaciones con las que podría imaginarme por qué querrías esto (el preso político quiere encriptar un mensaje a aliados externos). Pero creo que esta publicación es lo suficientemente larga. :)

Fixee
fuente
1
Si bien si existe un proceso físico verdaderamente aleatorio está abierto a debate (aunque los experimentos que involucran la paradoja EPR sugieren una respuesta positiva), existe una definición teórica de una secuencia aleatoria, basada en la complejidad de Kolmogorov.
biziclop
3

La razón de la proliferación de los RNG basados ​​en herramientas es que aún no se ha desarrollado un buen algoritmo interno para la generación de números aleatorios .

Afortunadamente, los generadores portátiles de números aleatorios, que incluyen monedas para el flopping, dados (con varios números de facetas) para rodar, tarjetas para recoger y pajitas para dibujar, son relativamente fáciles de obtener a bajo costo. Además, para los tecnófilos entre nosotros, hay algunas simulaciones bastante buenas de estas herramientas disponibles para la mayoría de las plataformas móviles.

Recomiendo encarecidamente cualquiera de estos sobre cualquier alternativa de carne.

Kramii reinstala a Monica
fuente
1
Y estos dispositivos físicos realmente tienen una naturaleza impredecible, por lo que, en cierto sentido, son más aleatorios que los mejores algoritmos informáticos.
Omega Centauri
( @OmegaCentauri: ¡Naturalmente, veo lo que hiciste allí!; O) (No estoy seguro de que el juego de palabras fuera intencionado, pero me gusta. :)) )
Aaron Thoma
3

¿Altamente aleatorizado, gran cantidad por minuto y generado por humanos? No va a pasar

Los principales problemas con los que te encontrarás son

  • La gente se aburre rápidamente, por lo que los patrones ocurrirán rápidamente
  • El cerebro humano tiene una gran estructura dedicada al reconocimiento / creación de patrones, por lo que tendrás que vencer eso
  • Los números verdaderamente aleatorios contienen repeticiones que los humanos intentan evitar
  • Los humanos no son buenos con grandes cantidades

Esto llevó a muchos criptógrafos a abandonar las técnicas "internas" en favor de procesos externos que eran aleatorios porque era demasiado simple elaborar patrones basados ​​en números "internos".

Fuera de tema pero interesante

Si bien no es un mecanismo para generar números aleatorios en su cabeza, el algoritmo Solitario (como se describe en Cryptonomicon de Neal Stephenson ) demuestra lo difícil que es usar números aleatorios para fines criptográficos. Solo requiere un paquete de cartas normales para crear una salida razonablemente segura, pero el método para hacerlo es bastante complejo.

Gary Rowe
fuente
1
Creo que esto no responde la pregunta. Los 4 puntos de su respuesta solo se aplican si las personas intentaron encontrar números aleatorios sin un algoritmo. Creo que el OP es consciente de eso y esta es la razón por la que pide un algoritmo que la gente pueda hacer en sus cabezas y dar buenos resultados, es decir, no sufra los problemas mencionados en su respuesta.
FabianB
2

Tengo una curiosidad genuina sobre cualquier cosa que la gente pueda haber tenido sobre este problema.

Aléjese del escritorio y vaya a Las Vegas.

La humanidad tiene docenas de procedimientos aleatorios. Puedes verlos a todos en Las Vegas.

Tienes círculos giratorios. Tienes cubos rotos. Y has barajado las fichas. Todos funcionan maravillosamente bien.

Los cubos son quizás los más antiguos. Aparentemente, se usaron palos alargados de 4 lados en un punto. Los nudillos cúbicos simétricos de ovejas fueron populares durante milenios. Hemos estado usando ese tipo de aleatorizadores desde, probablemente, casi al mismo tiempo que desarrollamos el lenguaje.

http://itunes.apple.com/us/app/motionx-dice/id287509231?mt=8

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

--- John von Neumann

S.Lott
fuente
77
Votación negativa: no me interesan las herramientas externas para generar números aleatorios, sino algoritmos internos que pueden basarse en recuerdos o estímulos para generar números verdaderamente aleatorios.
Magnus Wolffelt
3
no puedes tirar dados en la cabeza
jk.
2
@ jk01: Correcto. Tampoco puedes hacer al azar en tu cabeza.
S.Lott
@ S.Lott - Creo que lo que quieres decir es "Un humano típico no puede generar números aleatorios consistentes en su cabeza a alta velocidad usando el método ingenuo y sin herramientas externas".
Inaimathi
1
@Inaimathi. No, estoy diciendo algo mucho más fuerte. No puedes hacer al azar en tu cabeza. Su cerebro está lleno de sesgos, por lo que necesita un algoritmo. Ningún algoritmo finito, efectivo y determinista es aleatorio. Simplemente no puedes hacerlo. Ningún algoritmo lo suficientemente simple es incluso seudoaleatorio, por lo que no puede aproximarse al azar. Los dados son pequeños, prácticos y tienen una larga, larga historia de uso.
S.Lott
1

No se me ocurre ninguno. De hecho, esperaría que cualquier cosa que se te ocurriera tuviera tantos prejuicios que sería inútil.

Si necesito números aleatorios, generalmente lanzo dados.

Zachary K
fuente
0

¿Estás pidiendo un LCM que puedas hacer en tu cabeza? Tenga en cuenta que la idea de que esto es mejor que los dados sigue siendo absurda.

Sin embargo, esto es tan aleatorio como cualquier algoritmo finito, definido y efectivo puede ser.

http://www.vias.org/simulations/simusoft_lincong.html

http://www1.i2r.a-star.edu.sg/~knandakumar/nrg/Tms/Probability/Probgenerator.htm

U_ {k + 1} = (a \ times U_k + b) mod (m + 1).

Es más fácil ver qué está haciendo esto si elegimos valores pequeños a = 5, b = 1 ym = 7. Deberías poder hacer eso en tu cabeza.

S.Lott
fuente
Me pregunto si hay una versión decentemente aleatoria de esto ( generador congruencial lineal (LCG) ), que es realmente fácil de hacer en la cabeza. a = 1 idealmente, a = 2 segundo idealmente. (Mis pensamientos hasta ahora sobre esto en el próximo comentario.)
Aaron Thoma
(( Pensé que a = 1, b prime, b inteligentemente elegido, podría ser una alternativa más factible para m más grandes, que todavía funcionaría bien. Entonces noté que probablemente no sea cierto: para b≈0 o b≈m, será atravesar los números de forma bastante secuencial, así que pensé que b≈m / 2 es la respuesta; pero luego me di cuenta de que eso también podría ser secuencial (para pequeños | b – m / 2 | / m), solo en dos posiciones alternadamente. b≈m / 3, podría ser secuencial, alternando entre 3 posiciones; para b≈m / 99 el problema ya no estaría en forma alterna, pero tomaría ~ 99 pasos para recorrer una resta de módulo. ))
Aaron Thoma