Simulando una probabilidad de 1 de 2 ^ N con menos de N bits aleatorios

Digamos que necesito simular la siguiente distribución discreta:

P (X = k) = {\begin{cases} \frac{1}{2^{N}}, & if k = 1 \\ 1 - \frac{1}{2^{N}}, & if k = 0 \end{cases}

$P(X = k) = \begin{cases} \frac{1}{2^N}, & \text{if $k = 1$} \\ 1 - \frac{1}{2^N}, & \text{if $k = 0$} \end{cases}$

La forma más obvia es dibujar bits aleatorios y verificar si todos equivalen a (o ). Sin embargo, la teoría de la información dice $N$ $0$ $1$

\begin{aligned} S & = - \sum_{i} P_{i} \log P_{i} \\ = - \frac{1}{2^{N}} \log \frac{1}{2^{N}} - (1 - \frac{1}{2^{N}}) \log (1 - \frac{1}{2^{N}}) \\ = \frac{1}{2^{N}} \log 2^{N} + (1 - \frac{1}{2^{N}}) \log \frac{2^{N}}{2^{N} - 1} \\ \to 0 \end{aligned}

$\begin{align} S & = - \sum_{i} P_i \log{P_i} \\ & = - \frac{1}{2^N} \log{\frac{1}{2^N}} - \left(1 - \frac{1}{2^N}\right) \log{\left(1 - \frac{1}{2^N}\right)} \\ & = \frac{1}{2^N} \log{2^N} + \left(1 - \frac{1}{2^N}\right) \log{\frac{2^N}{2^N - 1}} \\ & \rightarrow 0 \end{align}$

Por lo tanto, el número mínimo de bits aleatorios requeridos en realidad disminuye a medida que aumenta . ¿Cómo es esto posible? $N$

Suponga que estamos ejecutando en una computadora donde los bits son su única fuente de aleatoriedad, por lo que no puede simplemente elegir una moneda sesgada.

algorithms information-theory randomness pseudo-random-generators entropy nalzok
fuente

Esto está estrechamente relacionado con la teoría de codificación y la complejidad de Kolmogorov, si está buscando palabras clave para profundizar. La técnica de contar repeticiones repetidas del mismo bit que DW menciona a continuación es muy útil

Brian Gordon,

Respuestas:

Wow, gran pregunta! Déjame intentar explicar la resolución. Tomará tres pasos distintos.

Lo primero a tener en cuenta es que la entropía se centra más en el número promedio de bits necesarios por sorteo, no en el número máximo de bits necesarios.

Con su procedimiento de muestreo, el número máximo de bits aleatorios necesarios por sorteo es bits, pero el número promedio de bits necesarios es 2 bits (el promedio de una distribución geométrica con ), esto se debe a que hay un probabilidad de que solo necesite 1 bit (si el primer bit resulta ser 1), probabilidad de que solo necesite 2 bits (si los primeros dos bits resultan ser 01), un probabilidad de que solo necesite 3 bits (si los primeros tres bits resultan ser 001), y así sucesivamente. $N$ $p=1/2$ $1/2$ $1/4$ $1/8$

La segunda cosa a tener en cuenta es que la entropía realmente no captura el número promedio de bits necesarios para un solo sorteo. En cambio, la entropía captura el número amortizado de bits necesarios para muestrear iid extracciones de esta distribución. Supongamos que necesitamos bits para muestrear dibujos; entonces la entropía es el límite de como . $m$ $f(m)$ $m$ $f(m)/m$ $m \to \infty$

La tercera cosa a tener en cuenta es que, con esta distribución, puede muestrear iid draws con menos bits de los necesarios para muestrear repetidamente un dibujo. Suponga que ingenuamente decidió dibujar una muestra (toma 2 bits aleatorios en promedio), luego extraiga otra muestra (usando 2 bits aleatorios más en promedio), y así sucesivamente, hasta que haya repetido esto veces. Eso requeriría alrededor de bits aleatorios en promedio. $m$ $m$ $2m$

Pero resulta que hay una manera de muestrear dibujos usando menos de bits. ¡Es difícil de creer, pero es verdad! $m$ $2m$

Déjame darte la intuición. Suponga que anota el resultado del muestreo de sorteos, donde es realmente grande. Entonces el resultado podría especificarse como una cadena de bits. Esta cadena de bits será principalmente 0, con unos pocos 1: en particular, en promedio tendrá aproximadamente 1 (podría ser más o menos que eso, pero si es lo suficientemente grande, generalmente el número estará cerca de eso). La longitud de los espacios entre los 1 es aleatoria, pero típicamente estará en algún lugar vagamente cerca de (podría ser fácilmente la mitad o el doble o incluso más, pero de ese orden de magnitud). Por supuesto, en lugar de escribir todo el $m$ $m$ $m$ $m$ $m/2^N$ $m$ $2^N$ $m$ cadena de bits, podríamos escribirlo de manera más sucinta escribiendo una lista de las longitudes de los huecos, que contiene la misma información, en un formato más comprimido. ¿Cuánto más sucinto? Bueno, generalmente necesitaremos unos bits para representar la longitud de cada espacio; y habrá aproximadamente espacios; así que necesitaremos en total aproximadamente bits (podría ser un poco más, podría ser un poco menos, pero si es lo suficientemente grande, por lo general estará cerca de eso). Eso es mucho más corto que una cadena de bits. $N$ $m/2^N$ $mN/2^N$ $m$ $m$

Y si hay una manera de escribir la cadena de manera sucinta, tal vez no sea demasiado sorprendente si eso significa que hay una manera de generar la cadena con un número de bits aleatorios comparables a la longitud de la cadena. En particular, genera aleatoriamente la longitud de cada espacio; esto es un muestreo de una distribución geométrica con , y eso se puede hacer con aproximadamente bits aleatorios en promedio (no ). Necesitará aproximadamente iid a partir de esta distribución geométrica, por lo que necesitará en total aproximadamente bits aleatorios. (Podría ser un factor constante pequeño más grande, pero no demasiado grande). Y tenga en cuenta que esto es mucho más pequeño que bits. $p=1/2^N$ $\sim N$ $2^N$ $m/2^N$ $\sim Nm/2^N$ $2m$

Por lo tanto, podemos muestrear iid extrae de su distribución, utilizando solo bits aleatorios (aproximadamente). Recuerde que la entropía es . Así que esto significa que usted debe esperar que la entropía sea (más o menos) . Eso se apaga un poco, porque el cálculo anterior fue incompleto y crudo, pero espero que te dé una idea de por qué la entropía es lo que es y por qué todo es consistente y razonable. $m$ $f(m) \sim Nm/2^N$ $\lim_{m \to \infty} f(m)/m$ $N/2^N$

DW
fuente

Wow, gran respuesta! Pero, ¿podría explicar por qué el muestreo de una distribución geométrica con toma bits en promedio? Sé que una variable tan aleatoria tendría una media de , por lo que se necesitan en promedio bits para almacenar, pero supongo que esto no significa que pueda generar uno con bits.

p = \frac{1}{2^{N}}

$p=\frac{1}{2^N}$

N

$N$

2^{N}

$2^N$

N

$N$

N

$N$

nalzok

@nalzok, una pregunta justa! ¿Tal vez podrías hacer eso como una pregunta separada? Puedo ver cómo hacerlo, pero es un poco complicado escribir en este momento. Si preguntas, tal vez alguien pueda responder más rápido que yo. El enfoque en el que estoy pensando es similar a la codificación aritmética. Defina (donde es el rv geométrico), luego genere un número aleatorio en el intervalo , y encuentre tal que . Si anota los bits de la expension binaria uno a la vez, por lo general después de anotar bits de , serán determinados por completo.

q_{i} = Pr [X \leq i]

$q_i = \Pr[X\le i]$

X

$X$

r

$r$

[0, 1)

$[0,1)$

i

$i$

q_{i} \leq r < q_{i + 1}

$q_i \le r < q_{i+1}$

r

$r$

N + O (1)

$N+O(1)$

r

$r$

i

$i$

Entonces, ¿básicamente está utilizando el método inverso CDF para convertir una variable aleatoria distribuida uniformemente en una distribución arbitraria, combinada con una idea similar a la búsqueda binaria? Necesitaré analizar la función cuantil de una distribución geométrica para estar seguro, pero esta pista es suficiente. ¡Gracias!

nalzok

@nalzok, ahh, sí, esa es una mejor manera de pensarlo, encantador. Gracias por sugerir eso. Sí, eso es lo que tenía en mente.

Puedes pensar esto al revés: considera el problema de la codificación binaria en lugar de la generación. Suponga que tiene una fuente que emite símbolos con , . Por ejemplo, si , obtenemos . Entonces (Shannon nos dice) hay una codificación binaria decodificable de forma exclusiva , donde (bits de datos), de modo que necesitamos, en promedio, aproximadamente bits de datos para cada símbolo original . $X\in \{A,B\}$ $p(A)=2^{-N}$ $p(B)=1-2^{-N}$ $N=3$ $H(X)\approx 0.54356$ $X \to Y$ $Y \in \{0,1\}$ $0.54356$ $X$

(En caso de que se pregunte cómo puede existir tal codificación, dado que solo tenemos dos símbolos de origen, y parece que no podemos hacerlo mejor que la codificación trivial, , , con un bit por símbolo, necesita comprender que para aproximar el límite de Shannon necesitamos tomar "extensiones" de la fuente, es decir, para codificar secuencias de entradas como un todo. Ver en particular la codificación aritmética). $A\to 0$ $B\to 1$

Una vez que lo anterior está claro, si suponemos que tenemos un mapeo invertible , y notando que, en el límite de Shannon, debe tener una entropía máxima (1 bit de información por bit de datos), es decir , tiene las estadísticas de una moneda justa, entonces tenemos a mano un esquema de generación: dibuje bits aleatorios (aquí no tiene relación con ) con una moneda justa, interprete como la salida del codificador , y decodificar de él. De esta manera, tendrá el distribución de probabilidad deseada, y tenemos que (en promedio) monedas para generar cada valor de . $X^n \to Y^n$ $Y^n$ $Y^n$ $n$ $n$ $N$ $Y^n$ $X^n$ $X^n$ $H(X)<1$ $X$

leonbloy
fuente