Lo fascinante de la teoría de números

Números aleatorios y teoría de números

Posted in Números by ZetaSelberg on 23 noviembre, 2013

Puedes ver esta entrada en la nueva dirección Números aleatorios y teoría de números



En una entrada anterior, había hablado acerca de un experimento en el cual buscaba determinar primos usando el azar. Uno de los experimentos, utilicé un pequeño programa en Java, por medio del cual se generaban números “aleatorios”. En dicha entrada hacía una aclaración en la cual indicaba que tales números no son del todo aleatorios, que de hecho, se llaman pseudo-aleatorios. El objetivo de esta entrada es ver algunos métodos por los cuales se generan números aleatorios en los cuales se utilizan algunos conceptos de teoría de números.


Generadores de congruencia lineal


El primer método que veremos, consiste en, a partir de unos datos inciales, generar números usando congruencias lineales. De manera más precisa, el método funciona así.

Generador. Dados cuatro números enteros positivos x (llamado semilla), a, b y m, se define el número x_0 como

x_0\equiv (ax+b)\bmod m.

Para todo n\geq 1 se generan de manera recursiva,

x_{n+1}\equiv x_n\bmod m.

Como te puedes dar cuenta, es un método bastante sencillo, además de ser barato. Hagamos un ejemplo.


Ejemplo con x=2, a=3b=5 y m=7


Lo primero que hacemos es calcular el valor x_0, reemplazando los valores en la congruencia obtenemos

x_0\equiv (3\cdot 2+5)\equiv 11\equiv 4\bmod 7.

De modo que x_0=4. A partir de acá, se pueden generar todos los demás números.

Valor n Número generado x_n
0 4
1 3
2 0
3 5
4 6
5 2
6 4
7 3
8 0

Como puedes ver, es un método bastante económico y sencillo de recrear en código. Una observación que podemos hacer, es que el valor que se genera en cada número aleatorio será menor al del módulo, en este caso el valor m. De modo que no es conveniente tomar un valor pequeño, como en nuestro ejemplo, pues los números generados irán desde 0 hasta 6, conviene más tomar un valor grande.

Una de las principales limitaciones de este método es qué, al ser un módulo, los valores se repiten. Si observamos la tabla anterior vemos que el valor x_6 es el mismo x_0, de hecho, a partir de allí se repiten todos los números. Es decir, sin importar los valores que tomemos, eventualmente se empezarán a repetir los números que se generan.

Otra desventaja de este método, es que la semilla siempre genera los mismos números aleatorios. Dicho de otra forma,

Dada la semilla x, este método genera siempre los mismos números aleatorios.

Este hecho quita la sensación de algo aleatorio, en qué sentido: ¿Como se le puede llamar aleatorio a un método que genera siempre los mismos números? Existen programas que sub-sanan este detalle cambiando la semilla constantemente.

Si nos adentramos un poco más, vemos que puede ocurrir otro problema, y es que dicho periodo se repita lo más pronto posible. Por ejemplo, si tomamos como semilla x=2, a=3b=5 y  m=12, obtenemos la siguiente sucesión de números aleatorios.

Valor n Número generado x_n
0 11
1 2
2 11
3 2
4 11
5 2
6 11
7 2
8 11

El cual, sin lugar a dudas, no es una sucesión que nos convenga como para obtener números aleatorios. Esto da buenos argumentos para deducir que la selección de los valores xabm no pueden hacerse sin cuidado alguno.

El siguiente teorema nos permite saber si el periodo del generador es el más grande posible

Teorema(Hull – Dobell). Un generador de congruencia lineal tiene periodo máximo si

  1. Los números m y b son primos relativos.
  2. Si q es un número primo que divide a m entonces q divide a a-1.
  3. Si cuatro divide a m, entonces cuatro divide a a-1.

Generalmente, los números que se utilizan para estos generadores son a=7^5b=0m=2^{r}-1, donde r es cierta cantidad según la capacidad de procesamiento que se disponga. Este fue propuesto por  Park y Miller en 1988, la única condición es que la semilla sea distinto de cero.

Otra variación para este tipo de generadores, es este

Generador. Dados los enteros positivos a_0, a_1, …, a_k, b y m, dadas la k semillas x_0, x_1, …, x_k, se define el valor x_{k+1} como

x_{n+1}\equiv (a_0x_{n}+a_1x_{n-1}\cdots a_k x_{n-k}+b)\bmod m.

Para todo n>k se generan de manera recursiva.

Es decir, en este caso, cada valor depende de los k valores  anteriores.


Cuadrado medio


Este es un método que se usó en un tiempo, consistía en ir elevando al cuadrado un número, para luego tomar los dígitos del medio, para así generar el nuevo número aleatorio. De manera más precisa

Generador. Partimos de un número de 2n dígitos. Para generar el siguiente número elevamos el número al cuadrado y tomamos el segmento que se encuentra en la mitad de longitud 2n.

Por ejemplo, si partimos del número 1234, para generar el siguiente número, elevamos al cuadrado para obtener

1522756,

de modo que el nuevo número es 5227. El siguiente número sería

27321529,

el siguiente número será 3215… y así

Valor n Número generado x_n
0 1234
1 5227
2 3215
3 3362
4 3030
5 1809
6 2724
7 4291
8 6484

Este método fue propuesto por John Von Neumann y Nicholas Metropolis alrededor de 1946, y parece generar un buen número aleatorio. Sin embargo, este tiene sus problemas, por ejemplo, es posible que se caiga en un bucle rápidamente, si empezamos por el número 6100, obtenemos la siguiente sucesión de números:

Valor n Número generado x_n
0 6100
1 2100
2 4100
3 8100
4 6100
5 2100
6 4100
7 8100
8 6100

Hay algo que cabe resaltar, y es que en algunos casos el número obtenido al elevar al cuadrado no tiene un segmento mitad, como por ejemplo, en la anterior tabla, al elevar al cuadrado 2100 obtenemos 4410000, dicho número tiene un segmento medio de cuatro dígitos. En tal caso, toca determinar qué lado se va a escoger, en este caso, tomé la parte de la izquierda. Note que si se toma la parte de la derecha se cae en un bucle que termina en ceros:

Valor n Número generado x_n
0 6100
1 2100
2 1000
3 0000
4 0000
5 0000
6 0000
7 0000
8 0000

Generadores de Fibonacci


Antes de decir como es el generador como tal, recordemos como es la sucesión de Fibonacci.

Se definen los valores f_0 y f_1 como

f_1=1

f_2=1,

definimos f_n para n>2 como

f_{n}=f_{n-1}+f_{n-2}.

Es una de las sucesiones más conocidas, de las cuales se conocen bastantes propiedades. Los generadores tipo Fibonacci, simplemente son generadores en los cuales cada número depende de los dos anteriores.

Generador. Dados N_0 y N_1 un par de valores enteros positivos, sea m>1 entero positivo, entonces

N_n\equiv N_{n-s}\circ {N_{n-r}}\bmod m

donde s y s son valores distintos ambos menores a n y \circ es una operación es algun de las operaciones suma, resta o multiplicación.

Es un generador sencillo, económico a la vez. Acá está un ejemplo, si tomamos N_0=4 y N_1=11, además de m=13, y s=1, r=2 obtenemos los siguientes valores.

Valor n Número generado x_n
0 4
1 11
2 5
3 3
4 2
5 6
6 12
7 7
8 6

PI


Sí, nuestro último método que veremos tiene que ver con aquella constante tan famosa llamada Pi. Una manera de obtener un número aleatorio es escoger una cadena de números de los dígitos de la constante Pi. Este parece ser un método que no tiene ningún problema, sin embargo, se demostró que la aleatoriedad que se obtiene es distinta a otros métodos.

Expliquemos un poco más esto, para que un método genere buenos “números aleatorios” el método debe cumplir ciertas características, la principal de ellas es la siguiente

Si consideramos el inverso de cada número 1/x_i entonces esa sucesión de inversos se asemeje a una sucesión de realizaciones independientes de una variable aleatoria con distribución uniforme entre cero y uno.

No se demostró propiamente que esta manera de generar números cumple o no la anterior condición, a cambio, se comparó los números obtenidos con otros métodos, con el fin de sacar conclusiones.

[…]Se ha completado un estudio comparando la “aleatoriedad” en  los dígitos de pi a los producidos por treinta programas de computador generadores de números aleatorios y una máquina (física) generadora de caos. Después de llevar a cabo muchas pruebas, ellos han encontrado que aunque las sucesiones de pi son, de hecho, una fuente aceptable de números aleatorios […] los dígitos de pi no siempre producen números aleatorios tan efectivos como otros generadores lo hacen.

Es decir, solo concluyen que, a partir de experimentos, es mejor considerar algún otro método que con los dígitos de pi, sin desestimar la aleatoriedad otorgada por la constante pi.


Referencias

  • Pi seems a good random number generator – but not always the best, Chad Boutin [URL].
  • Algoritmos usados para generar número pseudo-aleatorios en los randomizer o rng, Nelson García [URL]
  • Simulación computacional. Generación de números aleatorios. Irene Tischer, [URL]
  • Generación de números aleatorios. [URL]
Anuncios

Una respuesta

Subscribe to comments with RSS.


Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: