înregistrare Logare
Puncte:0
avatar Crypto

Câte $k$-biți cuvinte dintr-un șir de biți aleatoriu trebuie să extragem înainte de apariția tuturor $2^k$ cuvinte posibile?

drapel de
lyrically wicked

Lăsa $C(X)$ denotă cardinalitatea mulţimii $X$. De exemplu, $C(\{0\}) = 1, C(\{0, 2\}) = 2$ etc.

Lăsa $S$ denotă o secvență (potențial infinită) de biți aleatori. Despică $S$ în $k$-bit cuvinte $w_1, w_2, w_3, \ldots$ De exemplu, dacă $k = 4$ și $S = 0001111010100100\ldots$, atunci $w_1 = 0001, w_2 = 1110, w_3 = 1010, \ldots$

La fiecare pas $i$ (Aici $i \geq 1$), faceți următorii subpași:

  1. Extrage $w_i$ și treceți la sub-pasul 2;
  2. Dacă $C(X) < 2^k$ și $X$ conţine $w_i$, nu face nimic și treci la pas $(i+1)$; dacă $C(X) < 2^k$ și $X$ nu contine $w_i$, a pune $w_i$ în $X$ și treceți la sub-pasul 3;
  3. Dacă $C(X) < 2^k$, mergi la pas $(i+1)$; dacă $C(X) = 2^k$, Stop.

Întrebare: care este valoarea așteptată $i$ când se oprește algoritmul de mai sus? Cu alte cuvinte, dacă $S$ este sursa de biți pseudoaleatori cu adevărat aleatori sau imparțiali, câte cuvinte ar trebui să ne așteptăm să extragem pentru a le umple $X$ cu tot posibilul $k$-biți elemente?

46
0 + 0
Puncte:4
fgrieu avatar Crypto
drapel ng
fgrieu

Acest lucru cunoscut sub numele de problema colectorului de cupoane, cu numărul de cupoane înlocuit cu $2^k$ și $k$ este numărul de biți independenți desenați ($k=4$ în exemplul întrebării).

Este de așteptat $(k\log(2)+\gamma)\,2^k+\frac12+\mathcal O(2^{-k})$ extractii, unde $\gamma\aproximativ 0,5772 $ este constanta lui Euler, și $\log(2)\aproximativ 0,6931$.

Când se fac puține experimente, o aproximare aproximativă a așteptărilor este adesea suficient de bună, de ex. $0,7\,k\,2^k$. Distribuția are a coada lunga. Cred că deviație standard este $\aproximativ\frac\pi{\sqrt6}\,2^k\aprox1,3\times 2^k$.

0 + 0
drapel romania
SEF 777
întrebarea această in alte limbi:

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.