Puncte:2

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?

drapel de

Am citit câteva lucrări care menționează corectorul von Neumann. Ei presupun întotdeauna că pentru corectorul von Neumann, biții de intrare sunt independenți unul de celălalt și aceeași părtinire

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?

Puncte:2
drapel my

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...

Paul Uszak avatar
drapel cn
Ei bine, Paul e un nemaipomenit, motiv pentru care nimeni nu-l place. Dar pe fond, paragraful tău final este greșit din punct de vedere matematic. Îmi pare rău. Se vor produce execuții în întregime probabilistice precum `000000110001` din care vN poate extrage entropia. H(stream) $\ne$ 0. Și versiunea vN mai avansată (care folosește mai mult decât comparații pe perechi) se va descurca și mai bine.
Paul Uszak avatar
drapel cn
Nu foarte bine cu chestia cu matematica, dar `01` înseamnă $a
Paul Uszak avatar
drapel cn
Și vă rugăm să votați întrebarea dacă ați considerat că merită să răspundeți...
Paul Uszak avatar
drapel cn
Re: _"Dibiaserul Von Neumann de bază (sic)_" este, de asemenea, incorect. vN nu este bazat pe biți, este bazat pe eșantion, așa cum este detaliat [aici](https://crypto.stackexchange.com/a/87362/23115). Asta am vrut să spun cu $a$ și $b$.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.