TD13 : Entropie et codage

Énoncé

I. Échauffement

1.

  • $1-p = P(Pile)$
  • $p = P(face)$
digraph {
        A -> A;
        A -> B[label="p"];
        B -> A[label="p"];
        B -> D[label="p"];
        A -> C[label="1-p"];
        C -> A[label="1-p"];
        C -> E[label="1-p"]; A[label="𝜀"];
        B[label="F"];
        C[label="P"];
        E[label="retourne pile", shape="doublecircle"];
        D[label="retourne face", shape="doublecircle"];
	}
while x==y:
  x = tirer_piece()
  y = tirer_piece()

return x

Soit $P_E$ la probabilité d’avoir face à la fin depuis l’état :

  • $P_{F} = q + pP_A$
  • $P_{P} = qP_A$
  • $P_{𝜀} = pq + p^2 P_𝜀 + q^2 P_𝜀$

P_𝜀 - p^2 P_𝜀 - P_𝜀 + 2p - p^2P_𝜀 = pq \\ ⟹ P_𝜀 = \frac{1}{2}

Autre méthode :

P(tirage=face) = P(x=face \mid x≠y) \\ = \dfrac{P(x=face, y= pile)}{\underbrace{P(x=face, y=pile)+P(x=pile, y=face)}_{P(x≠y)}} \\ = \frac{pq}{2pq} \\ = \frac{1}{2}

Espérance du nombre de tours dans la chaîne de Markov :

P(x≠y) = 2pq

On a une loi géométrique (le nombre de runs dans la chaîne de Markov), d’espérance

\frac{1}{2pq}

Comme le il y a 2 lancers par tour :

E(\text{nombre de tours}) = 2 × \frac{1}{2pq}= \frac{1}{pq}

2.

On procède par dichotomie :


Tirage_parfait(n):
  k = int(log_2(n))
  x = n
  while x >=n:
    x = 0
    for i in range(k, -1):
      y = tirage()
      if y==face:
        x += 2**(i-1)

  return x+1
P(tirage\_parfait() = 1) = P(x=0 \mid x<n) \\ = \frac{P(x=0, x<n)}{P(x<n)} \\ = \frac{P(x=0)}{P(x<n)} \\ = \frac{(1/2)^k}{n(1/2)^k} \\ = \frac 1 n

Espérance du temps d’exécution $T$:

E(T) = k + \underbrace{\frac{2^k-n}{2^k} }_{\text{probabilité de recommencer}}E(T) \\ = \frac{k}{1 - \frac{2^k-n}{2^k}} = k \frac{2^k}{n}

ou

Espérance du nombre de boucles :

$\frac{2^k}{n}$ et dans chaque boucle, $k$ lancers.


NB : Si $n$ est une puissance de $2$, on peut le faire en temps borné.

Réciproquement :

Supposons qu’on puisse faire un algo en coût constant pour $n$.

Soit $k$ le nombre constant de tirages.

Alors il existe une fonction

f: \lbrace Pile, Face \rbrace^k ⟶ ⟦1,n⟧

tq

∀i, \frac{card(f^{-1}(i))}{2^k} = \frac 1 n

On a

n × card(f^{-1}(i)) = 2^k

donc $n$ est une puissance de $2$.

II. Entropie

Rappel : Pour une v.a $X$ à valeurs finies, tq

p_x ≝ P(X=x)

on a

H(X) = - \sum\limits_{ x∈X } p_x \log(p_x)

De manière plus générale, trouvons une relation entre $H(X)$ et $H(f(X))$, où

P(f(X) = y) = \sum\limits_{ y=f(X) } p_x

NB : si $f$ est injective,

H(f(X)) = - \sum\limits_{ y ∈ Dom(f) } p_y \log(p_y) \\ = - \sum\limits_{ y = f(x) } p_x \log(p_x) = H(X)

car si $f$ est injective, $P(f(x)=y) = p_x$ puisque $x$ est l’unique élément tq $f(x) = y$


Cas général :

H(f(X)) = - \sum\limits_{ y ∈ Dom(f) } p_y \log(p_y) \\ = - \sum\limits_{ y ∈ Dom(f) } \sum\limits_{ \lbrace x \mid y = f(x) \rbrace } p_x \log(\sum\limits_{ \lbrace x \mid y = f(x) \rbrace }) \\ ≤ - \sum\limits_{ y ∈ Dom(f) } \sum\limits_{ \lbrace x \mid y = f(x) \rbrace } p_x \log(p_x) ≤ H(X)

3.

a).

$Y = 2^X$

H(f(X)) = H(X)

par injectivité de $2^\bullet$

b).

$Y = cos(X)$

H(f(X)) ≤ H(X)

4.

Soit $X$ une variable aléatoire $X$ à valeurs dans $\lbrace x_1, ⋯, x_n \rbrace$ et tq

p_i = P(X=x_i)

La valeur minimale de

H(X) = - \sum\limits_{ 1≤i≤n } p_i \underbrace{\log(p_i)}_{≤ 0} ≥ 0

est $0$ : elle est atteinte si la loi de $X$ est un Dirac.

5.

a).

$X \leadsto 𝒢(1/2)$, donc :

H(X) ≝ - \sum\limits_{ i≥1 } p_i \log(p_i)\\ = \sum\limits_{ i≥1 } (1/2)^n n \log(2) = 2 \log(2) = 2

b).

$S_j ≝ ⟦1,j⟧$

j = 1
while xS_j:
  j+=1
return j

Probabilité de sortir de la boucle :

P(x∈S_j \mid x∉S_{j-1}) = \frac{P(x∈S_j, x∉S_{j-1})}{P(x\not∈S_j)} \\ = \frac{1/2^j}{1/2^{j-1}} \\ = \frac 1 2

Donc l’espérance du nombre de requêtes vaut

H(X)=2

III. Codes uniquement déchiffrables

7.

Soient $u, v∈𝛴^\ast$

u-v = \underbrace{\lbrace u' ∈𝛴^\ast \mid u = v\cdot u' \rbrace}_{\text{ soit vide, soit un singleton}}
T_0 ≝ \bigcup\limits_{u≠v∈S} u-v \\ T_i = T_{i-1} ∪ \bigcup\limits_{u∈S, v∈T_{i-1}} \Big( (u-v) ∪ (v-u) \Big) \\ T = \bigcup_{i≥0} T_i

Ex :

S = \lbrace 0, 10, 11 \rbrace \\ T_0 = ∅

Terminaison :

$∃N; T_N = T_{N+1}$ car il y a un nombre fini de suffixes de mots de $S$ (qui est un ensemble fini), et $(T_i)$ est croissante.

Donc $T = T_N$

a).

On veut montrer que $S$ est uniquement déchiffrable ssi $T_N$ ne contient pas $𝜀$.

On peut monter que $T$ satisfait :

\bigcup\limits_{u∈S, v∈T} \Big( (u-v) ∪ (v-u) \Big) ⊆ T

Lemme 1 : Si il existe $u∈T$ et $u_1, ⋯, u_k, v_1, ⋯, v_l∈S$ tq

u_1 ⋯ u_k = u v_1 ⋯ v_l

alors

$𝜀∈T$.

Par récurrence $k+l$ :

  • Cas de base : $k+l=0$ : immédiat.

  • Hérédité : $k+l>0$

    • Si $k=0$ : trivial
    • Si $k>0$ :

      u_1 ⋯ u_k = u v_1 ⋯ v_l
      • Cas 1 : $\vert u \vert < \vert u_1 \vert$

        alors $\underbrace{(u_1-u)}_{≝ u’_1 ∈T} u_2 ⋯ u_k = v_1 ⋯ v_l$

        et on conclut par HR.

      • Cas 2 : $\vert u \vert = \vert u_1 \vert$

        alors $u = u_1$, et $T \ni 𝜀 = u-u_1$

      • Cas 3 : $\vert u \vert > \vert u_1 \vert$

        on procède de même que dans le cas 1.


Lemme 2 : Pour tout $i$, s’il existe $u∈T_i$ et $u_1, ⋯, u_k, v_1, ⋯, v_l∈S$ tq

u u_1 ⋯ u_k = v_1 ⋯ v_l

alors

il existe $v∈T_0$ et $u’_1, ⋯, u’_k, v’_1, ⋯, v’_l∈S$ tq

v u'_1 ⋯ u'_{k'} = v'_1 ⋯ v'_{l'}

Par induction sur $i$

  • Cas de base : $i=0$ : trivial, avec $u=v$

  • Hérédité : $i>0$ :

    Si $u ∈ T_{i}\backslash T_{i-1}$ : il existe $v∈T_{i-1}, s∈S$ tq

    • Cas 1 : $u = v-s$ :

      \underbrace{(su)}_{= v∈ T_{i-1}} u_1 ⋯ u_k = s v_1 ⋯ v_l

      puis HR.

    • Cas 2 : $u = s-v$ :

      \underbrace{(vu)}_{= s∈ S} u_1 ⋯ u_k = \underbrace{v}_{∈T_{i-1}} v_1 ⋯ v_l

      puis HR.


Montrons que

$S$ est uniquement déchiffrable ssi $𝜀∉T$

Si

  • $S ≝ \lbrace w_1, ⋯, w_n \rbrace$
  • $A ≝ \lbrace a_1, ⋯, a_n \rbrace $
  • $f: A ⟶ S$ avec $f(a_i) = w_i$

Montrons que $f^\ast : A^\ast ⟶ S^\ast$ est injective.

$S$ est uniquement déchiffrable ssi $f^\ast : A^\ast ⟶ S^\ast$ est injective.

Supposons que $𝜀∈T$ :

Il existe $N$ tel que $𝜀∈T_N$, donc par le lemme 2, il existe $v∈T_0$ et $u’_1, ⋯, u’_k, v’_1, ⋯, v’_l∈S$ tq

v u'_1 ⋯ u'_{k'} = v'_1 ⋯ v'_{l'}

Donc $v ≝ u - w$ pour $u≠w∈S$, et

\underbrace{w v}_{u} u'_1 ⋯ u'_{k'} = w v'_1 ⋯ v'_{l'}

Comme $u≠w$, $f^\ast$ n’est pas injective.

Supposons que $f^\ast$ n’est pas injective :

Alors il existe $a’_1, ⋯, a’_k$ et $b’_1, ⋯, b’_l$ tq

  • $\underbrace{f(a’1 ⋯ a’_k)}{u_1 ⋯ u_k} = \underbrace{f (b’1 ⋯ b’_l)}{v_1 ⋯ v_l}$
  • $a’_1 ≠ b’_1$

Donc

\underbrace{(u_1-v_1)}_{∈T}u_2 ⋯ u_k = v_2 ⋯ v_l

et par le lemme 1 :

𝜀∈T

b).

S_1 = \lbrace 0, 01, 11 \rbrace \\ T_0 = \lbrace 1 \rbrace = T

⟶ uniquement déchiffrable

S_2 = \lbrace 0, 01, 10 \rbrace \\ T_0 = \lbrace 1 \rbrace \\ T_1 = \lbrace 0, 1 \rbrace \\ T_2 = \lbrace 0, 1, 𝜀 \rbrace

⟶ PAS uniquement déchiffrable

$S_3$ : clairement uniquement déchiffrable

S_4 = \lbrace 00, 01, 10, 11 \rbrace \\ T_0 = ∅ = T

⟶ uniquement déchiffrable

Leave a Comment