fusión aleatoria

En la teoría de extractores , una función de fusión de aleatoriedad extrae aleatoriedad de un conjunto de variables aleatorias, siempre que al menos una de ellas sea uniformemente aleatoria. Su nombre proviene del hecho de que puede considerarse un procedimiento que "fusiona" todas las variables en una sola, preservando al menos parte de la entropía contenida en la variable uniformemente aleatoria. Actualmente, las funciones de fusión se utilizan para construir explícitamente extractores de aleatoriedad.

Consideremos un conjunto de${\displaystyle k}$variables aleatorias ,${\displaystyle X_{1},\ldots ,X_{k}}$, cada uno distribuido sobre${\displaystyle \{0,1\}^{n}}$Al menos una de ellas es aleatoria uniformemente; pero se desconoce cuál. Además, las variables pueden estar correlacionadas arbitrariamente: pueden ser funciones unas de otras, pueden ser constantes, etc. Sin embargo, dado que al menos una de ellas es uniforme, el conjunto en su conjunto contiene al menos${\displaystyle n}$bits de entropía.

La función de la fusión es generar una nueva variable aleatoria, también distribuida sobre${\displaystyle \{0,1\}^{n}}$que conserva la mayor cantidad posible de esa entropía. Idealmente, si se supiera cuál de las variables es uniforme, podría usarse como resultado, pero esa información se desconoce. La idea detrás de las fusiones es que, al usar una pequeña semilla aleatoria adicional, es posible obtener un buen resultado incluso sin saber cuál es la variable uniforme.

Una idea ingenua sería calcular la operación XOR de todas las variables. Si una de ellas tiene una distribución uniforme y es independiente de las demás variables, entonces la salida sería uniforme. Sin embargo, supongamos que...${\displaystyle X_{1}=X_{2}}$y ambos están distribuidos uniformemente, entonces el método no funcionaría.

Definición (fusión):

Una función${\displaystyle M:(\{0,1\}^{n})^{k}\times \{0,1\}^{d}\rightarrow \{0,1\}^{n}}$se llama un${\displaystyle (m,\varepsilon)}$-merger si para cada conjunto de variables aleatorias${\displaystyle (X_{1},\ldots ,X_{k})}$distribuido sobre${\displaystyle \{0,1\}^{n}}$, al menos una de las cuales es uniforme, la distribución de${\displaystyle Z=M(X_{1},\ldots ,X_{k},U_{d})}$tiene entropía mínima suave${\displaystyle H_{\infty }^{\varepsilon }(Z)\geq m}$. La variable${\displaystyle U_{d}}$denota la distribución uniforme sobre${\displaystyle d}$bits, y representa una semilla verdaderamente aleatoria.

En otras palabras, utilizando una pequeña semilla uniforme de longitud${\displaystyle d}$, la fusión devuelve una cadena que es${\displaystyle \varepsilon }$-cerca de tener al menos${\displaystyle m}$min-entropía ; esto significa que su distancia estadística de una cadena con${\displaystyle m}$La min-entropía no es mayor que${\displaystyle \varepsilon }$.

Recordatorio : Existen varias nociones para medir la aleatoriedad de una distribución; la min-entropía de una variable aleatoria.${\displaystyle Z}$se define como el más grande${\displaystyle k}$de tal manera que el valor más probable de${\displaystyle Z}$ocurre con una probabilidad no mayor que${\displaystyle 2^{-k}}$La min-entropía de una cadena es un límite superior a la cantidad de aleatoriedad que se puede extraer de ella. ^{[ 1 ]}

Es posible utilizar fusiones para producir extractores de aleatoriedad con buenos parámetros. Recordemos que un extractor es una función que toma una variable aleatoria con alta min-entropía y devuelve una variable aleatoria más pequeña, pero cercana a la distribución uniforme. Se puede obtener un extractor de min-entropía arbitraria utilizando el siguiente esquema basado en fusiones: ^{[ 2 ] [ 3 ]}

• Dada una fuente de alta min-entropía, divídala en bloques. Según un resultado conocido, ^{[ 4 ]} al menos una de estas particiones también tendrá alta min-entropía como fuente de bloques.
• Aplique un extractor de bloques por separado a todos los bloques. Este es un tipo de extractor más débil, y se conocen buenas construcciones para él. ^{[ 2 ]} Dado que al menos uno de los bloques tiene una entropía mínima alta, al menos una de las salidas es muy cercana a la uniformidad.
• Utilice la función de fusión para combinar todas las salidas anteriores en una sola cadena. Si se utiliza una buena función de fusión, la cadena resultante tendrá una entropía mínima muy alta en relación con su longitud.
• Utilice un extractor conocido que funcione únicamente con fuentes de entropía mínima muy alta para extraer la aleatoriedad.

La esencia del método anterior consiste en utilizar la fusión para transformar una cadena con entropía mínima arbitraria en una cadena más corta, sin perder mucha entropía mínima en el proceso. Esta nueva cadena tiene una entropía mínima muy alta en relación con su longitud, lo que permite utilizar extractores antiguos y conocidos que solo funcionan con ese tipo de cadenas.

• Extractor de aleatoriedad