LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

problema del matrimonio estable (también conocido como problema de emparejamiento estable o SMP ) es el problema de encontrar una correspondencia estable entre dos conjuntos de elementos de igual tamaño dado un orden de preferencias para cada elemento. Una coincidencia es una asignación de los elementos de un conjunto a los elementos del otro conjunto. Una coincidencia no es estable si:

1. Hay un elemento A del primer conjunto coincidente que prefiere un determinado elemento B del segundo conjunto coincidente sobre el elemento con el que A ya está coincidente, y
2. B también prefiere A sobre el elemento con el que B ya está emparejado.

En otras palabras, una coincidencia es estable cuando no existe ninguna coincidencia ( A , B ), por lo que tanto Acomo B estarían individualmente mejor que con el elemento con el que están actualmente emparejados.

El problema del matrimonio estable se ha declarado como sigue:

Dados n hombres y n mujeres, donde cada persona ha clasificado a todos los miembros del sexo opuesto en orden de preferencia, se casan con los hombres y las mujeres de manera tal que no haya dos personas del sexo opuesto que preferirían tener el uno al otro que sus parejas actuales. . Cuando no hay tales parejas de personas, el conjunto de matrimonios se considera estable.

Tenga en cuenta que la existencia de dos clases que se deben emparejar entre sí (hombres y mujeres en este ejemplo), distingue este problema del problema de los compañeros de habitación estable .

Aplicaciones [ editar ]

Los algoritmos para encontrar soluciones al problema del matrimonio estable tienen aplicaciones en una variedad de situaciones del mundo real, quizás el más conocido de estos esté en la asignación de estudiantes de medicina graduados a sus primeras citas en el hospital. ^[1] En 2012, se otorgó el Premio Nobel de Economía a Lloyd S. Shapley y Alvin E. Roth "por la teoría de las asignaciones estables y la práctica del diseño de mercado". ^[2]

Una aplicación importante ya gran escala del matrimonio estable es la asignación de usuarios a servidores en un gran servicio de Internet distribuido. ^[3] Miles de millones de usuarios acceden a páginas web, videos y otros servicios en Internet, lo que requiere que cada usuario sea asignado a uno de (potencialmente) cientos de miles de servidores en todo el mundo que ofrecen ese servicio. Un usuario prefiere servidores lo suficientemente proximales para proporcionar un tiempo de respuesta más rápido para el servicio solicitado, lo que da como resultado un pedido preferencial (parcial) de los servidores para cada usuario. Cada servidor prefiere atender a los usuarios que puede con un costo menor, lo que da como resultado un pedido preferencial (parcial) de usuarios para cada servidor. Redes de entrega de contenidoque distribuyen gran parte del contenido y los servicios del mundo resuelven este gran y complejo problema de matrimonio estable entre usuarios y servidores cada decenas de segundos para permitir que miles de millones de usuarios se puedan comparar con sus respectivos servidores que pueden proporcionar las páginas web, videos u otros elementos solicitados. servicios. ^[3]

Solución [ editar ]

Animación que muestra un ejemplo del algoritmo Gale-Shapley.

En 1962, David Gale y Lloyd Shapley demostraron que, para un número igual de hombres y mujeres, siempre es posible resolver el SMP y hacer que todos los matrimonios sean estables. Presentaron un algoritmo para hacerlo. ^[4] [5]

El algoritmo Gale-Shapley (también conocido como algoritmo de aceptación diferida ) implica una serie de "rondas" (o " iteraciones "):

• En la primera ronda, primero a ) cada hombre no comprometido le propone a la mujer que más prefiere, y luego b ) cada mujer responde "tal vez" a su pretendiente que ella prefiere y "no" a todos los demás pretendientes. A continuación, se "compromete" provisionalmente con el pretendiente que más prefiere hasta ahora, y ese pretendiente también está comprometido provisionalmente con ella.
• En cada ronda subsiguiente, primero a ) cada hombre no comprometido propone a la mujer más preferida a la que aún no ha propuesto (independientemente de si la mujer ya está comprometida), y luego b ) cada mujer responde "tal vez" si actualmente está no está comprometida o si ella prefiere a este hombre sobre su actual pareja provisional (en este caso, ella rechaza a su actual pareja provisional que no se involucra). La naturaleza provisional de los compromisos preserva el derecho de una mujer ya comprometida a "comerciar" (y, en el proceso, a "arruinar" a su pareja hasta entonces).
• Este proceso se repite hasta que todos están comprometidos.

La complejidad del tiempo de ejecución de este algoritmo es $${\ displaystyle O (n ^ {2})} dónde $${\ displaystyle n}Es número de hombres o mujeres. ^[6]

Este algoritmo garantiza que:

Todos se casan 

Al final, no puede haber un hombre y una mujer sin compromiso, como él debe haberle propuesto en algún momento (ya que un hombre eventualmente propondrá a todo el mundo, si es necesario) y, al ser propuesto, necesariamente estaría comprometido ( a alguien) a partir de entonces.

Los matrimonios son estables. 

Que Alice y Bob se comprometan, pero no entre ellos. Al completar el algoritmo, no es posible que Alice y Bob se prefieran entre sí sobre sus compañeros actuales. Si Bob prefiere a Alice a su pareja actual, debe haberle propuesto a Alice antes de hacerlo a su pareja actual. Si Alice aceptó su propuesta, pero no está casada con él al final, debe haberlo dejado por alguien que le gusta más y, por lo tanto, no le gusta más a Bob que a su pareja actual. Si Alice rechazó su propuesta, ya estaba con alguien que le gustaba más que a Bob.

Algoritmo [ editar ]

función stableMatching {
    Inicializar todos los m ∈ M y w ∈ W para libre 
    , mientras que ∃ libre el hombre m que todavía tiene una mujer w proponer a {
       w = primera mujer en la lista de m a quien m aún no ha propuesto
       si w está libre 
         (m, w) se activa, de lo 
       contrario ya existe algún par (m ', w)
          si w prefiere m a m'
            m 'queda libre 
           (m, w) se compromete de  
         otra manera 
           (m', w) permanece ocupado
    }
}

Diferentes emparejamientos estables [ editar ]

En general, puede haber muchos emparejamientos estables diferentes. Por ejemplo, supongamos que hay tres hombres (A, B, C) y tres mujeres (X, Y, Z) que tienen preferencias de:

A: YXZ B: ZYX C: XZY  

X: BAC Y: CBA Z: ACB

Hay tres soluciones estables para este arreglo coincidente:

• los hombres obtienen su primera opción y las mujeres su tercera opción (AY, BZ, CX);
• todos los participantes obtienen su segunda opción - (AX, BY, CZ);
• las mujeres obtienen su primera opción y los hombres la tercera - (AZ, BX, CY).

Los tres son estables, porque la inestabilidad requiere que uno de los participantes esté más contento con un partido alternativo. Darle a un grupo sus primeras elecciones asegura que las coincidencias sean estables porque no estarían satisfechos con cualquier otra coincidencia propuesta. Dar a cada uno su segunda opción asegura que cualquier otra coincidencia sea rechazada por una de las partes.

Optimalidad de la solución [ editar ]

Prueba de que la aceptación diferida es óptima para los hombres.

La existencia de diferentes coincidencias estables plantea la pregunta: ¿qué coincidencia devuelve el algoritmo de Gale-Shapley? ¿Es el emparejamiento mejor para los hombres, para las mujeres o el intermedio? En el ejemplo anterior, el algoritmo converge en una sola ronda en la solución óptima para los hombres porque cada mujer recibe exactamente una propuesta y, por lo tanto, selecciona esa propuesta como su mejor opción, asegurándose de que cada hombre tenga una oferta aceptada y finalice el emparejamiento.

Este es un hecho general: el algoritmo Gale-Shapley en el que los hombres se proponen a las mujeres siempre produce una coincidencia estable que es la mejor para todos los hombres entre todas las coincidencias estables. Del mismo modo, si las mujeres lo proponen, el emparejamiento resultante es el mejor para todas las mujeres entre todos los emparejamientos estables.

Para ver esto, considera la ilustración de la derecha. Sea A el emparejamiento generado por el algoritmo de proposición de hombres, y B un emparejamiento estable alternativo que sea mejor para al menos un hombre, digamos m ₀ . Supongamos que m ₀ coincide en B con una mujer w ₁ , que él prefiere a su partido en A. Esto significa que en A, m ₀ ha visitado w ₁ , pero ella lo rechazó (esto se denota con la flecha verde de m ₀ a w ₁ ). w ₁ lo rechazaron en favor de un hombre que prefiere, digamos m ₂ . Así que en B, w ₁coincide con m ₀ pero "yearns" (quiere pero no coincide ) con m ₂ (esto se denota con la flecha roja de w ₁ a m ₂ ).

Como B es una coincidencia estable, m ₂ debe coincidir en B con una mujer que él prefiere w ₁ , digamos w ₃ . Esto significa que en A, m ₂ ha visitado w ₃ antes de llegar a w ₁ , lo que significa que w _{3 lo} ha rechazado. Por consideraciones similares, y dado que la gráfica es finita, eventualmente debemos tener un ciclo dirigido en el que cada hombre fue rechazado en A por la siguiente mujer en el ciclo, quien lo rechazó en favor del siguiente hombre en el ciclo. Pero esto es imposible ya que tal "ciclo de rechazos" no puede comenzar en ninguna parte: supongamos por contradicción que comienza, por ejemplo, en m ₀- el primer hombre rechazado por su mujer adyacente ( w ₁ ). Por supuesto, este rechazo ocurre solo después de que m ₂ llega a w ₁ . Pero esto solo puede suceder después de que w ₃ rechaza m ₂ , lo que contradice que m ₀ sea ​​el primero.

Consideraciones estratégicas [ editar ]

El algoritmo GS es un mecanismo verdadero desde el punto de vista de los hombres (el lado que propone). Es decir, ningún hombre puede obtener una mejor correspondencia para sí mismo al tergiversar sus preferencias. Además, el algoritmo GS es incluso una prueba de estrategia grupal para los hombres, es decir, ninguna coalición de hombres puede coordinar una tergiversación de sus preferencias de tal manera que todos los hombres en la coalición estén estrictamente en mejores condiciones. ^[7] Sin embargo, es posible que alguna coalición distorsione sus preferencias de tal manera que algunos hombres estén en mejores condiciones y los otros hombres conserven la misma pareja. ^[8]

El algoritmo GS no es verídico para las mujeres (el lado de revisión): cada mujer puede tergiversar sus preferencias y obtener una mejor coincidencia.

Contando los emparejamientos estables [ editar ]

En una instancia uniformemente aleatoria del problema del matrimonio estable con n hombres yn mujeres, el número promedio de emparejamientos estables es asintóticamente$${\ displaystyle e ^ {- 1} n \ ln n}. ^[9]

El máximo crece al menos exponencialmente con n , y contar el número de coincidencias estables en una instancia dada es isP-completo . ^[10]

Implementación en paquetes de software [ editar ]

• R : El algoritmo Gale-Shapley (también conocido como algoritmo de aceptación diferida) para el matrimonio estable y el problema de los hospitales / residentes está disponible como parte de los paquetes matchingMarkets^[11] [12] y matchingR^[13] .

• API : La API de MatchingTools proporciona una interfaz de programación de aplicaciones gratuita para el algoritmo Gale-Shapley. ^[14]

• Python : el algoritmo Gale-Shapley se incluye junto con varios otros para problemas de coincidencia generalizados en el QuantEcon/MatchingMarkets.pypaquete ^[15]

• Matlab : El algoritmo Gale-Shapley se implementa en la assign2DStablefunción que forma parte de la Biblioteca de componentes del rastreador gratuito del Laboratorio de Investigación Naval de los Estados Unidos ^[16] .

Problemas similares [ editar ]

En la correspondencia estable con la indiferencia , algunos hombres pueden ser indiferentes entre dos o más mujeres y viceversa.

El problema de los compañeros de cuarto estables es similar al problema del matrimonio estable, pero difiere en que todos los participantes pertenecen a un grupo único (en lugar de dividirse en números iguales de "hombres" y "mujeres").

El problema de los hospitales / residentes , también conocido como el problema de ingreso a la universidad, se diferencia del problema del matrimonio estable en que un hospital puede aceptar varios residentes o una universidad puede recibir una clase entrante de más de un estudiante. Los algoritmos para resolver el problema de los hospitales / residentes pueden estar orientados hacia el hospital (como lo fue el NRMP antes de 1995) ^[17]o orientarse hacia los residentes . Este problema se resolvió, con un algoritmo, en el mismo artículo original de Gale y Shapley, en el que se resolvió el problema del matrimonio estable. ^[18]

El problema de los hospitales / residentes con las parejas permite que el conjunto de residentes incluya parejas que deben ser asignadas juntas, ya sea al mismo hospital o a un par específico de hospitales elegidos por la pareja (por ejemplo, una pareja casada quiere asegurarse de que se quedarán) juntos y no queden atrapados en programas que están muy lejos unos de otros). La adición de parejas al problema de los hospitales / residentes hace que el problema NP-completo . ^[19]

El problema de asignación busca encontrar una coincidencia en un gráfico bipartito ponderado que tenga el peso máximo. Los emparejamientos ponderados máximos no tienen que ser estables, pero en algunas aplicaciones un emparejamiento ponderado máximo es mejor que uno estable.

El problema de emparejamiento con contratos es una generalización del problema de emparejamiento, en el cual los participantes pueden ser emparejados con diferentes términos de contratos. ^[20] Un caso especial importante de contratos es emparejar con salarios flexibles.

Esta página trata sobre las características comunes de los algoritmos generadores de números pseudoaleatorios. Para el concepto formal en informática teórica, vea Generador pseudoaleatorio .

Un ejemplo de un generador de números pseudoaleatorios.

Un generador de números pseudoaleatorios ( PRNG ), también conocido como generador de bits aleatorio determinista ( DRBG ), ^[1] es un algoritmo para generar una secuencia de números cuyas propiedades se aproximan a las propiedades de las secuencias de números aleatorios . La secuencia generada por PRNG no es verdaderamente aleatoria , ya que está completamente determinada por un valor inicial, llamado semilla del PRNG (que puede incluir valores verdaderamente aleatorios). Aunque las secuencias que son más cercanas a las verdaderamente aleatorias se pueden generar usando generadores de números aleatorios de hardware , pseudoaleatoriosLos generadores de números son importantes en la práctica por su velocidad en la generación de números y su reproducibilidad. ^[2]

Los PRNG son centrales en aplicaciones como simulaciones (por ejemplo, para el método de Monte Carlo ), juegos electrónicos (por ejemplo, para la generación de procedimientos ) y criptografía . Las aplicaciones criptográficas requieren que la salida no sea predecible de salidas anteriores, y se necesitan algoritmos más elaborados , que no heredan la linealidad de PRNG más simples.

Las buenas propiedades estadísticas son un requisito central para la salida de un PRNG. En general, se requiere un análisis matemático cuidadoso para tener la confianza de que un PRNG genera números que son lo suficientemente cercanos al azar como para adaptarse al uso previsto. John von Neumann advirtió sobre la mala interpretación de un PRNG como un verdadero generador aleatorio, y dijo en broma que "cualquiera que considere métodos aritméticos para producir dígitos al azar está, por supuesto, en un estado de pecado". 

Los problemas potenciales con los generadores deterministas [ editar ]

En la práctica, la salida de muchos PRNG comunes exhibe artefactos que hacen que fallen las pruebas estadísticas de detección de patrones. Éstos incluyen:

• Períodos más cortos que los esperados para algunos estados semilla (tales estados semilla pueden llamarse 'débiles' en este contexto);
• Falta de uniformidad de distribución para grandes cantidades de números generados;
• Correlación de valores sucesivos;
• Distribución dimensional pobre de la secuencia de salida;
• Las distancias entre donde ocurren ciertos valores se distribuyen de manera diferente de aquellas en una distribución de secuencia aleatoria.

Los defectos exhibidos por PRNGs defectuosos van desde imperceptibles (y desconocidos) hasta muy obvios. Un ejemplo fue el algoritmo de números aleatorios RANDU utilizado durante décadas en computadoras centrales. Fue gravemente defectuoso, pero su insuficiencia no fue detectada durante mucho tiempo.

En muchos campos, mucho trabajo de investigación anterior al siglo XXI que se basó en la selección aleatoria o en las simulaciones de Monte Carlo , o en otras formas se basó en los PRNG, es mucho menos confiable de lo que podría haber sido como resultado del uso de PRNG de baja calidad. ^[4] Incluso hoy en día, a veces se requiere precaución, como lo ilustra la siguiente advertencia, que se encuentra en la Enciclopedia Internacional de Ciencia Estadística (2010). ^[5]

La lista de generadores de uso general que deben descartarse es [larga] ... Verifique el [PRNG] predeterminado de su software favorito y esté listo para reemplazarlo si es necesario. Esta última recomendación se ha hecho una y otra vez en los últimos 40 años. Tal vez sorprendentemente, sigue siendo tan relevante hoy como lo fue hace 40 años.

Como ilustración, consideremos el lenguaje de programación Java ampliamente utilizado . A partir de 2017 , Java todavía se basa en un generador lineal congruente (LCG) para su PRNG; ^[6] [7] sin embargo, los LCG son de baja calidad; consulte más abajo.

El primer PRNG que evitó problemas importantes y aún funcionó con bastante rapidez fue el Mersenne Twister(que se explica a continuación), que se publicó en 1998. Desde entonces, se han desarrollado otros PRNG de alta calidad.

Generadores basados ​​en recurrencias lineales [ editar ]

En la segunda mitad del siglo XX, la clase estándar de algoritmos utilizados para los PRNG comprendía generadores lineales congruentes . Se sabía que la calidad de los LCG era inadecuada, pero no había mejores métodos disponibles. Press et al. (2007) describió el resultado de esta manera: "Si todos los artículos científicos cuyos resultados están en duda debido a [LCGs y relacionados] desaparecieran de las estanterías de la biblioteca, habría una brecha en cada estante tan grande como su puño". ^[8]

Un gran avance en la construcción de generadores pseudoaleatorios fue la introducción de técnicas basadas en recurrencias lineales en el campo de dos elementos; tales generadores están relacionados con los registros de desplazamiento de retroalimentación lineal .

La invención de 1997 de Mersenne Twister , ^[9] en particular, evitó muchos de los problemas con generadores anteriores. El Mersenne Twister tiene un período de 2 ¹⁹⁹³⁷ −1 iteraciones (≈4.3 × 10 ⁶⁰⁰¹ ), se ha demostrado que se equidistribuye en (hasta) 623 dimensiones (para valores de 32 bits), y en el momento de su introducción estaba funcionando más rápido que otros generadores estadísticamente razonables.

En 2003, George Marsaglia introdujo la familia de generadores xorshift , ^[10] nuevamente basada en una recurrencia lineal. Tales generadores son extremadamente rápidos y, combinados con una operación no lineal, pasan pruebas estadísticas sólidas. ^{[11] [12] [13]}

En 2006 se desarrolló la familia de generadores WELL . ^[14] De alguna manera, los generadores WELL mejoran la calidad del Mersenne Twister, que tiene un espacio de estado demasiado grande y una recuperación muy lenta de los espacios de estado con un gran número de ceros.

Generadores de números pseudoaleatorios criptográficamente seguros [ editar ]

Artículo principal: Generador de números pseudoaleatorios criptográficamente seguro

Un PRNG adecuado para aplicaciones criptográficas se denomina PRNG criptográficamente seguro (CSPRNG). Un requisito para un CSPRNG es que un adversario que no sepa que la semilla tiene una ventaja insignificante al distinguir la secuencia de salida del generador de una secuencia aleatoria. En otras palabras, mientras que un PRNG solo se requiere para pasar ciertas pruebas estadísticas, un CSPRNG debe pasar todas las pruebas estadísticas que están restringidas al tiempo polinomial en el tamaño de la semilla. Aunque una prueba de esta propiedad está más allá del estado actual de la técnica de la teoría de la complejidad computacional , se puede proporcionar evidencia sólida reduciendo el CSPRNG a un problemase supone que es difícil , como la factorización de enteros . ^[15] En general, pueden requerirse años de revisión antes de que un algoritmo pueda ser certificado como un CSPRNG.

Algunas clases de CSPRNGs incluyen lo siguiente:

• cifrados de flujo
• cifrados de bloque que se ejecutan en el contador ^[16] o en modo de realimentación de salida
• PRNG que han sido diseñados específicamente para ser criptográficamente segura, como Microsoft 's aplicación criptográfica interfaz de programación de la función CryptGenRandom , el algoritmo de Yarrow(incorporado en Mac OS X y FreeBSD ), y Fortuna
• PRNG combinados que intentan combinar varios algoritmos primitivos de PRNG con el objetivo de eliminar cualquier no aleatoriedad detectable
• diseños especiales basados ​​en suposiciones de dureza matemática: los ejemplos incluyen el generador Micali-Schnorr , ^[17] función pseudoaleatoria Naor-Reingold y el algoritmo Blum Blum Shub , que proporcionan una sólida prueba de seguridad. Tales algoritmos son bastante lentos en comparación con las construcciones tradicionales, y no son prácticos para muchas aplicaciones.
• PRNG genéricos: se ha demostrado que un PRNG seguro (criptográficamente) puede construirse genéricamente a partir de cualquier función unidireccional . ^[18] Sin embargo, esta construcción genérica es extremadamente lenta en la práctica y es principalmente de interés teórico.

Se ha demostrado que es probable que la NSA haya insertado una puerta trasera asimétrica en el generador de números pseudoaleatorios certificado por el NIST Dual_EC_DRBG . ^[19]

La mayoría de los algoritmos de PRNG producen secuencias que se distribuyen uniformemente por cualquiera de varias pruebas. Es una pregunta abierta, y una parte central de la teoría y la práctica de la criptografía , si existe alguna forma de distinguir el resultado de un PRNG de alta calidad de una secuencia verdaderamente aleatoria. En esta configuración, el distintivo sabe que se usó el algoritmo PRNG conocido (pero no el estado con el que se inicializó) o que se usó un algoritmo verdaderamente aleatorio, y debe distinguir entre los dos. ^[20] La seguridad de la mayoría de los algoritmos y protocolos criptográficos que usan PRNG se basa en el supuesto de que no es posible distinguir el uso de un PRNG adecuado del uso de una secuencia verdaderamente aleatoria. Los ejemplos más simples de esta dependencia son:cifrados de flujo , que (en la mayoría de los casos) funcionan mediante la exclusiva o el texto simple de un mensaje con la salida de un PRNG, lo que produce texto cifrado . El diseño de PRNGs criptográficamente adecuados es extremadamente difícil, ya que deben cumplir con criterios adicionales. El tamaño de su período es un factor importante en la idoneidad criptográfica de un PRNG, pero no el único.

Criterios de evaluación BSI [ editar ]

La Oficina Federal Alemana para la Seguridad de la Información ( Bundesamt für Sicherheit in der Informationstechnik , BSI) ha establecido cuatro criterios para la calidad de los generadores de números aleatorios deterministas. ^[21] Se resumen aquí:

• K1: debe haber una alta probabilidad de que las secuencias generadas de números aleatorios sean diferentes entre sí.
• K2: una secuencia de números que no se puede distinguir de los números "aleatorios verdaderos" según las pruebas estadísticas especificadas. Las pruebas son la prueba monobit (número igual de unos y ceros en la secuencia), la prueba de póquer (una instancia especial de la prueba de chi-cuadrado ), la prueba de carreras(cuenta la frecuencia de las carreras de varias longitudes), la prueba de larga duración (verifica si existe una ejecución de longitud 34 o mayor en 20 000 bits de la secuencia), tanto de BSI ^[21] como de NIST , ^[22] y la autocorrelaciónprueba. En esencia, estos requisitos son una prueba de qué tan bien una secuencia de bits: tiene ceros y unos con la misma frecuencia; después de una secuencia de n ceros (o unos), el siguiente bit es uno (o cero) con probabilidad media; y cualquier subsecuencia seleccionada no contiene información sobre el (los) siguiente (s) elemento (s) en la secuencia.
• K3: debería ser imposible para cualquier atacante (para todos los propósitos prácticos) calcular, o adivinar de otra manera, a partir de cualquier subsecuencia dada, cualquier valor anterior o futuro en la secuencia, ni ningún estado interno del generador.
• K4: para todos los propósitos prácticos, debería ser imposible para un atacante calcular, o adivinar a partir de un estado interno del generador, números anteriores en la secuencia o estados anteriores del generador interno.

Para aplicaciones criptográficas, solo se aceptan los generadores que cumplan con el estándar K3 o K4.

Definición matemática [ editar ]

Dado

• $${\ displaystyle P} - una distribución de probabilidad en $${\ displaystyle \ left (\ mathbb {R}, {\ mathfrak {B}} \ right)} (dónde $${\ displaystyle {\ mathfrak {B}}}es el Borel estándar establecido en la línea real)
• $${\ displaystyle {\ mathfrak {F}}} - una colección no vacía de conjuntos de Borel $${\ displaystyle {\ mathfrak {F}} \ subseteq {\ mathfrak {B}}}, p.ej $${\ displaystyle {\ mathfrak {F}} = \ left \ {\ left (- \ infty, t \ right]: t \ in \ mathbb {R} \ right \}}. Si$${\ displaystyle {\ mathfrak {F}}} no se especifica, puede ser cualquiera $${\ displaystyle {\ mathfrak {B}}} o $${\ displaystyle \ left \ {\ left (- \ infty, t \ right]: t \ in \ mathbb {R} \ right \}}, dependiendo del contexto.
• $${\ displaystyle A \ subseteq \ mathbb {R}}- un conjunto no vacío (no necesariamente un conjunto Borel). A menudo$${\ displaystyle A} es un conjunto entre $${\ displaystyle P}El apoyo y su interior ; por ejemplo, si$${\ displaystyle P} Es la distribución uniforme en el intervalo. $${\ displaystyle \ left (0,1 \ right]}, $${\ displaystyle A} puede ser $${\ displaystyle \ left (0,1 \ right]}. Si$${\ displaystyle A} no se especifica, se supone que es un conjunto contenido en el soporte de $${\ displaystyle P} y conteniendo su interior, según el contexto.

Llamamos una funcion $${\ displaystyle f: \ mathbb {N} _ {1} \ rightarrow \ mathbb {R}} (dónde $${\ displaystyle \ mathbb {N} _ {1} = \ left \ {1,2,3, \ dots \ right \}}es el conjunto de enteros positivos) un generador de números pseudoaleatorios para$${\ displaystyle P} dado $${\ displaystyle {\ mathfrak {F}}} tomando valores en $${\ displaystyle A} sif

• $${\ displaystyle f \ left (\ mathbb {N} _ {1} \ right) \ subseteq A}
• {\ displaystyle \ forall E \ in {\ mathfrak {F}} \ quad \ forall 0 <\ varepsilon \ in \ mathbb {R} \ quad \ existe N \ in \ mathbb {N} _ {1} \ quad \ forall N \ leq n \ in \ mathbb {N} _ {1}, \ quad \ left | {\ frac {\ # \ left \ {i \ in \ left \ {1,2, \ dots, n \ right \} : f (i) \ in E \ right \}} {n}} - P (E) \ right | <\ varepsilon}

($${\ displaystyle \ #S} denota el número de elementos en el conjunto finito $${\ displaystyle S}.)

Se puede demostrar que si $${\ displaystyle f} es un generador de números pseudoaleatorios para la distribución uniforme en $${\ displaystyle \ left (0,1 \ right)} y si $${\ displaystyle F}Es el CDF de alguna distribución de probabilidad dada.$${\ displaystyle P}, entonces $${\ displaystyle F ^ {*} \ circ f} es un generador de números pseudoaleatorios para $${\ displaystyle P}, dónde $${\ displaystyle F ^ {*}: \ left (0,1 \ right) \ rightarrow \ mathbb {R}} es el percentil de $${\ displaystyle P}es decir $${\ displaystyle F ^ {*} (x): = \ inf \ left \ {t \ in \ mathbb {R}: x \ leq F (t) \ right \}}. Intuitivamente, se puede simular una distribución arbitraria a partir de una simulación de la distribución uniforme estándar.

Los primeros enfoques [ editar ]

Un PRNG basado en una computadora temprana, sugerido por John von Neumann en 1946, se conoce como el método del cuadrado medio . El algoritmo es el siguiente: tomar cualquier número, cuadrarlo, eliminar los dígitos del medio del número resultante como "número aleatorio", luego usar ese número como semilla para la siguiente iteración. Por ejemplo, al cuadrar el número "1111" se obtiene "1234321", que se puede escribir como "01234321", siendo un número de 8 dígitos el cuadrado de un número de 4 dígitos. Esto da "2343" como el número "aleatorio". Repitiendo este procedimiento se obtiene "4896" como el siguiente resultado, y así sucesivamente. Von Neumann usó números de 10 dígitos, pero el proceso fue el mismo.

Un problema con el método del "cuadrado medio" es que todas las secuencias eventualmente se repiten, algunas muy rápidamente, como "0000". Von Neumann era consciente de esto, pero encontró el enfoque suficiente para sus propósitos, y le preocupaba que las "correcciones" matemáticas simplemente ocultaran los errores en lugar de eliminarlos.

Von Neumann consideró que los generadores de números aleatorios de hardware no eran adecuados, ya que, si no registraban la salida generada, no podrían probarse los errores más tarde. Si registraran su salida, agotarían las limitadas memorias de computadora disponibles en ese momento, y así la capacidad de la computadora para leer y escribir números. Si los números se escribieran en tarjetas, tardarían mucho más tiempo en escribir y leer. En la computadora ENIAC que estaba usando, el método del "cuadrado medio" generaba números a una velocidad unas cientos de veces más rápida que la lectura de números desde tarjetas perforadas .

El método del cuadrado medio ha sido suplantado por generadores más elaborados.

Una innovación reciente es combinar el cuadrado medio con una secuencia de Weyl . Este método produce resultados de alta calidad durante un largo período. Ver Middle Square Weyl Sequence PRNG .

Generadores no uniformes [ editar ]

Artículo principal: Muestreo de números pseudoaleatorios.

Los números seleccionados de una distribución de probabilidad no uniforme pueden generarse usando un PRNG de distribución uniforme y una función que relaciona las dos distribuciones.

Primero, se necesita la función de distribución acumulativa. $${\ displaystyle F (b)} de la distribución de destino $${\ displaystyle f (b)}:

$${\ displaystyle F (b) = \ int _ {- \ infty} ^ {b} f (b ') db'}

Tenga en cuenta que $${\ displaystyle 0 = F (- \ infty) \ leq F (b) \ leq F (\ infty) = 1}. Usando un número aleatorio c de una distribución uniforme como la densidad de probabilidad para "pasar", obtenemos

$${\ displaystyle F (b) = c}

así que eso

$${\ displaystyle b = F ^ {- 1} (c)}

es un número seleccionado al azar de la distribución $${\ displaystyle f (b)}.

Por ejemplo, lo inverso de la distribución gaussiana acumulada. $${\ displaystyle \ operatorname {erf} ^ {- 1} (x)} con un PRNG uniforme ideal con rango (0, 1) como entrada $${\ displaystyle x}produciría una secuencia de valores (solo positivos) con una distribución gaussiana; sin embargo

• Cuando se usan representaciones numéricas prácticas, las "colas" infinitas de la distribución deben truncarse a valores finitos.
• Recálculo repetitivo de $${\ displaystyle \ operatorname {erf} ^ {- 1} (x)}debe reducirse por medios tales como el algoritmo ziggurat para una generación más rápida.

Consideraciones similares se aplican a la generación de otras distribuciones no uniformes, como Rayleigh y Poisson .