Simulando uma probabilidade de 1 de 2 ^ N com menos de N bits aleatórios

Digamos que preciso simular a seguinte distribuição 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}$

A maneira mais óbvia é desenhar $N$ bits aleatórios e verificar se todos são iguais a (ou ). No entanto, a teoria da informação diz $0$ $1$

\begin{aligned} S & = - \sum_{Eu} P_{Eu} registro P_{Eu} \\ = - \frac{1}{2^{N}} registro \frac{1}{2^{N}} - (1 - \frac{1}{2^{N}}) registro (1 - \frac{1}{2^{N}}) \\ = \frac{1}{2^{N}} registro 2^{N} + (1 - \frac{1}{2^{N}}) registro \frac{2^{N}}{2^{N} - 1} \\ \to 0 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}$

Portanto, o número mínimo de bits aleatórios necessários realmente diminui à medida que aumenta. Como isso é possível? $N$

Por favor, assuma que estamos rodando em um computador em que bits é sua única fonte de aleatoriedade, portanto você não pode simplesmente jogar uma moeda tendenciosa.

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

Isso está intimamente relacionado à teoria da codificação e à complexidade de Kolmogorov, se você estiver procurando por palavras-chave para aprofundar. A técnica de contar repetições repetidas da mesma parte que DW menciona abaixo é muito importante - essas notas de aula tocam nela, por exemplo, people.cs.uchicago.edu/~fortnow/papers/kaikoura.pdf

Brian Gordon

Respostas:

Uau, ótima pergunta! Deixe-me tentar explicar a resolução. São necessários três passos distintos.

A primeira coisa a observar é que a entropia está mais focada no número médio de bits necessários por sorteio, não no número máximo de bits necessário.

Com o procedimento de amostragem, o número máximo de bits aleatórios necessários por sorteio é $N$ bits de, mas o número médio de bits necessários é de 2 bits (a média de uma distribuição geométrica com $p=1/2$ ) - Isto é porque existe um $1/2$ probabilidade de que você só precisa de 1 bit (se o primeiro bit acaba por ser 1), um $1/4$ probabilidade de que você só precisa de 2 bits (se os dois primeiros bits vir a ser 01), um $1/8$ probabilidade de você precisar apenas de 3 bits (se os três primeiros forem 001) e assim por diante.

A segunda coisa a notar é que a entropia não captura realmente o número médio de bits necessários para um único desenho. Em vez disso, as capturas de entropia o amortizado número de bits necessários para a amostra $m$ iid retira esta distribuição. Suponha que precisamos de $f(m)$ bits para amostrar $m$ draws; então a entropia é o limite de $f(m)/m$ como $m \to \infty$ .

A terceira coisa a notar é que, com esta distribuição, você pode provar $m$ iid desenha com menos bits do que o necessário para repetidamente amostra um empate. Suponha que você ingenuamente tenha decidido desenhar uma amostra (em média 2 bits aleatórios) e, em seguida, outra amostra (usando mais 2 bits aleatórios em média), e assim por diante, até repetir isso $m$ vezes. Isso exigiria cerca de $2m$ de bits aleatórios em média.

Mas acontece que há uma maneira de coletar amostras de $m$ draws usando menos de $2m$ bits. É difícil de acreditar, mas é verdade!

Deixe-me lhe dar a intuição. Suponha que você anotou o resultado da amostragem de $m$ draws, onde $m$ é realmente grande. Em seguida, o resultado pode ser especificado como uma sequência de bits de $m$ . Essa cadeia de $m$ bits será composta principalmente de 0's, com alguns 1's: em particular, em média, terá cerca de $m/2^N$ (pode ser mais ou menos que isso, mas se $m$ for suficientemente grande, geralmente o número estará perto disso). O comprimento dos intervalos entre as 1 são aleatório, mas será tipicamente algures vagamente na vizinhança de $2^N$ (poderia facilmente ser metade ou duas vezes mais ou mais, mas dessa ordem de magnitude). Obviamente, em vez de escrever toda a cadeia de bits de $m$ , poderíamos escrevê-la de maneira mais sucinta, escrevendo uma lista dos comprimentos das lacunas - que carregam todas as mesmas informações, em um formato mais compactado. Quanto mais sucinto? Bem, normalmente precisamos de cerca de $N$ bits para representar o comprimento de cada intervalo; e haverá cerca de $m/2^N$ folgas; portanto, precisaremos no total de $mN/2^N$ bits (pode ser um pouco mais, pode ser um pouco menos, mas se $m$ for suficientemente grande, geralmente será próximo disso). Isso é muito mais curto que um $m$ cadeia de bits .

