Mensimulasikan probabilitas 1 dari 2 ^ N dengan bit acak kurang dari N

Katakanlah saya perlu mensimulasikan distribusi diskrit berikut:

P (X = k) = {\begin{cases} \frac{1}{2^{N}}, & if k = 1 \\ 1 - \frac{1}{2^{N}}, & if k = 0 \end{cases}

$P(X = k) = \begin{cases} \frac{1}{2^N}, & \text{if $k = 1$} \\ 1 - \frac{1}{2^N}, & \text{if $k = 0$} \end{cases}$

Cara yang paling jelas adalah menggambar bit acak $N$ dan memeriksa apakah semuanya sama dengan $0$ (atau $1$ ). Namun, kata teori informasi

\begin{aligned} S & = - \sum_{i} P_{i} \log P_{i} \\ = - \frac{1}{2^{N}} \log \frac{1}{2^{N}} - (1 - \frac{1}{2^{N}}) \log (1 - \frac{1}{2^{N}}) \\ = \frac{1}{2^{N}} \log 2^{N} + (1 - \frac{1}{2^{N}}) \log \frac{2^{N}}{2^{N} - 1} \\ \to 0 \end{aligned}

$\begin{align} S & = - \sum_{i} P_i \log{P_i} \\ & = - \frac{1}{2^N} \log{\frac{1}{2^N}} - \left(1 - \frac{1}{2^N}\right) \log{\left(1 - \frac{1}{2^N}\right)} \\ & = \frac{1}{2^N} \log{2^N} + \left(1 - \frac{1}{2^N}\right) \log{\frac{2^N}{2^N - 1}} \\ & \rightarrow 0 \end{align}$

Jadi jumlah minimum bit acak yang dibutuhkan benar-benar berkurang karena $N$ menjadi besar. Bagaimana ini mungkin?

Harap asumsikan bahwa kami menjalankan pada komputer di mana bit adalah satu-satunya sumber keacakan Anda, jadi Anda tidak bisa hanya melemparkan koin bias.

algorithms information-theory randomness pseudo-random-generators entropy nalzok
sumber

Ini terkait erat dengan teori pengkodean dan kompleksitas Kolmogorov, jika Anda mencari kata kunci untuk menggali lebih dalam. Teknik penghitungan berjalan berulang dengan bit yang sama yang disebutkan oleh DW di bawah ini banyak muncul - catatan kuliah ini menyentuh contohnya people.cs.uchicago.edu/~fortnow/papers/kaikoura.pdf

Brian Gordon

Wow, pertanyaan bagus! Biarkan saya mencoba menjelaskan resolusi. Itu akan mengambil tiga langkah berbeda.

Hal pertama yang perlu diperhatikan adalah bahwa entropi lebih difokuskan pada jumlah rata - rata bit yang dibutuhkan per undian, bukan jumlah maksimum bit yang dibutuhkan.

Dengan prosedur pengambilan sampel Anda, jumlah maksimum bit acak yang dibutuhkan per imbang adalah $N$ bit, tetapi rata-rata jumlah bit yang diperlukan adalah 2 bit (rata-rata dari distribusi geometris dengan $p=1/2$ ) - ini karena ada $1/2$ probabilitas bahwa Anda hanya perlu 1 bit (jika bit pertama ternyata 1), a $1/4$ probabilitas bahwa Anda hanya perlu 2 bit (jika dua bit pertama berubah menjadi 01), seorang $1/8$ probabilitas bahwa Anda hanya membutuhkan 3 bit (jika tiga bit pertama berubah menjadi 001), dan seterusnya.

Hal kedua yang perlu diperhatikan adalah bahwa entropi tidak benar-benar menangkap jumlah rata-rata bit yang diperlukan untuk undian tunggal. Sebaliknya, entropi menangkap jumlah bit diamortisasi yang diperlukan untuk sampel $m$ iid menarik dari distribusi ini. Misalkan kita membutuhkan $f(m)$ bit untuk mengambil sampel $m$ ; maka entropi adalah batas $f(m)/m$ sebagai $m \to \infty$ .

Hal ketiga untuk dicatat adalah bahwa, dengan distribusi ini, Anda dapat mencicipi $m$ iid menarik dengan bit yang lebih sedikit dari yang dibutuhkan untuk berulang kali sampel satu hasil imbang. Misalkan Anda secara naif memutuskan untuk menggambar satu sampel (rata-rata mengambil 2 bit acak), lalu menggambar sampel lain (menggunakan rata-rata 2 bit acak lebih banyak), dan seterusnya, hingga Anda mengulangi ini sebanyak $m$ kali. Itu akan membutuhkan sekitar $2m$ bit acak rata-rata.

Tapi ternyata ada cara untuk mengambil sampel dari $m$ draw menggunakan kurang dari $2m$ bit. Sulit dipercaya, tapi itu benar!

Biarkan saya memberi Anda intuisi. Misalkan Anda menuliskan hasil penarikan sampel $m$ , di mana $m$ sangat besar. Maka hasilnya dapat ditentukan sebagai string $m$ -bit. Ini $m$ tali-bit akan kebanyakan 0, dengan beberapa 1 di dalamnya: khususnya, rata-rata akan memiliki sekitar $m/2^N$ 1 ini (bisa lebih atau kurang dari itu, tetapi jika $m$ cukup besar, biasanya jumlah akan dekat dengan itu). Panjang celah antara 1 adalah acak, tetapi biasanya akan berada di suatu tempat di sekitar $2^N$ (Bisa dengan mudah setengah atau dua kali atau bahkan lebih, tetapi dari urutan besarnya). Tentu saja, alih-alih menuliskan seluruh string $m$ -bit, kita dapat menuliskannya lebih ringkas dengan menuliskan daftar panjang kesenjangan - yang membawa semua informasi yang sama, dalam format yang lebih terkompresi. Seberapa ringkas? Yah, kita biasanya membutuhkan sekitar $N$ bit untuk mewakili panjang setiap celah; dan akan ada sekitar $m/2^N$ kesenjangan; jadi kita akan membutuhkan total tentang $mN/2^N$ bit (bisa sedikit lebih banyak, bisa sedikit lebih sedikit, tetapi jika $m$ cukup besar, biasanya akan mendekati itu). Itu jauh lebih pendek daripada a $m$ -bit string.

Dan jika ada cara untuk menuliskan string ini secara ringkas, mungkin tidak akan terlalu mengejutkan jika itu berarti ada cara untuk menghasilkan string dengan jumlah bit acak yang sebanding dengan panjang string. Terutama, Anda secara acak menghasilkan panjang setiap celah; ini sampel dari distribusi geometris dengan $p=1/2^N$ , dan yang dapat dilakukan dengan kasar $\sim N$ bit acak rata-rata (tidak $2^N$ ). Anda akan membutuhkan sekitar $m/2^N$ iid menarik dari distribusi geometrik ini, jadi Anda akan membutuhkan total sekitar $\sim Nm/2^N$ bit acak. (Ini bisa menjadi faktor konstan kecil yang lebih besar, tetapi tidak terlalu besar.) Dan, perhatikan bahwa ini jauh lebih kecil dari $2m$ bit.

Jadi, kita dapat mencicipi $m$ iid menarik dari distribusi Anda, hanya menggunakan $f(m) \sim Nm/2^N$ bit acak (kira-kira). Ingat bahwa entropi adalah $\lim_{m \to \infty} f(m)/m$ . Jadi ini berarti bahwa Anda harus mengharapkan entropi untuk menjadi (kira-kira) $N/2^N$ . Itu sedikit keluar, karena perhitungan di atas tidak jelas dan kasar - tetapi mudah-mudahan itu memberi Anda beberapa intuisi mengapa entropi itu seperti apa adanya, dan mengapa semuanya konsisten dan masuk akal.

DW
sumber

Wow, jawaban yang bagus! Tetapi dapatkah Anda menguraikan mengapa pengambilan sampel dari distribusi geometrik dengan

membutuhkan

bit rata-rata? Saya tahu variabel acak seperti itu akan memiliki rata-rata

, jadi dibutuhkan rata-rata

bit untuk menyimpan, tapi saya kira ini tidak berarti Anda dapat menghasilkan satu dengan

bit.

p = \frac{1}{2^{N}}

$p=\frac{1}{2^N}$

N

$N$

2^{N}

$2^N$

N

$N$

N

$N$

nalzok

@nalzok, Pertanyaan yang wajar! Bisakah Anda menanyakan hal itu sebagai pertanyaan terpisah? Saya bisa melihat bagaimana melakukannya, tetapi agak berantakan untuk mengetik sekarang. Jika Anda bertanya, mungkin seseorang akan menjawab lebih cepat daripada saya. Pendekatan yang saya pikirkan mirip dengan pengkodean aritmatika. Tentukan

(di mana

adalah rv geometrik), kemudian hasilkan bilangan acak

dalam interval

, dan temukan

sedemikian rupa sehingga

q_{i} = Pr [X \leq i]

$q_i = \Pr[X\le i]$

X

$X$

r

$r$

[0, 1)

$[0,1)$

i

$i$

q_{i} \leq r < q_{i + 1}

$q_i \le r < q_{i+1}$ . Jika Anda menuliskan bit-bit dari binary expension

satu per satu, biasanya setelah menuliskan

akan sepenuhnya ditentukan.

r

$r$

bit

N + O (1)

$N+O(1)$

r

$r$

i

$i$

Jadi pada dasarnya Anda menggunakan metode invers CDF untuk mengubah variabel acak berdistribusi seragam menjadi distribusi sewenang-wenang, dikombinasikan dengan ide yang mirip dengan pencarian biner? Saya perlu menganalisis fungsi kuantil dari suatu distribusi geometris untuk memastikan, tetapi petunjuk ini cukup. Terima kasih!

nalzok

@nalzok, ahh, ya, itu cara yang lebih baik untuk memikirkannya - bagus. Terima kasih telah menyarankan itu. Yup, itulah yang ada dalam pikiran saya.

Mensimulasikan probabilitas 1 dari 2 ^ N dengan bit acak kurang dari N

Jawaban: