Apakah ada distribusi univariat yang tidak dapat kami sampel?

Kami memiliki beragam metode untuk pembangkitan acak dari distribusi univariat (transformasi terbalik, accept-reject, Metropolis-Hastings, dll.) Dan tampaknya kami dapat mengambil sampel dari setiap distribusi yang valid secara literal - apakah itu benar?

Bisakah Anda memberikan contoh distribusi univariat yang tidak mungkin dihasilkan secara acak? Saya kira contoh di mana itu tidak mungkin tidak ada (?), Jadi katakanlah dengan "tidak mungkin" yang kami maksudkan juga kasus-kasus yang sangat mahal secara komputasi, misalnya yang memerlukan simulasi gaya-kasar seperti menggambar sejumlah besar sampel untuk menerima hanya beberapa dari mereka.

Jika contoh tersebut tidak ada, dapat kita benar-benar membuktikan bahwa kita bisa menghasilkan random menarik dari setiap distribusi valid? Saya hanya ingin tahu apakah ada contoh tandingan untuk ini.

Jika Anda mengetahui fungsi distribusi kumulatif, , maka Anda dapat membalikkannya, baik secara analitik atau numerik, dan menggunakan metode sampling transformasi terbalik untuk menghasilkan sampel acak https://en.wikipedia.org/wiki/Inverse_transform_sampling .$F(x)$

Tentukan . Ini akan menangani distribusi apa pun, baik kontinu, diskrit, atau kombinasi apa pun. Ini selalu dapat diselesaikan secara numerik, dan mungkin secara analitis. Biarkan U menjadi sampel dari variabel acak yang didistribusikan sebagai Seragam [0,1], yaitu, dari generator nomor acak yang seragam [0,1]. Kemudian , didefinisikan seperti di atas, adalah sampel acak dari variabel acak yang memiliki distribusi . F - 1 ( U ) F ( x $F^{-1}(y) = inf(x:F(x) \ge y)$$F^{-1}(U)$$F(x)$

Ini mungkin bukan cara tercepat untuk menghasilkan sampel acak, tetapi ini adalah cara, dengan anggapan bahwa F (x) diketahui.

Jika F (x) tidak diketahui, maka itu cerita yang berbeda.

Ketika distribusi hanya ditentukan oleh fungsi pembangkit momennya atau dengan fungsi karakteristiknya Φ ( t ) = E [ exp { i t X } ] , jarang ditemukan cara menghasilkan dari distribusi tersebut.$\phi(t)=\mathbb{E}[\exp\{tX\}]$$\Phi(t)=\mathbb{E}[\exp\{itX\}]$

Contoh yang relevan dibuat dari distribusi stabil$\alpha$ , yang tidak memiliki bentuk diketahui untuk kepadatan atau cdf, tidak ada fungsi menghasilkan momen, tetapi fungsi karakteristik bentuk tertutup.

Dalam statistik Bayesian, distribusi posterior yang terkait dengan kemungkinan yang sulit diatasi atau hanya set data yang terlalu besar untuk ditampung dalam satu komputer dapat dilihat sebagai tidak mungkin (tepatnya) disimulasikan.

Dengan asumsi Anda merujuk pada distribusi berkelanjutan. Dengan menggunakan transformasi integral probabilitas , Anda dapat mensimulasikan dari setiap distribusi univariat dengan mensimulasikan u ∼ ( 0 , 1 ) dan kemudian mengambil F - 1 ( u ) . Jadi, kita bisa mensimulasikan seragam, maka bagian itu selesai. Satu-satunya hal yang dapat menghalangi simulasi dari F adalah bahwa Anda tidak dapat menghitung invers F - 1 , tetapi ini harus dikaitkan dengan kesulitan komputasi, daripada sesuatu yang teoritis.$F$$u \sim (0,1)$$F^{-1}(u)$$F$$F^{-1}$

${\bf \theta} = (\theta_1,...,\theta_d)$$\theta_j$

Ada beberapa metode untuk memperkirakan sampel dari posterior ini dalam beberapa kasus, tetapi tidak ada metode umum yang tepat saat ini.

$(q_i)_{i=1}^\infty$$P(X=q_i)=0$$i$$\sum_{i=1}^\infty P(X=q_i)=0$$P(X\in \mathbb{Q})=1$

$\mu$$\pi(\mu) = 1$

Bisakah Anda memberikan contoh distribusi univariat yang tidak mungkin dihasilkan secara acak?

$c$$c$

Jika Anda hanya tertarik untuk mengambil sampel variabel acak yang nilainya dapat didekati secara wajar dengan angka floating-point 64-bit, atau Anda memiliki toleransi yang serupa untuk kesalahan hingga dalam nilainya, dan Anda tidak mewakili sampel Anda, mesin Turing bagaimanapun juga. , pertimbangkan ini:

$X \sim \text{Ber}(p)$$p = 1 - c$$0$$1$

$0$$(-∞, c)$$1$$[c, ∞)$$0$$(-∞, 0)$$c$$[0, 1)$$1$$[1, ∞)$$c$$x$$y$-sumbu. Saya tidak yakin yang membuat pengambilan sampel paling sulit, jadi pilih yang paling Anda sukai (-))

katakanlah dengan "tidak mungkin" yang kami maksudkan juga kasus-kasus yang sangat mahal secara komputasi, misalnya yang memerlukan simulasi gaya-kasar seperti menggambar sampel dalam jumlah besar untuk menerima hanya sedikit dari mereka.

Dalam hal ini, jawaban yang jelas tampak jelas:

• $n$$n$
• Cicipi preimage fungsi hash kriptografi (yaitu menghasilkan bitcoin dan break git dan mercurial).
• Cicipi serangkaian strategi Go yang optimal (dengan aturan superko Cina, yang membuat semua game terbatas — sejauh yang saya mengerti).

Sedikit lebih formal: Saya memberi Anda contoh besar masalah NP-complete (atau EXP-complete, dll.) Dan meminta Anda untuk secara seragam mencicipi serangkaian solusi untuk saya.

$\bot$$\mathbb{R}$$-1$$\bot$

Anda dapat dengan mudah memeriksa apakah setiap penugasan kebenaran yang diberikan memenuhi instance SAT saya, dan setelah memeriksa semua yang Anda tahu apakah ada yang melakukannya, maka saya telah menentukan CDF sepenuhnya dengan memberi Anda formula boolean (atau sirkuit), belum mencicipi distribusi yang sesuai. Anda harus pada dasarnya menjadi sesuatu yang setidaknya sekuat oracle SAT-solvability.

Jadi saya memberi Anda nomor yang tidak dapat dihitung yang harus membuang pasir di gigi Anda, dan saya memberi Anda CDF yang lambat untuk dihitung. Mungkin pertanyaan jelas berikutnya untuk ditanyakan adalah seperti ini: apakah ada CDF yang direpresentasikan dalam bentuk yang efisien (misalnya dapat dievaluasi dalam waktu polinomial) sehingga sulit untuk menghasilkan sampel dengan distribusi itu? Saya tidak tahu jawabannya. Saya tidak tahu jawabannya.