De ce corectorul Von Neumann funcționează numai atunci când biții de intrare sunt independenți unul de celălalt și aceeași părtinire?
Dibiaserul Von Neumann de bază funcționează astfel: generați doi biți X, Y și apoi scoateți un bit (sau nu scoateți un bit) cu această logică:
X=0 Y=0 -> Fără ieșire
X=0 Y=1 -> Ieșire a 0
X=1 Y=0 -> Ieșire a 1
X=1 Y=1 -> Fără ieșire
Dacă X și Y sunt necorelate și au aceeași părtinire (adică, probabilitatea ca ele să fie 0 este $p$ iar probabilitatea de 1 este $(1-p)$), atunci rezultă imediat că probabilitatea ca procedura de mai sus să scoată un 0 este $p(1-p)$ iar probabilitatea unui 1 este $p(1-p)$, care este identic (și există o probabilitate $p^2 + (1-p)^2$ de a nu scoate nimic - îl vom rula din nou cu încă doi biți de intrare). În plus, deoarece presupunem că biții de intrare sunt independenți, rularea debiaserului de mai multe ori pe biți de intrare independenți va genera ieșiri independente.
Cu toate acestea, întrebarea dvs. este "ce se întâmplă dacă biții nu sunt independenți sau nu au aceeași părtinire").
În acest caz, logica de mai sus nu este valabilă.
Dacă biții conțin părtiniri diferite, adică dacă primul bit este 0 cu probabilitate $p$, iar al doilea bit este 0 cu probabilitate $q \ne p$), atunci probabilitatea unui 0 este $p(1-q) = p - pq$ iar o probabilitate de 1 este $q(1-p) = q - pq$, așa cum am presupus că $p \ne q$, acestea sunt în mod evident diferite și, prin urmare, ieșirea dibiaserului este părtinitoare.
Dacă biții împărtășesc aceeași părtinire medie, dar sunt corelați, ceea ce se poate întâmpla este ca biții de secvență de la debiaser să fie corelați. De exemplu, dacă a 01 succesiunea este urmată de alta 01 secvență 90% din timp (și în mod similar pentru a 10 secvență), atunci ieșirile adiacente de la debiaser vor fi ele însele puternic corelate, adică dibiaser-ul nu a reușit să transforme șirul brut de intrare în ceva „aleatoriu”.
Răspunsul anterior (care a dat doar contraexemple):
Luați în considerare un caz în care biții de intrare pare sunt 0 90% din timp, iar biții de intrare impari sunt 1 90% din timp.
În acest caz, ieșirea corectorului Von Neumann este și mai puternic părtinitoare decât intrarea.
Exercițiu pentru tine: inventează un contraexemplu similar în care biții nu sunt independenți unul de celălalt...
Paul s-a plâns că exemplul meu a fost „prea extrem” (indiferent ce înseamnă asta – mă gândisem că orice contraexemplu s-ar aplica). În orice caz, voi răspunde cu un alt exemplu, chiar mai extrem.
Luați în considerare o sursă brută care a generat perechi de biți cu această distribuție de probabilitate:
- 00 cu probabilitate 1/3
- 01 cu probabilitate 1/3
- 11 cu probabilitate 1/3
(fiecare pereche fiind necorelată cu orice altă pereche).
Un calcul simplu arată că fiecare pereche are entropia Shannon de $log_2(3) \aproximativ 1,5850$ biți (sau despre $0.7925$ biți de entropie pe bit).
Cu toate acestea, dacă trecem asta printr-un corector Von Neumann, obținem un flux care are, ei bine, 0 bucăți de entropie...
