De pile-face à Bernoulli $B(p)$

marsup · April 2021

Bonjour
Les deux faits suivants sont bien connus.

Pour $X_1,X_2,\dots$ une suite infinie de Pile/Face : iid de Bernoulli $B(1/2)$, la variable $U = \sum\limits_{n=1}^{+\infty} \frac{X_n}{2^n}$ est uniforme sur $[0;1]$.
Si $U$ est uniforme sur $[0;1]$, pour $p\in[0;1]$, la variable $1_{[U > p]}$ est de Bernoulli $B(p)$.

J'ai appris récemment l'astuce suivante qui met les deux résultats ensemble :

J'écris $p = \sum\limits_{n=1}^{+\infty} \frac{a_n}{2^n}$ en base 2 : $\forall n, a_n\in\{0,1\}$.

Alors pour $N = \inf\big\{n \mid X_n \neq a_n\big\}$, on a $[U > p] = [X_N > a_N]$ presque-sûrement.

De plus, la variable $N$ est géométrique de paramètre $\frac{1}{2}$, donc en particulier $E[N] = 2$.

Ainsi, si je connais $p$ en base 2, je peux me servir de ma suite illimitée $(X_n)$ pour obtenir non pas une seule v.a. $B(p)$, mais autant que je veux !
(et pour en engendrer $m$, il me suffit en moyenne de $2m$ pile ou face).

Il paraît que ça correspond au fait que l'entropie de $B(p)$ est $\le 1$, mais je ne m'y connais pas.

marsup · April 2021

Tiens d'ailleurs, je me faisais deux remarques en me relisant.

1. En termes de processus avec $\mathcal{F}_n = \sigma(X_1,\dots,X_n)$, ça signifie que l'événement $[U>p]$ est $\mathcal{F}_N$-mesurable.

2. Pour simuler la loi de Bernoulli $B(p)$, il me suffit en fait :

d'une variable géométrique $N$ de paramètre $\frac{1}{2}$,
d'une variable $Y$, indépendante et de loi $B(1/2)$, qui jouera le rôle de $X_N$.

Ensuite, on regarde l'événement $[Y>a_N]$, et celui-ci vient avec probabilité $p$.

marsup · April 2021

Bon, j'avance.

L'entropie pour la loi $N\hookrightarrow G(1/2)$ est $2$. Par la formule, l'entropie de cette loi, c'est son espérance (!)

Si j'ai une infinité $N_1,N_2,\dots$ d'instances iid de cette loi,

Si je dispose d'un signal binaire, je peux transmettre ces valeurs des $N_i$ en envoyant des signaux de la forme $\underbrace{1,1,1,\dots,1,0}_{N_i \text{ bits}}$.

Ceci donne une suite iid de PF, et chaque $N_i$ met en moyenne $E[N_i] = 2 = H(N_i)$ bits à être transmis. Je pense que ça signifie que ce procédé est optimal : c'est le plus compressé.

Évidemment, on peut faire la même chose avec n'importe quelle $G(p)$, mais on doit pouvoir trouver plus rapide, sans doute.

Par exemple pour $N_i$ géométriques avec $p=1-\frac{1}{\sqrt{2}}$, je conjecture qu'il vaut mieux envoyer $\lceil \frac{N_i + 1}{2} \rceil$ comme ci-dessus, puis envoyer un dernier bit pour dire si on est pair ou impair. En moyenne, ça demande 2+1 = 3 bits, ce qui est mieux que $\frac{1}{p} = \frac{1}{0,293} > 3$. Ok.

marsup · April 2021

Ah mais, pour la loi de Bernoulli, on peut faire un truc pareil.

Si on a une proba $p = \frac{1}{256} = 2^{8}$, et qu'on a une infinité de valeurs iid de $B(p)$ à envoyer, je les regroupe par paquet de 256. J'ai environ $\frac{1}{e}$ de chance d'avoir un succès parmi celles-là. Si c'est le cas, j'envoie simplement la liste des moments où j'ai eu un succès. (8 bits pour chaque succès en écrivant la position $\in\{0,...,255\}$ en binaire.)

Ça me fait en gros en moyenne ($1 + 8\times$ l'espérance de la loi de Poisson + $\epsilon = 9+\epsilon$) bits pour envoyer chaque groupe de 256 valeurs, ce qui est vachement plus compressé que les 256 valeurs communiquées.

Je pense que pour optimiser, quand $p$ est très petit, il faut envoyer par paquets de $\frac{\ln(2)}{p}$, comme ça, on a une chance sur 2 d'avoir un succès dans chaque paquet ?

Je crois que c'est à peu près ça (une petite partie) que dit le théorème de codage de la source de Shannon Youpi (:D

gebrane · May 2021

Bonjour mars up .

J'attends la suite de ton monologue que j'aime bien

De pile-face à Bernoulli $B(p)$

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 21