Espacio muestral de pequeño sesgo

En la informática teórica , un espacio de muestra de polarización pequeña (también conocido como espacio -biased muestra , generador -biased , o espacio de probabilidad de polarización pequeña ) es una distribución de probabilidad que los tontos funciones de paridad . En otras palabras, ninguna función de paridad puede distinguir entre un espacio muestral de pequeño sesgo y la distribución uniforme con alta probabilidad y, por lo tanto, los espacios muestrales de pequeño sesgo naturalmente dan lugar a generadores pseudoaleatorios para funciones de paridad. ${\ Displaystyle \ epsilon}$ ${\ Displaystyle \ epsilon}$

La principal propiedad útil de los espacios muestrales de pequeño sesgo es que necesitan muchos menos bits verdaderamente aleatorios que la distribución uniforme para engañar a las paridades. Las construcciones eficientes de espacios muestrales de pequeño sesgo han encontrado muchas aplicaciones en la informática, algunas de las cuales son la desaleatorización , los códigos de corrección de errores y las pruebas probabilísticamente verificables . La conexión con los códigos de corrección de errores es de hecho muy fuerte, ya que los espacios muestrales sesgados son equivalentes a los códigos de corrección de errores equilibrados . ${\ Displaystyle \ epsilon}$ ${\ Displaystyle \ epsilon}$

Sea una distribución de probabilidad sobre . El sesgo de con respecto a un conjunto de índices se define como ^[1] ${\ Displaystyle X}$ ${\ Displaystyle \ {0,1 \} ^ {n}}$ ${\ Displaystyle X}$ ${\ Displaystyle I \ subseteq \ {1, \ dots, n \}}$

donde se toma la suma , el campo finito con dos elementos. En otras palabras, la suma es igual si el número de unos en la muestra en las posiciones definidas por es par y, en caso contrario, la suma es igual . Porque , la suma vacía se define como cero, y por tanto . ${\ Displaystyle \ mathbb {F} _ {2}}$ ${\ Displaystyle \ sum _ {i \ in I} x_ {i}}$ ${\ displaystyle 0}$ ${\ Displaystyle x \ in \ {0,1 \} ^ {n}}$ ${\ Displaystyle I}$ ${\ Displaystyle 1}$ ${\ Displaystyle I = \ conjunto vacío}$ ${\ displaystyle {\ text {sesgo}} _ {\ emptyset} (X) = 1}$

Una distribución de probabilidad sobre se denomina espacio muestral sesgado si se cumple para todos los subconjuntos no vacíos . ${\ Displaystyle X}$ ${\ Displaystyle \ {0,1 \} ^ {n}}$ ${\ Displaystyle \ epsilon}$ ${\ Displaystyle {\ text {sesgo}} _ {I} (X) \ leq \ epsilon}$ ${\ Displaystyle I \ subseteq \ {1,2, \ ldots, n \}}$