Nomor acak seragam palsu: Lebih merata daripada data seragam asli

Saya mencari cara untuk menghasilkan angka acak yang tampaknya terdistribusi seragam - dan setiap tes akan menunjukkan mereka seragam - kecuali bahwa mereka lebih merata daripada data seragam sejati .

Masalah yang saya miliki dengan tebusan seragam yang "benar" adalah bahwa mereka kadang-kadang akan berkelompok. Efek ini lebih kuat pada ukuran sampel yang rendah. Secara kasar mengatakan: ketika saya menggambar dua seragam Uniform di U [0; 1], kemungkinan sekitar 10% bahwa mereka berada dalam kisaran 0,1, dan 1% bahwa mereka berada dalam 0,01.

Jadi saya mencari cara yang baik untuk menghasilkan angka acak yang lebih merata daripada tebusan seragam .

Contoh penggunaan kasus: katakan saya sedang melakukan permainan komputer, dan saya ingin menempatkan harta secara acak di peta (tidak peduli tentang hal lain). Saya tidak ingin harta itu berada di satu tempat, itu harus ada di seluruh peta. Dengan tebusan yang seragam, jika saya menempatkan, katakanlah, 10 objek, kemungkinannya tidak serendah itu sehingga ada 5 atau lebih yang sangat dekat satu sama lain. Ini bisa memberi satu pemain keunggulan dibanding yang lain. Pikirkan kapal penyapu ranjau, kemungkinan (walaupun rendah, jika ada cukup ranjau) adalah bahwa Anda benar-benar beruntung dan menang dengan satu klik.

Pendekatan yang sangat naif untuk masalah saya adalah membagi data ke dalam kisi. Selama jumlahnya cukup besar (dan memiliki faktor), seseorang dapat menerapkan keseragaman ekstra dengan cara ini. Jadi alih-alih menggambar 12 variabel acak dari U [0; 1], saya bisa menggambar 6 dari U [0; .5] dan 6 dari U [0,5; 1], atau 4 dari U [0; 1/3] + 4 dari U [1/3; 2/3] + 4 dari U [2/3; 1].

Apakah ada cara yang lebih baik untuk menyamakan seragam ini? Mungkin hanya bekerja untuk batch acak (ketika menggambar satu acak, saya jelas harus mempertimbangkan seluruh jajaran). Secara khusus, saya dapat mengocok catatan lagi setelah itu (jadi bukan yang pertama dari yang ketiga).

Bagaimana kalau dilakukan secara bertahap? Jadi yang pertama ada di U [0; 1], lalu dua dari masing-masing bagian, satu dari setiap ketiga, satu dari masing-masing keempat? Apakah ini sudah diselidiki, dan seberapa bagus itu? Saya mungkin harus berhati-hati untuk menggunakan generator yang berbeda untuk x dan y untuk tidak membuat mereka berkorelasi (xy pertama akan selalu di bagian bawah, yang kedua di bagian kiri dan ketiga di bawah, yang ketiga di tengah ketiga dan ketiga atas. .. jadi setidaknya beberapa permutasi bin acak juga diperlukan .. dan dalam jangka panjang, itu akan terlalu merata, kurasa.

Sebagai node samping, apakah ada tes yang terkenal apakah beberapa distribusi terlalu merata untuk benar-benar seragam? Jadi menguji "true uniform" vs. "seseorang mengacaukan data dan mendistribusikan item lebih merata". Jika saya ingat dengan benar, Statistik Hopkins dapat mengukur ini, tetapi bisakah itu digunakan untuk pengujian juga? Juga agak KS-Test terbalik: jika deviasi terbesar di bawah ambang batas yang diharapkan, data terlalu merata?

Ya , ada banyak cara untuk menghasilkan urutan angka yang lebih merata daripada seragam acak. Bahkan, ada seluruh bidang yang didedikasikan untuk pertanyaan ini; itu adalah tulang punggung quasi-Monte Carlo (QMC). Di bawah ini adalah tur singkat dari dasar-dasar absolut.

Mengukur keseragaman

Ada banyak cara untuk melakukan ini, tetapi cara yang paling umum memiliki rasa geometris yang kuat, intuitif. Misalkan kita prihatin dengan menghasilkan poin x 1 , x 2 , … , x n di [ 0 , 1 ] d untuk beberapa bilangan bulat positif d . Tetapkan mana adalah persegi panjang di sedemikian rupa sehingga$n$$x_1,x_2,\ldots,x_n$$[0,1]^d$$d$R [ a 1 , b 1 ] × ⋯ × [ a d , b d

$$\newcommand{\I}{\mathbf 1} D_n := \sup_{R \in \mathcal R}\,\left|\frac{1}{n}\sum_{i=1}^n \I_{(x_i \in R)} - \mathrm{vol}(R)\right| \>,$$ $R$$[a_1, b_1] \times \cdots \times [a_d, b_d]$ 0 ≤ a i ≤ b i ≤ 1 R R R v o l ( R ) = ∏ i ( b i - a i$[0,1]^d$$0 \leq a_i \leq b_i \leq 1$ dan adalah himpunan semua persegi panjang tersebut. Istilah pertama di dalam modulus adalah proporsi titik "yang diamati" di dalam dan istilah kedua adalah volume , .$\mathcal R$$R$$R$$\mathrm{vol}(R) = \prod_i (b_i - a_i)$

Kuantitas sering disebut ketidaksesuaian atau perbedaan ekstrim dari himpunan titik . Secara intuitif, kita menemukan kotak "terburuk" mana proporsi poin menyimpang paling banyak dari apa yang kita harapkan di bawah keseragaman yang sempurna. ( x i ) $D_n$$(x_i)$$R$

Ini sulit dalam praktik dan sulit untuk dihitung. Sebagian besar, orang lebih suka bekerja dengan perbedaan bintang , Satu-satunya perbedaan adalah set di mana supremum diambil. Ini adalah himpunan persegi panjang berlabuh (pada titik asal), yaitu, di mana .A a 1 = a 2 = ⋯ = a d =

$$D_n^\star = \sup_{R \in \mathcal A} \,\left|\frac{1}{n}\sum_{i=1}^n \I_{(x_i \in R)} - \mathrm{vol}(R)\right| \>.$$ $\mathcal A$$a_1 = a_2 = \cdots = a_d = 0$

Lemma : untuk semua , . Bukti . Tangan kiri terikat jelas karena . Batas kanan mengikuti karena setiap dapat dikomposisikan melalui serikat pekerja, persimpangan dan pelengkap tidak lebih dari persegi panjang berlabuh (yaitu, dalam ).$D_n^\star \leq D_n \leq 2^d D_n^\star$d A ⊂ R R ∈ R 2 d $n$$d$
$\mathcal A \subset \mathcal R$$R \in \mathcal R$$2^d$$\mathcal A$

Jadi, kita melihat bahwa bintang dan adalah ekuivalen dalam arti bahwa jika satu kecil seperti tumbuh, yang lain akan juga. Berikut adalah gambar (kartun) yang menunjukkan persegi panjang kandidat untuk setiap perbedaan.D ⋆ n$D_n$$D_n^\star$$n$

Contoh urutan "baik"

Urutan dengan perbedaan bintang yang dapat dibuktikan rendah, bintang sering disebut, tidak mengejutkan, urutan perbedaan yang rendah .$D_n^\star$

van der Corput . Ini mungkin contoh paling sederhana. Untuk , urutan van der Corput dibentuk dengan memperluas integer dalam biner dan kemudian "mencerminkan digit" di sekitar titik desimal. Secara lebih formal, ini dilakukan dengan fungsi invers radikal di basis , mana dan adalah digit dalam basis ekspansi . Fungsi ini membentuk dasar untuk banyak urutan lainnya juga. Sebagai contoh, dalam biner adalah dan seterusnyai b ϕ b ( i ) = ∞ ∑ k = 0 a k b - k - $d=1$$i$$b$i = ∑ ∞ k = 0 a k b k a k b i 41 101001 a 0 = 1 a 1 = 0 a 2 = 0 a 3 = 1 a 4 = 0 a 5 = 1 x 41 = ϕ 2 ( 41 ) =

$$\newcommand{\rinv}{\phi} \rinv_b(i) = \sum_{k=0}^\infty a_k b^{-k-1} \>,$$ $i = \sum_{k=0}^\infty a_k b^k$$a_k$$b$$i$$41$$101001$$a_0 = 1$ , , , , dan . Oleh karena itu, titik ke-41 dalam urutan van der Corput adalah .$a_1 = 0$$a_2 = 0$$a_3 = 1$$a_4 = 0$$a_5 = 1$$x_{41} = \rinv_2(41) = 0.100101\,\text{(base 2)} = 37/64$

Perhatikan bahwa karena bit paling tidak signifikan dari berosilasi antara dan , poin untuk odd ada di , sedangkan poin untuk even berada di .0 1 x i i [ 1 / 2 , 1 ) x i i ( 0 , 1 / 2 $i$$0$$1$$x_i$$i$$[1/2,1)$$x_i$$i$$(0,1/2)$

Urutan halton . Di antara yang paling populer dari urutan perbedaan rendah klasik, ini adalah ekstensi dari urutan van der Corput ke beberapa dimensi. Biarkan menjadi prime terkecil. Kemudian, th titik dari berdimensi urutan Halton adalah Untuk low ini berfungsi dengan baik, tetapi memiliki masalah di dimensi yang lebih tinggi . j i x i d x i = ( ϕ p 1 ( i ) , ϕ p 2 ( i ) , … , ϕ p d ( i ) $p_j$$j$$i$$x_i$$d$

$$x_i = (\rinv_{p_1}(i), \rinv_{p_2}(i),\ldots,\rinv_{p_d}(i)) \>.$$ $d$

Urutan memenuhi . Mereka juga baik karena mereka dapat diperluas dalam hal konstruksi titik tidak tergantung pada pilihan a priori dari panjang urutan .$D_n^\star = O(n^{-1} (\log n)^d)$$n$

Urutan Hammersley . Ini adalah modifikasi yang sangat sederhana dari urutan Halton. Kami menggunakan Mungkin secara mengejutkan, keuntungannya adalah mereka memiliki perbedaan bintang yang lebih baik, .D ⋆ n = O ( n - 1 ( log n ) d - 1

$$x_i = (i/n, \rinv_{p_1}(i), \rinv_{p_2}(i),\ldots,\rinv_{p_{d-1}}(i)) \>.$$ $D_n^\star = O(n^{-1}(\log n)^{d-1})$

Berikut adalah contoh dari urutan Halton dan Hammersley dalam dua dimensi.

Urutan Halton yang diijinkan oleh Faure . Serangkaian permutasi khusus (ditetapkan sebagai fungsi ) dapat diterapkan pada ekspansi digit untuk setiap saat memproduksi urutan Halton. Ini membantu memperbaiki (sampai taraf tertentu) masalah yang disinggung dalam dimensi yang lebih tinggi. Setiap permutasi memiliki properti yang menarik dengan menjaga dan sebagai titik tetap.a k i 0 b - $i$$a_k$$i$$0$$b-1$

Aturan kisi . Biarkan menjadi bilangan bulat. Ambil mana menunjukkan bagian pecahan dari . Pilihan yang bijaksana dari nilai menghasilkan properti keseragaman yang baik. Pilihan yang buruk dapat menyebabkan urutan buruk. Mereka juga tidak dapat diperluas. Berikut ini dua contoh. x i = ( i / n , { i β 1 / n } , … , { i β d - 1 / n } $\beta_1, \ldots, \beta_{d-1}${ y } y

$$x_i = (i/n, \{i \beta_1 / n\}, \ldots, \{i \beta_{d-1}/n\}) \>,$$ $\{y\}$$y$$\beta$

$(t,m,s)$ jaring . jaring dalam basis adalah sekumpulan titik sedemikian rupa sehingga setiap persegi panjang volume di berisi poin. Ini adalah bentuk keseragaman yang kuat. kecil adalah teman Anda, dalam hal ini. Urutan Halton, Sobol 'dan Faure adalah contoh dari jaring . Ini cocok untuk pengacakan melalui pengacakan. Perebutan acak (dilakukan dengan benar) dari jaring menghasilkan jaring lain . Proyek MinT menyimpan koleksi sekuens semacam itu.$(t,m,s)$$b$$b^{t-m}$$[0,1]^s$$b^t$$t$$(t,m,s)$$(t,m,s)$$(t,m,s)$

Pengacakan sederhana: Rotasi Cranley-Patterson . Biarkan menjadi urutan titik. Biarkan . Kemudian poin didistribusikan secara seragam dalam .$x_i \in [0,1]^d$$U \sim \mathcal U(0,1)$$\hat x_i = \{x_i + U\}$$[0,1]^d$

Berikut adalah contoh dengan titik-titik biru sebagai titik-titik asli dan titik-titik merah menjadi titik-titik yang dirotasi dengan garis-garis yang menghubungkannya (dan ditunjukkan melilit, jika perlu).

Urutan terdistribusi secara seragam . Ini adalah gagasan keseragaman yang bahkan lebih kuat yang terkadang ikut bermain. Misalkan menjadi urutan titik dalam dan sekarang bentuk blok tumpang tindih dengan ukuran untuk mendapatkan urutan . Jadi, jika , kita ambil maka , dll. Jika, untuk setiap , , maka dikatakan sepenuhnya terdistribusi secara merata . Dengan kata lain, urutan menghasilkan satu set poin apa pun$(u_i)$$[0,1]$$d$$(x_i)$$s = 3$$x_1 = (u_1,u_2,u_3)$$x_2 = (u_2,u_3,u_4)$ $s \geq 1$$D_n^\star(x_1,\ldots,x_n) \to 0$$(u_i)$dimensi yang memiliki properti diinginkan .$D_n^\star$

Sebagai contoh, urutan van der Corput tidak sepenuhnya terdistribusi secara merata karena untuk , titik berada di dalam kotak dan titik dalam . Oleh karena itu tidak ada titik dalam kuadrat yang menyiratkan bahwa untuk , untuk semua .$s = 2$$x_{2i}$$(0,1/2) \times [1/2,1)$$x_{2i-1}$$[1/2,1) \times (0,1/2)$$(0,1/2) \times (0,1/2)$$s=2$$D_n^\star \geq 1/4$$n$

Referensi standar

The Niederreiter (1992) monografi dan Fang dan Wang (1994) teks tempat untuk pergi untuk eksplorasi lebih lanjut.

Salah satu cara untuk melakukan ini adalah dengan menghasilkan angka acak yang seragam, kemudian menguji "kedekatan" menggunakan metode apa pun yang Anda suka dan kemudian menghapus item acak yang terlalu dekat dengan orang lain dan memilih satu set seragam acak untuk menebusnya.

Akankah distribusi seperti itu lulus setiap ujian keseragaman? Saya harap tidak! Ini tidak lagi terdistribusi secara seragam, sekarang beberapa distribusi lainnya.

Salah satu aspek probabilitas yang tidak intuitif adalah bahwa peluang itu tidak jelas. Ada lebih banyak data acak yang berjalan daripada yang diperkirakan orang. Saya pikir Tversky melakukan penelitian tentang hal ini (dia meneliti terlalu banyak, sehingga sulit untuk diingat).

Ini dikenal sebagai proses titik poisson "hard-core" - dinamakan demikian oleh Brian Ripley pada 1970-an; yaitu Anda ingin menjadi acak, tetapi Anda tidak ingin ada poin yang terlalu dekat. "Hard-core" dapat dibayangkan sebagai zona penyangga di mana titik-titik lain tidak dapat mengganggu.

Bayangkan Anda sedang merekam posisi beberapa mobil di kota - tetapi Anda hanya merekam titik di pusat nominal mobil. Sementara mereka berada di jalan-jalan, tidak ada pasangan titik yang dapat berdekatan karena poin-poinnya dilindungi oleh "inti" dari bodywork - kita akan mengabaikan posisi super potensial di tempat parkir bertingkat :-)

Ada prosedur untuk menghasilkan proses titik tersebut - satu cara adalah hanya untuk menghasilkan poin secara seragam dan kemudian menghapus semua yang terlalu berdekatan!

Untuk beberapa detail tentang proses tersebut, lihat misalnya untuk ini

Sehubungan dengan pembuatan bets sebelumnya, saya akan menghasilkan sejumlah besar set pseudorandom variations, dan kemudian mengujinya dengan tes seperti tes Kolmogorov-Smirnov. Anda akan ingin memilih set yang memiliki nilai p tertinggi (yaitu, ideal). Perhatikan bahwa ini akan lambat, tetapi karena bertambah besar, itu mungkin menjadi kurang perlu. $p \approx 1$$N$

Sehubungan dengan generasi tambahan, Anda pada dasarnya mencari seri dengan autokorelasi yang cukup negatif. Saya tidak yakin apa cara terbaik untuk melakukan itu, karena saya memiliki pengalaman yang sangat terbatas dengan deret waktu, tetapi saya curiga ada algoritma yang ada untuk ini.

Sehubungan dengan tes untuk "terlalu genap", setiap tes untuk apakah sampel mengikuti distribusi tertentu (seperti KS yang disebutkan di atas) akan dilakukan, Anda hanya ingin memeriksa apakah , daripada pendekatan standar. Saya menulis tentang contoh pendekatan alternatif ini di sini: chi-square selalu merupakan tes satu sisi . $p > (1-\alpha)$

Saya akan memformalkan masalah Anda dengan cara ini: Anda ingin distribusi lebih dari sedemikian rupa sehingga densitasnya adalah untuk beberapa mengkuantifikasi tolakan titik. f ( x ) ∝ e ( $[0,1]^n$ k<$f(x) \propto e^{\left(\frac1k\sum_{ij}\lvert x_i-x_j \rvert^{k}\right)^{\frac1k}}$$k<0$

Salah satu cara mudah untuk menghasilkan vektor semacam itu adalah dengan melakukan sampling Gibbs.