Menebak nilai entropi rendah dalam beberapa upaya

9

Misalkan Alice memiliki distribusi lebih terbatas (tapi mungkin sangat besar) domain, sehingga (Shannon) entropi dari adalah atas dibatasi oleh konstan sewenang-wenang kecil . Alice mengambil nilai dari , dan kemudian meminta Bob (siapa yang tahu ) untuk menebak . $\mu$ $\mu$ $\varepsilon$ $x$ $\mu$ $\mu$ $x$

Berapa probabilitas keberhasilan Bob? Jika dia hanya diperbolehkan satu tebakan, maka seseorang dapat menurunkan probabilitas ini sebagai berikut: entropi membatasi min-entropi, jadi ada elemen yang memiliki probabilitas minimal . Jika Bob memilih elemen ini sebagai tebakannya, probabilitas keberhasilannya adalah . $2^{-\varepsilon}$ $2^{-\varepsilon}$

Sekarang, anggaplah bahwa Bob diizinkan untuk membuat beberapa tebakan, katakan tebakan, dan Bob menang jika salah satu tebakannya benar. Apakah ada skema tebakan yang meningkatkan probabilitas keberhasilan Bob? Secara khusus, apakah mungkin untuk menunjukkan bahwa probabilitas kegagalan Bob menurun secara eksponensial dengan ? $t$ $t$

it.information-theory pr.probability Atau Meir
sumber

10

Taruhan terbaik Bob adalah menebak nilai dengan probabilitas terbesar. $t$

Jika Anda sedang bersedia untuk menggunakan Rényi entropi sebaliknya, Proposisi 17 di Boztaş' entropi, Menebak dan Kriptografi menyatakan bahwa probabilitas kesalahan setelah tebakan paling banyak $t$ manaadalah ukuran domain. Memang, ketergantungan padacukup buruk, dan mungkin Boztaş difokuskan pada rezim entropi yang berbeda.

1 - 2^{- H_{2} (μ) (1 - \frac{catatan t}{catatan n})} \approx dalam 2 (1 - \frac{catatan t}{catatan n}) H_{2} (μ),

$1 - 2^{-H_2(\mu)\left(1-\frac{\log t}{\log n}\right)} \approx \ln 2 \left(1-\frac{\log t}{\log n}\right) H_2(\mu),$

n

$n$

t

$t$

Untuk entropi Shannon, Anda dapat mencoba menyelesaikan masalah optimisasi ganda: dengan probabilitas kegagalan tetap , temukan entropi maksimal dari distribusi tersebut. Dengan menggunakan konveksitas , kita tahu bahwa distribusi memiliki bentuk , di mana , $\delta$ $-x\log x$ $\mu$ $a,b,\ldots,b;b,\ldots,b,c$ $a\geq b\geq c$ $a+(t-1)b = 1-\delta$ , dan . Kami memiliki $c = \delta-\lfloor\frac{\delta}{b}\rfloor b$ nilaiyang mendapatkan probabilitas. Mengkondisikan pada $t-1+\lfloor\frac{\delta}{b}\rfloor$ $b$ , kita dapat mencoba menemukanyang meminimalkan entropi. Untuk nilai, ini akan menjadi titik internal (di mana turunannya hilang). Saya tidak yakin bagaimana cara mendapatkan perkiraan asimptotik menggunakan pendekatan ini. $s = \lfloor\frac{\delta}{b}\rfloor$ $b$ $s$

Yuval Filmus
sumber

Terima kasih atas jawabannya! Saya mencoba pendekatan optimasi yang Anda sarankan, tetapi tidak dapat memperoleh perkiraan yang baik.

Atau Meir

Hai Yuval, setelah beberapa pekerjaan lagi, tampaknya pendekatan optimasi ini menghasilkan solusi. Sayangnya, dalam kasus ini juga, kesalahan berkurang hanya invers-logaritma dalam jumlah tebakan. Terima kasih!

Atau Meir

7

$X$ $N$ $N+H(X)$ $1/2$

Ini adalah bagian dari alasan mengapa orang pergi untuk memeriksa entropi Renyi.

Kodlu
sumber

Menebak nilai entropi rendah dalam beberapa upaya

Jawaban: