Pengambilan sampel yang seragam dari simpleks

29

Saya mencari algoritma untuk menghasilkan array angka acak N, sehingga jumlah angka-angka N adalah 1, dan semua angka berada dalam 0 dan 1. Misalnya, N = 3, titik acak (x, y, z) harus terletak di dalam segitiga:

x + y + z = 1
0 < x < 1
0 < y < 1
0 < z < 1

Idealnya saya ingin setiap titik dalam area memiliki probabilitas yang sama. Jika terlalu sulit, saya bisa membatalkan persyaratan. Terima kasih.

algorithms randomness random-number-generator sampling Ruofeng
sumber

Apa target distribusi? Apa yang sudah kamu coba?

Raphael

3

Perhatikan bahwa selalu ada sampel penolakan : sampel

nomor seragam dan tolak jika jumlahnya tidak bertambah hingga

. Di sini, jumlah iterasi yang diharapkan sangat tinggi, jadi Anda harus melakukan hal lain.

n

$n$

1

$1$

Raphael

28

Mari kita asumsikan bahwa Anda ingin mengambil sampel di dalamnya

x + y + z = 1
0 ≤ x ≤ 1
0 ≤ y ≤ 1
0 ≤ z ≤ 1

Ini tidak membuat perbedaan, karena titik sampel akan tetap berada di area yang Anda minta dengan probabilitas tinggi.

Sekarang Anda tinggal mengambil sampel titik dari simpleks . Dalam contoh 3d Anda mendapatkan simpleks (segitiga) 2d direalisasikan dalam 3d.

Cara memilih titik secara seragam secara acak dibahas dalam posting blog ini (lihat komentar).

Untuk masalah Anda, itu berarti Anda mengambil angka acak dari interval , lalu Anda menambahkan dan untuk mendapatkan daftar angka. Anda mengurutkan daftar dan kemudian Anda merekam perbedaan antara dua elemen berturut-turut. Ini memberi Anda daftar nomor yang akan berjumlah hingga . Apalagi pengambilan sampel ini seragam. Gagasan ini dapat ditemukan di Donald B. Rubin, The Bayesian bootstrap Ann. Statist. 9, 1981, 130-134. $n-1$ $(0,1)$ $0$ $1$ $n+1$ $n$ $1$

Sebagai contoh ( ) Anda memiliki tiga angka acak maka Anda mendapatkan urutan yang diurutkan dan ini memberikan perbedaan , dan dengan membangun keempat angka ini berjumlah hingga 1. $n=4$ 0.4 0.2 0.10 0.1 0.2 0.4 10.1 0.1 0.2 0.6

Pendekatan lain adalah sebagai berikut: sampel pertama dari hypercube (yaitu Anda lupa tentang x+y+z=1) dan kemudian menormalkan titik sampel. Normalisasi adalah proyeksi dari silinderperangkat ke -simpleks. Harus jelas secara intuitif bahwa titik-titik di pusat simpleks memiliki lebih banyak "titik-gambar-awal" daripada di luar $d$ $d-1$ . Oleh karena itu, jika Anda mengambil sampel secara seragam dari hypercube, ini tidak akan memberi Anda sampel seragam dalam simpleks. Namun, jika Anda mengambil sampel dari hypercube dengan Distribusi Eksponensial yang sesuai, maka efek ini akan dibatalkan. Gambar ini memberi Anda gambaran bagaimana kedua metode akan sampel. Namun, saya lebih suka metode "pengurutan" karena bentuknya yang sederhana. Ini juga lebih mudah diimplementasikan.

Contoh dari 2 metode pengambilan sampel

A.Schulz
sumber

Saya kira ide naif - menarik

angka dari

dan menormalkan - salah, kalau begitu.

n

$n$

(0, 1)

$(0,1)$

Raphael

Saya menjawab pertanyaan Anda dalam jawaban yang diperluas.

A.Schulz

1

Apakah ada bukti sederhana yang menunjukkan bahwa penyortiran memberikan distribusi yang seragam? Saya hanya memiliki latar belakang dasar dalam probabilitas sehingga kertas di atas kepala saya.

Chao Xu

5

n

$n$

(0, 1)

$(0, 1)$

n

$n$

n - 1

$n-1$

(0, 1)

$(0, 1)$

1

@Orient: Silakan ajukan pertanyaan kepada Anda di pos terpisah dan jangan menyalahgunakan komentar untuk ini.

A.Schulz

8

Ini untuk menambah jawaban yang ada.

Devroye adalah referensi yang sangat baik untuk pertanyaan semacam ini. Bab.7 memberikan algoritma yang diperlukan untuk menghasilkan statistik urutan seragam, yang mana OP inginkan.

$n$ $[0,1]$ $O(n \log n)$ $n$ $x_1,\ldots,x_n$ $\mathrm{Exp}(1)$

(y_{i})_{1 \leq i \leq n} = \frac{\sum_{1 \dots i} x_{j}}{\sum_{1 \dots n} x_{j}}

$(y_i)_{1\leq i\leq n} = \frac{\sum \limits_{1\ldots i} x_j}{\sum \limits_{1\ldots n} x_j}$

O (n)

$O(n)$

$[0,1]$ $2x+3y+z = 5$

PKG
sumber

Jika saya mengikuti jawabannya di sini: stackoverflow.com/questions/2106503/... Kemudian menghasilkan nomor acak dari distribusi eksponensial melibatkan mengevaluasi logaritma, yang bisa agak lambat.

R zu

3

X[0] = 0
for i = 1 to N-1
    X[i] = uniform(0,1)
X[n] = 1
sort X[0..N]
for i = 1 to N
    Z[i] = X[i] - X[i-1]
return Z[1..N]

Di sini, uniform(0,1)mengembalikan bilangan real secara independen dan seragam antara 0 dan 1.

JeffE
sumber

5

Ini adalah jawaban A. Schulz dalam kode tanpa penjelasan, kan?

Raphael

1

Lihat makalah ini : Smith, N. dan Tromble, R., Pengambilan sampel secara seragam dari unit simplex .

Alec
sumber

2

Harap format jawaban Anda dengan cara yang dapat dibaca: Anda menulis untuk manusia, bukan kompiler bibtex. Juga, jika kertas tersedia secara online, itu jauh lebih efisien bagi Anda untuk memberikan tautan.

David Richerby

Pengambilan sampel yang seragam dari simpleks

Jawaban: