Mensimulasikan dadu yang adil dengan dadu yang bias

Mengingat die-sisi bias $N$ , bagaimana angka acak dalam kisaran $[1,N]$ dapat dihasilkan secara seragam? Distribusi probabilitas dari wajah cetakan tidak diketahui, semua yang diketahui adalah bahwa setiap wajah memiliki probabilitas nol dan bahwa distribusi probabilitas adalah sama pada semua lemparan (khususnya, lemparan independen). Ini adalah generalisasi yang jelas dari hasil-hasil yang Adil dengan dadu yang tidak adil .

Menempatkan ini dalam istilah ilmu komputer, kami memiliki oracle yang mewakili die rolls: $D : \mathbb{N} \to [1,N]$ sehingga $p_i = P(D(k)=i)$ tidak nol dan tidak bergantung pada $k$ . Kami sedang mencari algoritma deterministik $A$ yang diparameterisasi oleh $D$ (yaitu $A$ dapat melakukan panggilan ke $D$ ) sehingga $P(A()=i) = 1/N$ . Algoritma harus diakhiri dengan probabilitas 1, yaitu probabilitas bahwa$A$ membuat lebih dari$n$ panggilan ke$D$ harus konvergen ke$0$ sebagai$n\to\infty$ .

Untuk $N=2$ (mensimulasikan koin yang adil dari koin terbalik dengan koin bias), ada algoritma yang terkenal:

• Ulangi "membalik dua kali" sampai dua lemparan muncul dengan hasil yang berbeda ((kepala, ekor) atau (ekor, kepala)). Dengan kata lain, loop untuk $k = 0..\infty$ hingga $D(2k+1) \ne D(2k)$
• Kembalikan 0 jika pasangan terakhir flips adalah (kepala, ekor) dan 1 jika itu (ekor, kepala). Dengan kata lain, kembalikan $D(2k)$ mana $k$ adalah indeks di mana loop dihentikan.

Cara sederhana untuk membuat die tidak bias dari bias adalah dengan menggunakan metode flip unbiasing koin untuk membangun koin adil, dan membangun die adil dengan sampel penolakan, seperti dalam Unbiasing dari urutan . Tetapi apakah ini optimal (untuk nilai generik dari distribusi probabilitas)?

Secara khusus, pertanyaan saya adalah: apa itu algoritma yang membutuhkan jumlah panggilan terkecil yang diharapkan ke oracle ? Jika himpunan nilai harapan yang dapat dicapai terbuka, apa batas bawah dan apa kelas algoritma yang menyatu ke arah batas bawah ini?

Jika keluarga algoritma yang berbeda optimal untuk distribusi probabilitas yang berbeda, mari fokus pada dadu yang hampir adil: Saya mencari algoritma atau keluarga algoritma yang optimal untuk distribusi sehingga $\forall i, \bigl|p_i - 1/N\bigr| \lt \epsilon$ untuk beberapa $\epsilon \gt 0$ .

Makalah berikut menjawab varian dekat dari pertanyaan ini: Konstruksi Efisien dari Urutan Acak yang Tidak Cocok, Elias 1972 .

Pertanyaannya sepertinya ini: Diberikan akses ke sumber independen yang bias ini, menampilkan urutan angka acak dalam (perhatikan perbedaan dari pertanyaan Anda di mana hanya satu simbol output yang diminta). Ketika panjang output yang diinginkan mencapai tak terhingga, "efisiensi" skema dalam makalah (yang tampaknya seperti generalisasi alami von Neumann) menjadi 1 , artinya, saya percaya, bahwa input dengan entropi h dikonversi menjadi sebuah output dari entropi yang mendekati h .$[1,N]$$1$$h$$h$

Pertanyaannya kelihatannya berperilaku jauh lebih baik ketika diutarakan dengan cara ini, daripada meminta satu digit output tunggal, karena, misalnya, jika kita menggambar sampel dan berakhir dengan output dengan banyak informasi (misalnya, semua simbol input N berbeda) , maka kita dapat menggunakan semua informasi itu untuk menghasilkan banyak simbol output, sedangkan dengan pertanyaan seperti yang diungkapkan di sini, setiap informasi di luar yang digunakan untuk menghasilkan satu simbol output akan sia-sia.$N$$N$

Saya percaya bahwa skema berulang kali mengambil menarik, melihat urutannya, dan memetakannya beberapa output atau string kosong. Mungkin ada cara untuk meningkatkan skema untuk pertanyaan Anda dengan melihat awalan dan berhenti jika kami memiliki informasi "cukup" untuk menghasilkan simbol? Saya tidak tahu$N$

