Editați | ×:
Pe baza comentariului OP, un mod de a gândi diferența dintre Guesswork și Shannon Entropy este următorul:
Shannon: Să presupunem că avem o variabilă aleatorie de codificat. Având în vedere distribuția sa, se poate folosi un cod Huffman sau o altă procedură de codare sursă, iar lungimea așteptată a cuvintelor de cod din acel cod este strâns legată de entropia Shannon a variabilei aleatoare. Un arbore de cod Huffman descrie un proces recursiv în care arbitrar puternic interogările pot fi făcute din variabila aleatoare. De exemplu se poate cere, pentru $X\în {1,\ldots,N\}$ intrebarea
Este $X \leq N/3$?
și alegeți ramura stângă a copacului de la rădăcină dacă răspunsul este da. În cazul lui Huffman, dorim să minimizăm copacul și, deși folosim o procedură frumoasă de jos în sus de „unire” frunzelor, în cele din urmă, dacă întrebarea este întrebarea de mai sus, atunci $Pr[X\leq N/3]\aprox 1/2.$ Ne împărțim stânga/dreapta într-un punct care lasă probabilitățile celor doi subarbori echilibrate.
Ghicituri: În acest context, interogarea nu poate fi arbitrar de puternic este de obicei atomică. Ceea ce vreau să spun este că în timp ce construim arborele, avem voie să punem o întrebare despre formă
Este $X=1$?
de exemplu. Presupunând $Pr[X=1]$ este cea mai mare probabilitate atomică a formei $Pr[X=x]$ Unde
$x\în \{1,2,\ldots,N\}$ aceasta este cea mai bună întrebare pe care trebuie să o puneți pentru a minimiza numărul de presupuneri. În acest caz, veți avea în continuare un arbore, dar structura costurilor se modifică, nu puteți exclude un subarboresc dacă răspunsul este Nu puteți exclude doar o valoare $X=1.$ Aceasta este ceea ce duce la Ghicirea entropiei sau $H_{1/2}(X).$
Aplicațiile în care se utilizează acest lucru includ atacuri de ghicire cu forță brută. Nu poți întreba Prima literă a parolei este A? trebuie să introduceți parola completă și fie să intrați, fie să fiți respins. Acesta este motivul pentru care nu puteți folosi întrebări atomice și nu puteți întreba despre părți ale șirului necunoscut.
Fundal:
S-au discutat aici despre Ghicirea entropiei (care este într-adevăr entropia Renyi de ordinul 1/2) în întrebările de mai jos:
diferențele dintre entropiile Shannon și Guessing
securitatea autentificării parolei dată de entropie
În rezumat, dacă sunteți îngrijorat de numărul mediu de presupuneri pentru a determina o variabilă aleatoare necunoscută, atunci ar trebui să utilizați Guessing entropy nu Shannon entropy, deoarece prima este strâns legată de numărul așteptat de presupuneri.
Entropia Renyi a ordinii $\alpha$ este definit de
$$
H_{\alpha}(X)=\frac{1}{1-\alpha} \log \left(\sum_{x} Pr(X=x)^{\alpha} \right)
$$
Unde $\alpha \in [0,1) \cup (1,\infty).$ Se supune
$$
\lim_{\alpha\rightarrow 1} H_{\alpha}(X)=H(X).
$$
A fost arătat de John Pliam (vezi Aici ) asta dacă $X$ este o variabilă aleatoare discretă cu $M$ puncte în sprijinul său $H(X)$ poate fi aproape de valoarea sa maximă $\log M$ în timp ce probabilitatea ca un ghicitor optim să descopere valoarea reală a $X$ în $k$ întrebări secvențiale este mult mai mică decât $2^{H(X)}=M.$
Mai mult, nu numai numărul așteptat de ghiciri, ci momente arbitrare
a numărului de ghiciri poate fi legat de entropiile Renyi de ordin divers.
Un rezultat al așteptărilor este că numărul așteptat de presupuneri să
a determina
o variabilă aleatorie $X$ (pentru secvența optimă de ghicire) este
delimitat superior de
$$2^{H_{1/2}(X)-1}$$
Unde $H_{1/2}(X)$ denotă entropia Renyi a ordinii $\alpha=1/2$ și se mai numește și ghicirea entropiei. Mai mult decât atât, este limitat de (pentru toate secvențele de ghicire)
$$\frac{2^{H_{1/2}(X)}}{1 + \log M } \aprox 2^{H_{1/2}(X)} / H_{max}(X)$ $
Unde $H_{max}(X)$ este entropia maximă $\log M$ fie în Renyi
sau cazul Shannon.
