Secara akurat menghasilkan varian dari distribusi kuasa hukum diskrit

Apa metode terbaik untuk secara akurat menghasilkan bilangan bulat acak yang didistribusikan sesuai dengan undang-undang kekuasaan? Probabilitas mendapatkan ( ) harus sama dengan dan metode ini harus bekerja dengan baik untuk .$k$$k=1,2,\ldots$$p_k = k^{-\gamma} / \zeta(\gamma)$$\gamma > 1$

Saya bisa melihat dua pendekatan naif:

1. Hitung hingga beberapa sehingga "cukup dekat" dengan 1, lalu buat bilangan bulat sesuai dengan probabilitas ini. Ini tidak akan berfungsi jika mendekati 1 karena harus berukuran besar.$p_k$$k_\text{max}$$\sum_{k=1}^{k_\text{max}}$$\gamma$$k_\text{max}$

2. Gambarlah bilangan real dari distribusi hukum daya berkelanjutan (masalah yang lebih mudah yang saya tahu bagaimana menyelesaikannya) dan bulatkan ke bilangan bulat dengan beberapa cara. Dimungkinkan untuk secara analitik menghitung probabilitas yang tepat untuk memperoleh setiap bilangan bulat dengan metode di atas. Saya dapat menggunakan penolakan untuk memperbaikinya ke (yang juga dapat dihitung asalkan saya dapat mengevaluasi fungsi ). (Ini akan sedikit berbulu karena saya harus membulatkan dengan cara yang saya dapatkan bilangan bulat dengan probabilitas lebih tinggi dari untuk lebih besar dari beberapa nilai kecil, dan menangani kurang dari itu secara terpisah.)$p_k$$\zeta$$p_k$$k$$k$

Apakah ada metode yang lebih baik yang juga akurat (tidak perkiraan)?

Saya pikir (versi yang sedikit dimodifikasi) metode 2 sebenarnya cukup mudah

Menggunakan definisi fungsi distribusi Pareto yang diberikan di Wikipedia

jika Anda mengambil dan maka rasio ke dimaksimalkan pada , yang berarti Anda hanya dapat skala dengan rasio di dan menggunakan sampling penolakan langsung. Tampaknya cukup efisien.$x_m=\frac{1}{2}$$\alpha=\gamma$$p_x$$q_x=F_X(x+\frac{1}{2})-F_X(x-\frac{1}{2})$$x=1$$x=1$

Untuk lebih eksplisit: jika Anda menghasilkan dari Pareto dengan dan dan bulat ke bilangan bulat terdekat (bukan memotong), maka tampaknya mungkin untuk menggunakan sampel penolakan. dengan - setiap nilai dihasilkan dari proses tersebut diterima dengan probabilitas .$x_m=\frac{1}{2}$$\alpha=\gamma$$M = p_1/q_1$$x$$\frac{p_x}{Mq_x}$

( sini sedikit dibulatkan karena saya malas; pada kenyataannya, kecocokan untuk kasus ini akan sedikit berbeda, tetapi tidak cukup untuk terlihat berbeda dalam plot - pada kenyataannya gambar kecil membuatnya terlihat agak terlalu kecil ketika sebenarnya sebagian kecil terlalu besar)$M$

Penyesuaian yang lebih cermat terhadap dan ( untuk beberapa antara 0 dan 1 katakan) mungkin akan meningkatkan efisiensi lebih lanjut, tetapi pendekatan ini cukup baik dalam kasus yang saya mainkan.$x_m$$\alpha$$\alpha=\gamma-a$$a$

Jika Anda dapat memberikan beberapa pengertian tentang kisaran nilai yang khas, saya dapat melihat lebih dekat pada efisiensi di sana.$\gamma$

Metode 1 dapat disesuaikan dengan tepat, juga, dengan melakukan metode 1 hampir selalu, kemudian menerapkan metode lain untuk menangani ekor. Hal yang bisa dilakukan adalah cara yang mungkin sangat cepat.

Misalnya, jika Anda mengambil vektor bilangan bulat dengan panjang 256, dan mengisi , nilai dengan , nilai dengan dan seterusnya hingga - yang hampir akan gunakan seluruh array. Beberapa sel yang tersisa kemudian mengindikasikan untuk pindah ke metode kedua yang menggabungkan berurusan dengan ekor kanan dan juga potongan kecil 'sisa' dari bagian kiri.$\lfloor 256 p_1\rfloor$1$\lfloor 256 p_2\rfloor$2$256 p_i <1$

Sisa kiri mungkin kemudian dilakukan dengan sejumlah pendekatan (bahkan dengan, katakanlah 'kuadratkan histogram' jika itu otomatis, tetapi itu tidak harus seefisien itu), dan ekor kanan kemudian dapat dilakukan dengan menggunakan sesuatu seperti pendekatan accept-reject di atas.

Algoritma dasar melibatkan menghasilkan integer dari 1 hingga 256 (yang hanya membutuhkan 8 bit dari rng; jika efisiensi adalah yang terpenting, operasi bit dapat mengambil yang 'dari atas', meninggalkan sisa dari nomor seragam (yang terbaik adalah dibiarkan sebagai nilai integer yang tidak dinormalkan ke titik ini) dapat digunakan untuk menangani sisa dan ekor kanan jika diperlukan.

Diimplementasikan dengan hati-hati, hal semacam ini bisa sangat cepat. Anda dapat menggunakan nilai dari 256 yang berbeda (mis. mungkin merupakan kemungkinan), tetapi semuanya secara teori sama. Namun, jika Anda mengambil meja yang sangat besar, mungkin tidak ada bit yang tersisa di seragam untuk itu cocok untuk menghasilkan ekor dan Anda membutuhkan nilai seragam kedua di sana (tetapi itu menjadi sangat jarang dibutuhkan, jadi itu tidak banyak. sebuah isu)$2^k$$2^{16}$

Dalam contoh zeta (2) yang sama seperti di atas, Anda akan memiliki nilai 212 1, 26 2, 7 3, 3 4, satu 5dan nilai dari 250-256 akan berurusan dengan sisa. Lebih dari 97% dari waktu Anda menghasilkan salah satu nilai dalam tabel (1-5).

Sejauh yang saya sadar, keadaan seni di undang-undang kekuasaan adalah kertas dengan Clauset, Shalizi dan Newman yang membahas masalah Anda di Lampiran D. Catatan khususnya (di mana adalah menarik dari kuasa hukum terus menerus) mereka berkata:$y$

Pendekatan perkiraan lain untuk menghasilkan bilangan bulat, seperti membulatkan (memotong) nilai y, memberikan hasil yang jauh lebih buruk dan tidak boleh digunakan.

Sebagai alternatif dari jawaban yang diterima, Clauset et al. metode untuk mendapatkan hasil imbang yang akurat dari distribusi kuasa hukum diskrit adalah dengan menggambar acak yang seragam dan kemudian melakukan mana adalah cdf komplementer dari undang-undang kekuatan diskrit. Anda memerlukan fungsi zeta untuk menghitung tetapi hanya harus dikomputasi hingga akurasi tertentu, sehingga dimungkinkan untuk menghasilkan gambar yang memiliki distribusi kekuatan hukum diskrit dengan cara ini. Anda perlu menggunakan metode pembagian dua untuk menyelesaikan persamaan .$r \in [0,1)$$x= P^{-1}(1-r)$$P(x) = \sum_{a=x}^\infty P(X=a)$$P(x)$$P(x) = 1-r$

Karena perhitungan pastinya mahal, metode perkiraan juga diberikan, yaitu mendefinisikan yang tidak persis sama dengan hanya pembulatan nilai dari hukum daya kontinu. Kesalahan perkiraan ini diberikan dalam Persamaan (D.7) dari Clauset et al. dan tergantung pada .