Simuler une probabilité de 1 sur 2 ^ N avec moins de N bits aléatoires

Disons que je dois simuler la distribution discrète suivante:

La façon la plus évidente est de dessiner $N$ bits aléatoires et de vérifier s'ils sont tous égaux à $0$ (ou $1$ ). Cependant, la théorie de l'information dit

Ainsi, le nombre minimum de bits aléatoires requis diminue réellement lorsque $N$ devient grand. Comment est-ce possible?

Veuillez supposer que nous fonctionnons sur un ordinateur où les bits sont votre seule source de hasard, donc vous ne pouvez pas simplement essayer une pièce biaisée.

Wow, grande question! Permettez-moi d'essayer d'expliquer la résolution. Cela prendra trois étapes distinctes.

La première chose à noter est que l'entropie se concentre davantage sur le nombre moyen de bits nécessaires par tirage, pas sur le nombre maximum de bits nécessaires.

Avec votre procédure d' échantillonnage, le nombre maximal de bits aléatoires nécessaires par tirage au sort est $N$ bits mais le nombre moyen de bits nécessaires est de 2 bits (la moyenne d'une distribution géométrique avec $p=1/2$ ) - ceci est qu'il y a un $1/2$ probabilité que vous avez seulement besoin de 1 bit (si le premier bit se révèle être 1), un $1/4$ probabilité que vous avez seulement besoin 2 bits (si les deux premiers bits se révèlent être 01), un $1/8$ probabilité que vous n'ayez besoin que de 3 bits (si les trois premiers bits s'avèrent être 001), et ainsi de suite.

La deuxième chose à noter est que l'entropie ne capture pas vraiment le nombre moyen de bits nécessaires pour un seul tirage. Au lieu de cela, l'entropie capture le nombre amorti de bits nécessaires pour échantillonner les tirages $m$ iid de cette distribution. Supposons que nous ayons besoin de $f(m)$ bits pour échantillonner $m$ tirages; alors l'entropie est la limite de $f(m)/m$ lorsque $m \to \infty$ .

La troisième chose à noter est qu'avec cette distribution, vous pouvez échantillonner des tirages $m$ iid avec moins de bits que nécessaire pour échantillonner plusieurs fois un tirage. Supposons que vous ayez décidé naïvement de tirer un échantillon (prend 2 bits aléatoires en moyenne), puis de dessiner un autre échantillon (en utilisant 2 autres bits aléatoires en moyenne), et ainsi de suite, jusqu'à ce que vous ayez répété cette opération $m$ fois. Cela nécessiterait environ $2m$ bits aléatoires en moyenne.

Mais il s'avère qu'il existe un moyen d'échantillonner à partir de $m$ tirages en utilisant moins de $2m$ bits. C'est difficile à croire, mais c'est vrai!

Laissez-moi vous donner l'intuition. Supposons que vous ayez noté le résultat de l'échantillonnage de $m$ tirages, où $m$ est vraiment grand. Le résultat pourrait alors être spécifié sous la forme d'une chaîne de $m$ bits. Cette chaîne de $m$ bits sera principalement composée de 0, avec quelques 1: en particulier, elle aura en moyenne environ $m/2^N$ 1 (pourrait être plus ou moins que cela, mais si $m$ est suffisamment grand, généralement le nombre sera proche de cela). La longueur des écarts entre les 1 est aléatoire, mais sera généralement quelque part vaguement à proximité de $2^N$(pourrait facilement être la moitié de cela ou le double ou même plus, mais de cet ordre de grandeur). Bien sûr, au lieu d'écrire toute la chaîne $m$ bits, nous pourrions l'écrire de manière plus succincte en écrivant une liste des longueurs des intervalles - qui contient toutes les mêmes informations, dans un format plus compressé. Combien plus succinct? Eh bien, nous aurons généralement besoin d'environ $N$ bits pour représenter la longueur de chaque espace; et il y aura environ $m/2^N$ lacunes; nous aurons donc besoin au total d'environ $mN/2^N$ bits (pourrait être un peu plus, peut être un peu moins, mais si $m$ est suffisamment grand, il sera généralement proche de cela). C'est beaucoup plus court qu'un$m$chaîne de m bits.

Et s'il existe un moyen d'écrire cette chaîne de manière succincte, il ne sera peut-être pas trop surprenant si cela signifie qu'il existe un moyen de générer la chaîne avec un nombre de bits aléatoires comparable à la longueur de la chaîne. En particulier, vous générez aléatoirement la longueur de chaque espace; ceci est échantillonnage d'une distribution géométrique avec $p=1/2^N$ , et qui peut être fait avec environ $\sim N$ bits aléatoires en moyenne (pas $2^N$ ). Vous aurez besoin d'environ $m/2^N$ iid à partir de cette distribution géométrique, vous aurez donc besoin au total d'environ $\sim Nm/2^N$bits aléatoires. (Ce pourrait être un petit facteur constant plus grand, mais pas trop grand.) Et, notez que c'est beaucoup plus petit que $2m$ bits.

$m$$f(m) \sim Nm/2^N$$\lim_{m \to \infty} f(m)/m$$N/2^N$

Vous pouvez penser cela à l'envers: considérez le problème de l'encodage binaire au lieu de la génération. Supposons que vous ayez une source qui émet les symboles avec , . Par exemple, si , nous obtenons . Donc (Shannon nous dit) il y a un codage binaire décodable unique , où (bits de données), de telle sorte que nous avons besoin, en moyenne, d'environ bits de données pour chaque symbole 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$

(Dans le cas où vous vous demandez comment un tel encodage peut exister, étant donné que nous n'avons que deux symboles source, et il semble que nous ne pouvons pas faire mieux que l'encodage trivial, , , avec un bit par symbole, vous devez comprendre que pour approximer la limite de Shannon, nous devons prendre des "extensions" de la source, c'est-à-dire coder des séquences d'entrées dans leur ensemble. Voir en particulier le codage arithmétique).$A\to 0$$B\to 1$

$X^n \to Y^n$$Y^n$$Y^n$$n$$n$$N$$Y^n$$X^n$$X^n$$H(X)<1$$X$