Bagaimana cara menghasilkan nilai yang didistribusikan secara seragam dan diurutkan dalam suatu interval secara efisien?

Katakanlah saya ingin menghasilkan satu set angka acak dari interval (a, b). Urutan yang dihasilkan juga harus memiliki properti yang disortir. Saya dapat memikirkan dua cara untuk mencapai ini.

Membiarkan nmenjadi panjang urutan yang akan dihasilkan.

Algoritma 1:

Let `offset = floor((b - a) / n)`
for i = 1 up to n:
   generate a random number r_i from (a, a+offset)
   a = a + offset
   add r_i to the sequence r

Algoritma 2:

for i = 1 up to n:
    generate a random number s_i from (a, b)
    add s_i to the sequence s
sort(r)

Pertanyaan saya adalah, apakah algoritma 1 menghasilkan urutan yang sebagus yang dihasilkan oleh algoritma 2?

random-generation ultrajohn
sumber

BTW sangat mudah untuk menghasilkan daftar angka acak yang diurut R. Dalam rangka untuk menghasilkan array

set

angka acak pada interval seragam

, kode berikut bekerja: .

k

$k$

n

$n$

[a, b]

$[a, b]$ rand_array <- replicate(k, sort(runif(n, a, b))

RobertF

Jawaban:

Algoritma pertama gagal buruk karena dua alasan:

Mengambil lantai dapat menguranginya secara drastis. Memang, ketika , itu akan nol, memberi Anda satu set yang nilainya sama! $(a-b)/n$ $b-a \lt n$
Ketika Anda tidak mengambil lantai, nilai-nilai yang dihasilkan terlalu merata . Misalnya, dalam setiap sampel acak sederhana dari variasi seragam iid (katakanlah antara dan ), ada peluang bahwa yang terbesar tidak akan dalam interval atas dari ke . Dengan algoritma 1, ada $n$ $a=0$ $b=1$ $(1-1/n)^n\approx 1/e\approx 37\%$ $1-1/n$ $1$ $100\%$ kemungkinan maksimum akan berada dalam interval itu. Untuk beberapa tujuan, super-keseragaman ini baik, tetapi secara umum itu adalah kesalahan yang mengerikan karena (a) banyak statistik akan hancur tetapi (b) bisa sangat sulit untuk menentukan mengapa.
Jika Anda ingin menghindari penyortiran, sebagai gantinya buat varian terdistribusi eksponensial bebas. Normalisasi jumlah kumulatif mereka ke kisaran dengan membaginya dengan jumlah. Jatuhkan nilai terbesar (yang akan selalu menjadi ). Skala ulang ke kisaran . $n+1$ $(0,1)$ $1$ $(a,b)$

Histogram dari ketiga algoritma ditampilkan. (Masing-masing menggambarkan hasil kumulatif dari set independen nilai masing-masing.) Kurangnya variasi yang terlihat dalam histogram untuk Algoritma 1 menunjukkan masalah di sana. Variasi dalam dua algoritma lainnya persis seperti yang diharapkan - dan apa yang Anda butuhkan dari generator angka acak. $1000$ $n=100$

Untuk banyak lagi (menghibur) cara untuk mensimulasikan variasi seragam independen, lihat Mensimulasikan undian dari Distribusi Seragam menggunakan undian dari Distribusi Normal .

Gambar: histogram

Berikut adalah Rkode yang menghasilkan gambar.

b <- 1
a <- 0
n <- 100
n.iter <- 1e3

offset <- (b-a)/n
as <- seq(a, by=offset, length.out=n)
sim.1 <- matrix(runif(n.iter*n, as, as+offset), nrow=n)
sim.2 <- apply(matrix(runif(n.iter*n, a, b), nrow=n), 2, sort)
sim.3 <- apply(matrix(rexp(n.iter*(n+1)), nrow=n+1), 2, function(x) {
  a + (b-a) * cumsum(x)[-(n+1)] / sum(x)
})

par(mfrow=c(1,3))
hist(sim.1, main="Algorithm 1")
hist(sim.2, main="Algorithm 2")
hist(sim.3, main="Exponential")

whuber
sumber

Apa pendapat Anda tentang algoritma (berdasarkan statistik urutan peringkat) dalam jawaban saya? ;-)

Memiliki QUIT - Anony-Mousse

@Anony Ini adalah versi yang kurang efisien dari algoritma saya 3. (Sepertinya Anda melibatkan banyak penyetelan ulang yang tidak perlu.) Anda menghasilkan variasi eksponensial dengan mengambil log seragam, yang merupakan standar.

whuber

Algoritma pertama menghasilkan angka terlalu merata

Lihat juga seri perbedaan rendah .

$[0;1]$

(Seperti yang ditunjukkan, ini mungkin properti yang diinginkan misalnya untuk stratifikasi. Serangkaian perbedaan rendah seperti Halton dan Sobel memang memiliki kasus penggunaannya.)

Pendekatan yang tepat tetapi mahal (untuk nilai nyata)

... adalah menggunakan nomor acak yang didistribusikan beta. Statistik urutan peringkat dari distribusi seragam adalah beta. Anda dapat menggunakan ini untuk menggambar secara acak yang terkecil , lalu yang terkecil kedua, ... ulangi.

$[0;1]$ $\text{Beta}[1,n]$ $n$ $1-X\sim \text{Beta}[n, 1]$ $-\ln (1-X)\sim \text{Exponential}[n]$ $\frac{-\ln(U[0;1])}{n}$

\begin{aligned} - \ln (1 - x) & = \frac{- \ln (1 - u)}{n} \\ 1 - x & = u^{\frac{1}{n}} \\ x & = 1 - u^{\frac{1}{n}} \end{aligned}

$\begin{align*} -\ln (1-x) &= \frac{-\ln(1-u)}{n} \\ 1-x &= u^\frac{1}{n} \\ x &= 1 - u^\frac{1}{n} \end{align*}$

Yang menghasilkan algoritma berikut:

x = a
for i in range(n, 0, -1):
    x += (b-x) * (1 - pow(rand(), 1. / i))
    result.append(x)

Mungkin ada ketidakstabilan numerik yang terlibat, dan komputasi powdan pembagian untuk setiap objek mungkin ternyata lebih lambat daripada penyortiran.

Untuk nilai integer Anda mungkin perlu menggunakan distribusi yang berbeda.

Penyortiran sangat murah, jadi gunakan saja

$O(n \log n)$

Memiliki QUIT - Anony-Mousse
sumber

Mungkin ada alasan untuk menghindari penyortiran. Salah satunya adalah ketika Anda ingin menghasilkan sejumlah besar variasi acak, begitu banyak sehingga rutin semacam standar tidak dapat mengatasinya.

whuber

Saya pikir masalah numerik dengan penjumlahan menggunakan matematika floating point menjadi masalah jauh lebih awal. (Dan masalah dengan pola siklik dalam angka acak semu!) Cukup mudah untuk mengukur pendekatan penyortiran ke terabyte, dan ke exabytes pada sistem terdistribusi.

Memiliki QUIT - Anony-Mousse

10^{12}

$10^{12}$

Ok, tidak harus menyimpannya adalah argumen. Tetapi kemudian Anda akan membutuhkan pendekatan saya, varian 3 Anda menggunakan jumlah kumulatif tidak akan berfungsi.

Memiliki QUIT - Anony-Mousse

Itu adalah poin yang sangat bagus. Sekarang saya melihat kelebihan perhitungan ekstra! (+1)

whuber

Ini juga tergantung pada apa yang Anda lakukan dengan angka acak. Untuk metode integrasi numerik masalah satu (ketika dikoreksi dengan melepaskan operator lantai) akan menghasilkan set titik superior. Apa yang Anda lakukan adalah suatu bentuk pengambilan sampel bertingkat dan memiliki keuntungan bahwa ia menghindari penggumpalan. misalnya, tidak mungkin mendapatkan semua nilai Anda dalam rentang 0 (ba) / n. Yang mengatakan untuk aplikasi lain ini bisa sangat buruk, itu tergantung pada apa yang ingin Anda lakukan dengannya.

pengguna67054
sumber

+1 Saya pikir ini adalah kontribusi yang berguna untuk pertanyaan, terutama dengan mengkarakterisasi Algoritma 1 dalam hal stratifikasi.

whuber