Siguiente: Métodos generales de generación de vv.aa. Nivel anterior: Métodos de generación de vv.aa. Previa: Métodos congruenciales

Otros métodos de generación de números pseudoaleatorios

Sean $\{u_i\}_i$ , $\{v_i\}_i$ dos sucesiones de números pseudoaleatorios, generados congruencialmente, con respectivos períodos c₁ y c₂. La sucesión $\{frac(u_i+v_i)\}_i$ tiene período mcm(c₁,c₂). Sean U₁, U₂ variables aleotorias independientes con distribución U(0,1). La variable Z=frac(U₁+U₂) sigue también una distribución U(0,1).
Demostración:
Como U₁, U₂ son independientes, entonces la variable bidimensional (U₁,U₂) sigue una distribución uniforme en el cuadrado $[0,1]\times [0,1]$ .

$\begin{displaymath}f_{(U_1,U_2)}(u_1,u_2)=1 \ \text {en} \ [0,1]\times [0,1].\end{displaymath}$

Sean

$\begin{displaymath}\left. \begin{array}{ccc} X & = & U_1+U_2 \\ Y & = & U_2 \end{array} \right \} \end{displaymath}$

$\begin{displaymath}\left. \begin{array}{ccc}U_1 & = & X-Y \\ U_2 & = & Y \end{a... ... \begin{array}{cc} 1 & -1 \\ 0 & 1 \end{array} \right\vert = 1\end{displaymath}$

$\begin{displaymath}f(x,y)=1 \text{\ en \ } R,\text{\ con \ } R=\{(x,y) \ / \ 0\leq y \leq 1, \ y \leq x \leq 1+y \} .\end{displaymath}$

La distribución marginal es

$\begin{displaymath}f_X(x)= \left \{ \begin {array} {ccc} x & si & 0 \leq x \leq 1 \\ 2-x & si & 1\leq x \leq 2 \end{array} \right.\end{displaymath}$

Por otra parte,

$\begin{displaymath}Z=frac(X) =\left \{\begin {array} {ccc} X & si & 0 \leq X \leq 1 \\ X-1 & si & 1\leq X \leq 2 \end{array} \right.\end{displaymath}$

Así, para $0\leq z \leq 1$ , se tiene

$\begin{displaymath}F_Z(z)=P(Z\leq z) = P(0\leq X\leq z) + P(1\leq X \leq z+1)=\end{displaymath}$

$\begin{displaymath}= \int_0^z {x}dx + \int_1^{1+z} {(2-x)} dx = \left [\frac{x^2}{2} \right]_0^z + \left [ 2x-\frac{x^2}{2} \right ]_1^{1+z} =\end{displaymath}$

$\begin{displaymath}= \frac{z^2}{2}-0+2(1+z) - \frac{(1+z)^2}{2} - 2 + \frac{1}{... ...} + 2 +2z - \frac{1}{2} - \frac{z^2}{2} -z - 2 + \frac{1}{2} = z.\end{displaymath}$

Q.E.D.

Generadores binarios de cambio de registro
Representemos por b_i el bit i-ésimo.

Partiendo de una semilla $b_{-d+1},\dots, \ b_{-1},\ b_0 ( 2 ) \in \{0,1\}$ , se obtiene el bit i-ésimo a partir de una combinación lineal de los anteriores:

$\begin{displaymath}b_i=a_1b_{i-1}+a_2b_{i-2}+\dots+a_db_{i-d},\text{\ con \ }a_1,\dots, \ a_d \in \{0,1\}.\end{displaymath}$

Los ciclos serán de longitud 2^d-1 a lo sumo (suponiendo a_d=1). Si se obtiene d veces consecutivas el valor 0, entonces el algoritmo degenera generando siempre este valor.

Usualmente se procede como sigue: se toma p>q y se hace

$\begin{displaymath}b_i = (b_{i-p}+b_{i-q}) \equiv 2.\end{displaymath}$

El ciclo así generado tendrá una longitud de a lo sumo 2^p-1 bits.

Si se quiere generar números pseudoaleatorios con precisión 2^-L, se toma

$\begin{displaymath}u_i = \sum_{s=1}^L \frac{b_{s+iL}}{2^s}.\end{displaymath}$

Con el fin de ahorrar esfuerzo de cálculo se suele tomar (método sugerido por Taustworthe)

$\begin{displaymath}u_i = \sum_{s=1}^L \frac{b_{s+it}}{2^s},\end{displaymath}$

donde t se denomina decimación. Así se tiene que el período máximo se alcanza cuando se cumple mcd(t,2^p-1)=1. Los valores más habituales son

$\begin{displaymath}\begin{array}{ccc} p=98 & , & q=27, \\ p=521 & , & q=32, \\ p=607 & , & q=273. \end{array}\end{displaymath}$