E se houver uma maneira de escrever a sequência de forma sucinta, talvez não seja muito surpreendente se isso significa que há uma maneira de gerar a sequência com um número de bits aleatórios comparável ao comprimento da sequência. Em particular, você gera aleatoriamente o comprimento de cada intervalo; esta é a amostragem a partir de uma distribuição geométrica com $p=1/2^N$ , e que pode ser feito com cerca de $\sim N$ bits aleatórios, em média (não $2^N$ ). Você precisará de $m/2^N$ iid é extraído dessa distribuição geométrica, portanto, precisará no total aproximadamente $\sim Nm/2^N$ bits aleatórios. (Pode ser um fator constante pequeno maior, mas não muito maior.) E observe que isso é muito menor que $2m$ bits.

Assim, podemos provar $m$ iid chama de sua distribuição, usando apenas $f(m) \sim Nm/2^N$ bits aleatórios (aproximadamente). Lembre-se de que a entropia é $\lim_{m \to \infty} f(m)/m$ . Então isso significa que você deve esperar a entropia ser (aproximadamente) $N/2^N$ . Isso diminuiu um pouco, porque o cálculo acima foi superficial e bruto - mas espero que lhe dê alguma intuição sobre por que a entropia é o que é e por que tudo é consistente e razoável.

DW
fonte

Uau, ótima resposta! Mas você poderia explicar por que a amostragem de uma distribuição geométrica com

leva

bits em média? Eu sei que uma variável aleatória teria uma média de

, por isso leva em média

bits para armazenar, mas suponho que isso não significa que você possa gerar uma com

bits.

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

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

N

$N$

2^{N}

$2^N$

N

$N$

N

$N$

nalzok 25/03

@nalzok, uma pergunta justa! Você poderia fazer isso como uma pergunta separada? Eu posso ver como fazê-lo, mas é um pouco bagunçado digitar agora. Se você perguntar, talvez alguém possa responder mais rápido do que eu. A abordagem em que estou pensando é semelhante à codificação aritmética. Defina

(onde

é o rv geométrico), gere um número aleatório

no intervalo

e encontre

tal que

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}$ . Se você escrever os bits da despesa binária

um de cada vez, geralmente depois de escrever

bits de

serei completamente determinado.

r

$r$

N + O (1)

$N+O(1)$

r

$r$

i

$i$

Então, você está basicamente usando o método CDF inverso para converter uma variável aleatória distribuída uniformemente em uma distribuição arbitrária, combinada com uma ideia semelhante à pesquisa binária? Precisarei analisar a função quantil de uma distribuição geométrica para ter certeza, mas essa dica é suficiente. Obrigado!

nalzok 25/03

@ Dalzok, ahh, sim, essa é uma maneira mais agradável de pensar sobre isso - adorável. Obrigado por sugerir isso. Sim, é isso que eu tinha em mente.

Você pode pensar o contrário: considere o problema da codificação binária em vez da geração. Suponhamos que tem uma fonte que emite símbolos $X\in \{A,B\}$ com $p(A)=2^{-N}$ , $p(B)=1-2^{-N}$ . Por exemplo, se $N=3$ , obtemos $H(X)\approx 0.54356$ . Então (Shannon nos diz), existe uma codificação binária exclusivamente decodível $X \to Y$ , Onde $Y \in \{0,1\}$ (bits de dados), tais que necessitam, em média, cerca de $0.54356$ bits de dados para cada símbolo original $X$ .

(Caso você esteja se perguntando como essa codificação pode existir, considerando que temos apenas dois símbolos de origem, e parece que não podemos fazer melhor que a codificação trivial, $A\to 0$ , $B\to 1$ , com um bit por símbolo, você precisa para entender que, para aproximar o limite de Shannon, precisamos usar "extensões" da fonte, ou seja, para codificar seqüências de entradas como um todo. Veja, em particular, codificação aritmética).

Uma vez que o exposto esteja claro, se assumirmos que temos um mapeamento invertível $X^n \to Y^n$ , e percebendo que, no limite de Shannon, $Y^n$ deve ter entropia máxima (1 bit de informação por bit de dados), ou seja, $Y^n$ tem as estatísticas de uma moeda justa, temos um esquema de geração à mão: desenhe $n$ bits aleatórios (aqui $n$ não tem relação com $N$ ) com uma moeda justa, interprete-a como a saída $Y^n$ do codificador e decodifique $X^n$ de isto. Dessa forma, $X^n$ terá a probabilidade de distribuição desejado, e precisamos de (em média) $H(X)<1$ moedas para gerar cada valor de $X$ .

leonbloy
fonte