Metode yang Anda gambarkan untuk generalisasi. Kami menggunakan bahwa semua permutasi [ 1 .. N ] memiliki kemungkinan yang sama bahkan dengan die bias (karena gulungannya independen). Oleh karena itu, kita dapat terus bergulir sampai kita melihat permutasi seperti gulungan N terakhir dan menghasilkan gulungan terakhir.$N=2$$[1..N]$$N$

Analisis umum rumit; jelas, bagaimanapun, bahwa jumlah gulungan yang diharapkan tumbuh dengan cepat dalam karena probabilitas melihat permutasi pada setiap langkah yang diberikan kecil (dan tidak terlepas dari langkah-langkah sebelum dan sesudah, karenanya rumit). Hal ini lebih besar dari 0 untuk tetap N , bagaimanapun, jadi prosedur berakhir hampir pasti (yaitu dengan probabilitas 1 ).$N$$0$$N$$1$

Untuk fixed kita dapat membangun rantai Markov pada himpunan Parikh-vektor yang berjumlah ≤ N , merangkum hasil dari gulungan N terakhir , dan menentukan jumlah langkah yang diharapkan sampai kita mencapai ( 1 , … , 1 ) untuk pertama kali . Ini cukup karena semua permutasi yang memiliki vektor Parikh sama-sama memungkinkan; rantai dan perhitungannya lebih sederhana dengan cara ini.$N$$\leq N$$N$$(1,\dots,1)$

Asumsikan kita berada dalam keadaan dengan Σ n i = 1 v i ≤ N . Kemudian, probabilitas mendapatkan elemen i (yaitu roll berikutnya adalah i ) selalu diberikan oleh$v=(v_1,\dots,v_N)$$\sum_{i=1}^n v_i \leq N$$i$$i$

.$\qquad\displaystyle \operatorname{Pr}[\text{gain } i] = p_i$

Di sisi lain, kemungkinan menjatuhkan elemen dari sejarah diberikan oleh$i$

$\qquad\displaystyle \operatorname{Pr}_v[\text{drop } i] = \frac{v_i}{N}$

setiap kali (dan 0 sebaliknya) justru karena semua permutasi dengan Parikh-vektor v memiliki kemungkinan yang sama. Probabilitas ini independen (karena gulungan independen), sehingga kami dapat menghitung probabilitas transisi sebagai berikut:$\sum_{i=1}^n v_i = N$$0$$v$

$\qquad\begin{align*} &\operatorname{Pr}[v \to (v_1,\dots,v_j + 1,\dots,v_N)] \\ &\qquad=\begin{cases} \operatorname{Pr}[\text{gain } j] &, \sum v < N \\ 0 &, \text{ else} \end{cases}\;,\\[3ex] &\operatorname{Pr}[v \to (v_1,\dots,v_i - 1, \dots v_j + 1,\dots,v_N)] \\ &\qquad=\begin{cases} 0 &, \sum v < N \lor v_i=0 \lor v_j=N \\ \operatorname{Pr}_v[\text{drop } i] \cdot \operatorname{Pr}[\text{gain } j] &, \text{ else} \end{cases}\;\text{ and}\\[3ex] &\operatorname{Pr}[v \to v] \\ &\qquad=\begin{cases} 0 &, \sum v < N \\ \sum_{v_i \neq 0} \operatorname{Pr}_v[\text{drop } i] \cdot \operatorname{Pr}[\text{gain } i] &, \text{ else} \end{cases}\;; \end{align*}$

semua probabilitas transisi lainnya adalah nol. Keadaan menyerap tunggal adalah , vektor Parikh dari semua permutasi [ 1 .. N ] .$(1,\dots,1)$$[1..N]$

Untuk rantai Markov yang dihasilkan adalah$N=2$

^{[ sumber ]}

dengan jumlah langkah yang diharapkan hingga penyerapan

$\qquad\displaystyle \mathbb{E}\,\text{steps} = 2 p_0 p_1 \cdot 2 + \sum_{i\geq 3} (p_0^{i-1}p_1 + p_1^{i-1}p_0)\cdot i = \frac{1 - p_0 + p_0^2}{p_0-p_0^2}\;,$

gunakan untuk penyederhanaan bahwa . Jika sekarang, seperti yang disarankan, p 0 = $p_1=1-p_0$untuk beberapaϵ∈[0,$p_0 = \frac{1}{2} \pm \epsilon$, lalu$\epsilon \in [0,\frac{1}{2})$

.$\qquad\displaystyle \mathbb{E}\,\text{steps} = \frac{3 + 4\epsilon^2}{1 - 4\epsilon^2}$

Untuk dan distribusi seragam (kasus terbaik) saya telah melakukan perhitungan dengan komputer aljabar²; karena ruang keadaan meledak dengan cepat, nilai yang lebih besar sulit untuk dievaluasi. Hasilnya (dibulatkan ke atas)$N \leq 6$

^{Plot menunjukkan - langkah sebagai fungsi N ; ke kiri biasa dan di sebelah kanan plot logaritmik.$\mathbb{E}\,\text{steps}$$N$}

Pertumbuhan tampaknya eksponensial tetapi nilainya terlalu kecil untuk memberikan perkiraan yang baik.

Adapun stabilitas terhadap gangguan kita dapat melihat situasi untuk N = 3 :$p_i$$N=3$

^{Plot menunjukkan sebagai fungsi dari p 0 dan p 1 ; secara alami, p 2 = 1 - p 0 - p 1 .$\mathbb{E}\,\text{steps}$$p_0$$p_1$$p_2 = 1 - p_0 - p_1$}

Dengan asumsi gambar yang sama untuk lebih besar (kernel crash komputasi hasil simbolik bahkan untuk N = 4 ), jumlah langkah yang diharapkan tampaknya cukup stabil untuk semua tetapi pilihan yang paling ekstrem (hampir semua atau tidak ada massa di beberapa p i ).$N$$N=4$$p_i$

Sebagai perbandingan, simulasi sebuah koin -biased (misalnya dengan menetapkan hasil die ke 0 dan 1 secara merata mungkin), menggunakan ini untuk mensimulasikan sebuah koin dan akhirnya melakukan bit-bijaksana penolakan pengambilan sampel memerlukan paling$\epsilon$$0$$1$

$\qquad\displaystyle 2\lceil \log N \rceil \cdot \frac{3 + 4\epsilon^2}{1 - 4\epsilon^2}$

gulungan mati dalam harapan - Anda mungkin harus tetap dengan itu.

1. Karena rantai menyerap dalam tepi yang ditunjukkan dalam warna abu-abu tidak pernah dilalui dan tidak mempengaruhi perhitungan. Saya memasukkannya hanya untuk tujuan kelengkapan dan ilustrasi.$(11)$
2. Implementasi dalam Mathematica 10 ( Notebook , Bare Source ); maaf, itu yang saya tahu untuk masalah seperti ini.

Hanya komentar singkat tentang kasus . Ambil sejumlah besar m , dan sampel m lemparan dadu. Jika Anda mendapat k kepala maka Anda dapat mengekstrak log ($N = 2$$m$$m$$k$ bit. Dengan asumsi die yangpbias, jumlah rata-rata informasi m Σ k=0pk(1-p)m-k ($\log \binom{m}{k}$$p$ Untuk mendapatkan perkiraan ini, menggunakan fakta bahwa variabel binomial terkonsentrasi di sekitark=pmbersama-sama dengan estimasilog (

Anda dapat menggunakan metode yang sama untuk umum , dan Anda mungkin akan mendapatkan H yang sama ( → p ) . Algoritma ini hanya optimal dalam batas, dan mungkin ada algoritma yang mencapai batas lebih cepat dari ini. Bahkan, saya lalai menghitung kecepatan konvergensi - ini mungkin latihan yang menarik.$N$$H(\vec{p})$

Saya akan membahayakan jawaban berikut.

Kasus spesifik 2 yang Anda sebutkan di atas adalah kasus spesifik ekspansi (di mana p adalah prob kepala dan q prob ekor) yang memberi Anda istilah 2 p q Ini berarti Anda bisa mendapatkan p q untuk satu kasus dan q p untuk kasus lain. Anda perlu mengulangi pengambilan sampel sampai Anda melihat p q atau q p (head-tail atau tail-head) Menggunakannya sebagai simulasi, Anda akan memberikan probabilitas yang sama.$(p + q)^2$$p$$q$$2pq$$pq$$qp$$pq$$qp$

$N=3$$(p + q + r)^3$$pqr$$q$$p$$r$

$N=3$$pqr$

.

Tambahan:

Ini membuat saya berpikir tentang ide sampel sederhana banyak untuk memperkirakan probabilitas setiap hasil dadu. Dalam kasus paling sederhana dari model satu lapisan tanpa lapisan tersembunyi (model yang diketahui), kita dapat menentukan batas untuk menyimpulkan bahwa estimasi tersebut menyatu dengan cepat. Sebenarnya Chernoff terikat menunjukkan kepada kita bahwa kesalahan turun secara eksponensial karena pengambilan sampel meningkat (linear).

$\prod_{i=1}^{i=n} p_i$

Namun demikian, pendekatan ini merupakan jawaban untuk cita rasa yang berbeda. Pertanyaannya meminta jaminan ketidakberpihakan yang sempurna dengan biaya pengambilan sampel yang berpotensi besar (meskipun masalah rendah). Pendekatan ini hanya menggunakan sampling terbatas dengan parameter kepercayaan terbatas. Jadi saya tidak berpikir pendekatan ini cocok untuk pertanyaan ini meskipun sangat menarik.