Método de Congruencias Lineales Modulares

z_{n}=\left( az_{n-1}+c\right) \mbox{mod}m

Donde a,c,m,z_{0} son enteros positivos conocidos, n\in \mathbb{N} y z_{0} es la “semilla” del método.

Ésta sucesión así definida, genera un conjunto de números pseudo-aleatorios que tiene periodo completo si se cumplen:

1) El mcd de \left( m,a\right) es igual a 1. (mcd=Máximo Común
Divisor)

2) Si p es un primo tal que p\backslash m entonces

p\backslash \left(a-1\right)

3) Si 4\backslash m entonces 4\backslash \left( a-1\right)

EJEMPLO

Si z_{0}=8,a=3,c=5,m=19 entonces z_{1}=\left( 3\ast 8+5\right) \mbox{mod}19=10 y la sucesión generada es:

z_{i}=\left\{ 10,16,15,17,18,2,11,0,5,1,8,...\right\}


SIN RECURSIVIDAD

Se probará por inducción sobre n que al resolver la recursividad
nos queda

z_{n}=\left( a^{n}z_{0}+\frac{c\left( a^{n}-1\right) }{a-1}\right) \mbox{mod}m

Para n=0 es obvio que z_{0}=\left( z_{0}\right) \mbox{mod}m, al igual que para n=1 queda z_{n}=\left( az_{0}+c\right) \mbox{mod}m

Suponemos para n=k que

z_{k}=\left( a^{k}z_{0}+\frac{c\left( a^{k}-1\right) }{a-1}\right) \mbox{mod}m

Y ahora para n=k+1 tenemos por definición

z_{k+1}=\left( az_{k}+c\right) \mbox{mod}m

Sustituyendo z_{k}

z_{k+1}=\left( a^{k+1}z_{0}+\frac{ac\left( a^{k}-1\right) }{a-1}+c\right) \mbox{mod}m

z_{k+1}=\left( a^{k+1}z_{0}+\frac{c\left( a^{k+1}-a\right) +c\left(a-1\right) }{a-1}\right) \mbox{mod}m

z_{k+1}=\left( a^{k+1}z_{0}+\frac{c\left( a^{k+1}-1\right) }{a-1}\right) \mbox{mod}m

Demostrado \forall n\in \mathbb{N}\cup \left\{ 0\right\} .


Post #04mycomplexsoul

Anuncios

Análisis de Números Pseudo-aleatorios

Se pretende analizar un conjunto de numeros pseudo-aleatorios para hallar los coeficientes del método de congruencias lineales modulares z_{n}=\left( az_{n-1}+c \right) \left( \mbox{mod}\right) m asociado al conjunto generado.

Aunque técnicamente podemos intentar hallar los coeficientes de cualquier método de generación de números pseudo-aleatorios, tomamos el más sencillo para dar una idea intuitiva de lo que podemos hacer para otros métodos.

Existe la dificultad de saber si realmente los datos que tenemos provienen de un método de congruencias lineales modulares de la forma en que proponemos aquí. En este caso suponemos que los datos provienen de un método de congruencias lineales modulares con coeficientes particulares a,c,m,z_{0}.


ANÁLISIS EN CONDICIONES IDEALES

Sea \left\{ z_{n}\right\} _{n=1}^{M} una sucesión de números pseudo-aleatorios generados por el método de congruencias lineales modulares, donde M\in \mathbb{N} (de preferencia M\rightarrow \infty )

DETERMINAR m

Supongamos que z_{n}=\left( az_{n-1}+c\right) \left( \mbox{mod}\right) m tiene periodo completo, es decir z_{j}=z_{j+m} \forall j\geq 0. De modo que si contamos con los suficientes datos podemos hallar fácilmente el parámetro m. Sabemos que \max_{n\in \mathbb{N}}\left\{ z_{n}\right\} =m-1 por ser el residuo más grande, de modo que

m=\max_{n\in \mathbb{N}}\left\{ z_{n}\right\} +1

DETERMINAR z_{0}

Observe que z_{0}=z_{0+m} de modo que si conocemos m, z_{m} coincide en valor con la semilla del método. De modo que

z_{0}=z_{m}

De no conocer el valor de z_{m}, necesitamos conocer los parámetros a,c,m para determinar z_{0} de z_{1}=\left( az_{0}+c\right) \left( \mbox{mod}\right) m resolviendo la siguiente ecuación entera

z_{0}=a^{-1}\left( z_{1}+hm-c\right)

Donde h es el entero asociado a z_{1}+hm=az_{0}+c después de haber calculado el modulo.

DETERMINAR c

Si z_{j}=0 para algún j, entonces el siguiente z_{j+1}=\left( a\ast 0+c\right) \left( \mbox{mod}\right) m=c+hm, h\geq 0 de modo que

c=z_{j+1}-hm

DETERMINAR a

Si z_{j}=1 para algún j, entonces el siguiente z_{j+1}=\left( a\ast 1+c\right) \left( \mbox{mod}\right) m=a+c+hm, h\geq 0 de modo que

a=z_{j+1}-c-hm


Post #03mycomplexsoul

Integrales Exponenciales

La integral exponencial simple \int x^{n}e^{ax}dx con n\geq 0 y a
constante tiene por resultado:

\int x^{n}e^{ax}dx=e^{ax}\sum\limits_{i=0}^{n}\left( -1\right) ^{i}\frac{1}{a^{i+1}}\frac{d^{i}}{dx^{i}}\left( x^{n}\right)

Donde \frac{d^{0}}{dx^{0}}\left( x^{n}\right) =x^{n}.

Para demostrar este resultado usamos inducción sobre n.


DEMOSTRACIÓN

Para n=0.

\int x^{0}e^{ax}dx=e^{ax}\sum\limits_{i=0}^{0}\left( -1\right) ^{i}\frac{1}{a^{i+1}}\frac{d^{i}}{dx^{i}}\left( x^{0}\right) =e^{ax}\left( \frac{1}{a}\right)

Suponemos para n=k.

\int x^{k}e^{ax}dx=e^{ax}\sum\limits_{i=0}^{k}\left( -1\right) ^{i}\frac{1}{a^{i+1}}\frac{d^{i}}{dx^{i}}\left( x^{k}\right)

Probamos para n=k+1. Usando integración por partes.

\int x^{k+1}e^{ax}dx=\frac{1}{a}x^{k+1}e^{ax}-\frac{\left( k+1\right) }{a}\int x^{k}e^{ax}dx

Sustituyendo

\int x^{k+1}e^{ax}dx=\frac{1}{a}x^{k+1}e^{ax}-\frac{\left( k+1\right) }{a}e^{ax}\sum\limits_{i=0}^{k}\left( -1\right) ^{i}\frac{1}{a^{i+1}}\frac{d^{i}}{dx^{i}}\left( x^{k}\right)

Reescribiendo el índice de la sumatoria

\int x^{k+1}e^{ax}dx=e^{ax}\left( \frac{1}{a}x^{k+1}-\frac{\left( k+1\right) }{a}\sum\limits_{j=1}^{k+1}\left( -1\right) ^{j-1}\frac{1}{a^{j}}\frac{d^{j-1}}{dx^{j-1}}\left( x^{k}\right) \right)

Reescribiendo

\int x^{k+1}e^{ax}dx=e^{ax}\left( \frac{1}{a}x^{k+1}+\sum\limits_{j=1}^{k+1}\left( -1\right) ^{j}\frac{1}{a^{j+1}}\frac{d^{j-1}}{dx^{j-1}}\left( \left( k+1\right) x^{k}\right) \right)

\int x^{k+1}e^{ax}dx=e^{ax}\left( \frac{1}{a}x^{k+1}+\sum\limits_{j=1}^{k+1}\left( -1\right) ^{j}\frac{1}{a^{j+1}}\frac{d^{j-1}}{dx^{j-1}}\left( \frac{d}{dx}\left( x^{k+1}\right) \right) \right)

\int x^{k+1}e^{ax}dx=e^{ax}\left( \frac{1}{a}x^{k+1}+\sum\limits_{j=1}^{k+1}\left( -1\right) ^{j}\frac{1}{a^{j+1}}\frac{d^{j}}{dx^{j}}\left( x^{k+1}\right) \right)

Introduciendo el termino restante con j=0.

\int x^{k+1}e^{ax}dx=e^{ax}\sum\limits_{j=0}^{k+1}\left( -1\right) ^{j}\frac{1}{a^{j+1}}\frac{d^{j}}{dx^{j}}\left( x^{k+1}\right)

Demostrado \forall n\in \mathbb{N}.


Post #02mycomplexsoul