Distribusi acak tertimbang kontinu, bias ke satu ujung

28

Saat ini saya berkontribusi pada sistem partikel untuk permainan kami dan mengembangkan beberapa bentuk emitor.

Distribusi acak seragam saya di sepanjang garis atau di sepanjang area persegi berfungsi dengan baik - tidak ada masalah.

Tapi sekarang saya ingin memiliki gradien 1 dimensi dalam distribusi ini. Ini berarti misalnya nilai yang lebih rendah lebih umum daripada nilai yang lebih tinggi.

Saya tidak tahu istilah matematika apa yang cocok untuk masalah ini, jadi keterampilan pencarian saya agak tidak berguna untuk masalah ini. Saya membutuhkan sesuatu yang sederhana secara komputasi, karena sistem partikel harus efisien.

didito
sumber
Apakah tidak ada yang akan menyebutkan kalkulus?
Alec Teal

Jawaban:

42

Lihatlah gambar ini:

Pemetaan kurva

Ini menunjukkan proses pemetaan nilai (acak) ke kurva. Misalkan Anda menghasilkan nilai acak X yang didistribusikan secara seragam, mulai dari 0 hingga 1. Dengan memetakan nilai ini ke kurva - atau, dengan kata lain, menggunakan f (X) alih-alih X - Anda dapat mengubah distribusi Anda dengan cara apa pun yang Anda suka .

Dalam gambar ini, kurva pertama membuat nilai yang lebih tinggi lebih mungkin; kedua membuat nilai yang lebih rendah lebih mungkin; dan yang ketiga membuat nilai cluster di tengah. Rumus yang tepat dari kurva tidak terlalu penting, dan dapat dipilih sesuka Anda.

Sebagai contoh, kurva pertama terlihat sedikit seperti akar kuadrat, dan kuadrat kedua seperti. Yang ketiga agak mirip kubus, hanya diterjemahkan. Jika Anda menganggap akar kuadrat terlalu lambat, kurva pertama juga terlihat seperti f (X) = 1- (1-X) ^ 2 - inversi kuadrat. Atau hiperbola: f (X) = 2X / (1 + X).

Seperti yang ditunjukkan kurva keempat, Anda cukup menggunakan tabel pencarian yang dikomputasi. Terlihat jelek sebagai kurva, tetapi mungkin akan cukup baik untuk sistem partikel.

Teknik umum ini sangat sederhana dan kuat. Distribusi apa pun yang Anda butuhkan, bayangkan saja pemetaan kurva, dan Anda akan menyusun formula dalam waktu singkat. Atau, jika mesin Anda memiliki editor, buat saja editor visual untuk kurva!

Sudahlah
sumber
terima kasih banyak atas penjelasannya yang sangat teliti dan mudah dimengerti. semua posting lainnya juga sangat membantu, tetapi saya benar-benar dapat memahami posting Anda yang termudah dan tercepat. itu mencuat bc itu benar-benar menghantam tempat untuk cara saya memahami hal-hal. dan aspek yang Anda jelaskan persis apa yang saya cari (atau berkeliaran)! itu akan memungkinkan saya untuk menggunakan ini dalam banyak kasus di masa depan. jadi terima kasih lagi !!! btw, saya bermain-main dengan beberapa lekuk tubuh Anda dan itu berfungsi seperti pesona.
didito
5
FYI: Ini disebut fungsi kuantil: en.wikipedia.org/wiki/Quantile_function
Neil G
8

Penjelasan yang lebih panjang:

Jika Anda memiliki distribusi probabilitas yang diinginkan seperti gradien @didito yang diminta, Anda dapat menggambarkannya sebagai fungsi. Katakanlah Anda menginginkan distribusi segitiga, di mana probabilitas pada 0 adalah 0,0, dan Anda ingin memilih angka acak dari 0 hingga 1. Kita mungkin menuliskannya sebagai y = x.

Langkah selanjutnya adalah menghitung integral dari fungsi ini. Dalam hal ini, x=1x2 . Dievaluasi dari 0 menjadi 1, itu ½. Itu masuk akal - itu adalah segitiga dengan basis 1 dan tinggi 1, jadi luasnya ½.

Anda kemudian memilih titik acak secara seragam dari 0 ke area (½ dalam contoh kami). Sebut saja z ini. (Kami memilih secara seragam dari distribusi kumulatif .)

Langkah selanjutnya adalah mundur, untuk menemukan nilai x (apa yang akan kita sebut x̂) sesuai dengan area z. Kami sedang mencari x=1x2 , dievaluasi dari 0 hingga x̂, sama dengan z. Ketika Anda menyelesaikan untuk1x̂2=z, Anda mendapatkanx̂=2z .

Dalam contoh ini, Anda memilih z dari 0 hingga ½ dan kemudian angka acak yang diinginkan adalah 2z . Sederhana, Anda dapat menuliskannya sebagairSebuahnd(0,1) - persis apa yang direkomendasikan eBusiness.

amitp
sumber
Terima kasih atas masukan Anda yang berharga. Saya selalu suka mendengar bagaimana orang yang terampil memecahkan masalah. tetapi saya masih perlu membungkus kepala saya untuk jujur ​​...
didito
ini luar biasa. Saya selalu membuat sqrt(random())seluruh hidup saya tetapi saya sampai pada hal itu secara empiris. Mencoba mengikat angka acak ke kurva, dan ternyata berhasil. Sekarang saya sedikit lebih mahir dalam bidang Matematika, mengetahui mengapa ia bekerja sangat berharga!
Gustavo Maciel
5

Anda mungkin akan mendapatkan perkiraan mendekati apa yang Anda inginkan dengan memanfaatkan sistem eksponensial.

Buat x berdasarkan sesuatu seperti 1- (nilai rnd ^) (Dengan asumsi rnd adalah antara 0 dan 1) dan Anda akan mendapatkan beberapa perilaku berbeda dari arah miring ke kanan berdasarkan apa yang Anda gunakan. Nilai yang lebih tinggi akan memberi Anda distribusi yang lebih miring

Anda dapat menggunakan alat grafik online untuk mendapatkan ide-ide kasar tentang perilaku yang diberikan persamaan yang berbeda sebelum Anda menempatkannya, atau Anda bisa bermain-main dengan persamaan langsung dalam sistem partikel Anda, tergantung gaya apa yang lebih sesuai dengan selera Anda.

EDIT

Untuk sesuatu seperti sistem partikel di mana waktu CPU per partikel sangat penting, menggunakan Math.Pow (atau bahasa yang setara) secara langsung dapat menyebabkan penurunan kinerja. Jika lebih banyak kinerja diinginkan, dan nilainya tidak diubah dalam run-time, pertimbangkan beralih ke fungsi yang setara seperti x * x alih-alih x ^ 2.

(Eksponen pecahan bisa lebih merupakan masalah, tetapi seseorang dengan latar belakang matematika yang lebih kuat daripada saya mungkin bisa datang dengan cara yang baik untuk membuat fungsi perkiraan)

Lunin
sumber
1
Alih-alih menggunakan program grafik, Anda bisa memplot distribusi Beta karena ini adalah kasus khusus. Untuk yang diberikan value, ini adalah Beta (nilai, 1).
Neil G
Terima kasih. Saya mencoba merencanakan beberapa grafik dan saya pikir itu bisa membuat saya di tempat yang saya inginkan.
didito
@Neil G terima kasih atas tipnya dengan "distribusi beta" - ini terdengar menarik dan bermanfaat ... saya akan melakukan riset tentang topik itu
didito
3

Istilah yang Anda cari adalah Weighted Random Numbers, sebagian besar algoritma yang saya lihat menggunakan fungsi trigonometri, tapi saya pikir saya menemukan cara yang akan efisien:

Buat tabel / array / Daftar (apa pun) yang menyimpan nilai pengganda untuk fungsi acak. Isi dengan tangan atau secara terprogram ...

randMulti= {.1,.1,.1,.1,.1,.1,.2,.2,.3,.3,.9,1,1,1,} 

... lalu Kalikan randomdengan yang dipilih secara acak randMultidan akhirnya dengan Nilai maksimum dari distribusi ...

weightedRandom = math.random()*randMulti[Math.random(randMulti.length)]*maxValue

Saya percaya bahwa ini akan jauh lebih cepat daripada menggunakan sqrt, atau fungsi komputasional yang lebih kompleks lainnya, dan akan memungkinkan lebih banyak pola pengelompokan kustom.

SerangHobo
sumber
2
Jika Anda dapat mengorbankan memori, tabel 100 nilai yang sudah dihitung sebelumnya akan lebih cepat (dan sedikit lebih akurat). Saya ragu pengguna akan dapat membedakan antara versi lengkap dan pra-komputasi.
Daniel Blezek
@Daniel akan lebih cepat, tetapi dengan 100 nilai acak, cukup mudah untuk melihat pola berulang.
AttackingHobo
Hanya karena tampaknya ada pola berulang tidak berarti itu tidak acak. Inti dari keacakan adalah ketidakpastiannya, yang secara harfiah berarti bahwa sebanyak orang tidak dapat memprediksi bahwa tidak akan ada pola, orang juga tidak dapat memprediksi bahwa mungkin ada satu (setidaknya untuk waktu yang singkat). Anda harus melakukan beberapa pengujian, tetapi jika Anda menemukan pola dengan beberapa pengujian menggunakan benih yang berbeda, maka algoritma Anda untuk menghasilkan angka pseudo-acak mungkin perlu ditinjau.
Randolf Richardson
@AttackingHobo thx untuk trik itu. Saya suka penggunaan LUT. dan formulanya cukup mudah dimengerti. Saya tidak berpikir seperti ini sebelumnya. tidak melihat kayu untuk pohon ... :) juga saya pikir pola berulang harus dihindari tetapi mungkin tidak akan diakui dalam kasus ini. tetap saja, mengkalkulasi semua nilai akan merusak pengalaman visual.
Bagaimanapun
juga terima kasih telah memunculkan istilah Weighted "Random Numbers"!
didito
2

Saya pikir yang Anda minta adalah distribusi yang dicapai menggunakan fungsi akar kuadrat.

[position] = sqrt(rand(0, 1))

Ini akan memberikan distribusi dalam bidang dimensi tunggal di [0, 1]mana probabilitas untuk suatu posisi setara dengan posisi itu, yaitu "distribusi segitiga".

Generasi bebas squareroot alternatif:

[position] = 1-abs(rand(0, 1)-rand(0, 1))

Root kuadrat dalam implementasi optimal hanya beberapa perintah perkalian dan jumlah tanpa cabang. (Lihat: http://en.wikipedia.org/wiki/Fast_inverse_square_root ). Salah satu dari dua fungsi ini yang lebih cepat dapat bervariasi tergantung pada platform dan generator acak. Sebagai contoh, pada platform x86 hanya dibutuhkan beberapa cabang yang tidak dapat diprediksi dalam generator acak untuk membuat metode kedua lebih lambat.

aaaaaaaaaaaa
sumber
Probabilitas suatu posisi tidak akan sama dengan posisi (itu tidak mungkin secara matematis - sepele, domain dan rentang fungsi mencakup 0,50 dan 0,51), juga bukan merupakan distribusi segitiga. ( en.wikipedia.org/wiki/Triangular_distribution )
1
Sementara sqrt memberikan beberapa pola yang menarik, sistem partikel umumnya harus sangat ringan CPU per partikel, jadi saya akan merekomendasikan menghindari akar kuadrat (yang secara komputasi lambat) di mana mungkin. Kadang-kadang Anda bisa lolos hanya dengan melakukan pra-komputasi, tetapi itu bisa membuat partikel Anda memiliki pola yang terlihat dari waktu ke waktu.
Lunin
1
@ Jo Wreschnig, apakah Anda membaca sendiri artikel Wikipedia itu, hal-hal a = 0, b = 1, c = 1 ke dalam formula generasi dan Anda mendapatkan formula dalam posting saya.
aaaaaaaaaaaa
3
@ Lunun, mengapa Anda mengeluh tentang akar kuadrat ketika Anda memiliki eksponen dalam jawaban Anda?
aaaaaaaaaaaa
1
@ Lunin: Teori kinerja adalah bidang yang cukup diabaikan, banyak dari apa yang orang pikir mereka tahu di mana kira-kira 30 tahun yang lalu ketika ALU sangat mahal dan lambat. Bahkan fungsi eksponen yang baru saja Anda temukan sebagai fungsi aritmatika yang sangat lambat jarang merupakan pendosa kinerja yang sangat signifikan. Percabangan (menggunakan pernyataan if) dan melewatkan cache (membaca sepotong data yang saat ini tidak berada di cache) biasanya merupakan biaya kinerja paling tinggi.
aaaaaaaaaaaa
1

Cukup gunakan distribusi Beta:

  • Beta (1,1) datar
  • Beta (1,2) adalah gradien linier
  • Beta (1,3) adalah kuadratik

dll.

Dua parameter bentuk tidak harus berupa bilangan bulat.

Neil G
sumber
Terima kasih atas bantuan Anda. seperti yang dinyatakan di atas, distribusi beta terdengar menarik. tetapi saya belum dapat memahami konten halaman wikipedia. atau formula / kode. baik, juga saya tidak punya waktu sekarang untuk menyelidiki lebih lanjut: si melihat bahwa dorongan memiliki kode untuk distribusi beta, tetapi ini akan berlebihan. baik, saya kira saya harus pergi dulu dan kemudian menulis versi saya sendiri yang disederhanakan.
didito
1
@dito: Tidak terlalu sulit. Anda cukup mengganti uniform_generator()panggilan Anda dengan gsl_ran_beta(rng, a, b). Lihat di sini: gnu.org/software/gsl/manual/html_node/…
Neil G
Terima kasih atas petunjuknya. saya tidak menggunakan GSL (sebenarnya belum pernah mendengarnya sebelumnya), tetapi panggilan yang bagus. saya akan memeriksa sumbernya!
didito
@dito: Dalam hal ini, saya akan pergi dengan solusi Lunin. Semoga berhasil.
Neil G
0

Lebih sederhana, tergantung pada kecepatan generator acak Anda, Anda hanya dapat menghasilkan dua nilai dan rata-rata.

Atau, bahkan lebih sederhana, di mana X adalah hasil dari Ping, pertama double y = double(1/x);, x = y*[maximum return value of rng];. Ini akan menimbang angka secara eksponensial ke angka yang lebih rendah.

Hasilkan dan ratakan lebih banyak nilai untuk meningkatkan kemungkinan mendapatkan nilai lebih dekat ke pusat.

Tentu saja ini hanya berfungsi untuk distribusi kurva lonceng standar atau versi "terlipat" *, tetapi dengan generator cepat, mungkin lebih cepat dan lebih sederhana daripada menggunakan berbagai fungsi matematika seperti sqrt.

Anda dapat menemukan segala macam penelitian tentang ini untuk kurva lonceng dadu. Faktanya, Anydice.com adalah situs bagus yang menghasilkan grafik untuk berbagai metode rolling dadu. Meskipun Anda menggunakan RNG, premisnya sama, seperti hasilnya. Jadi ini adalah tempat yang bagus untuk melihat distribusi bahkan sebelum mengkodekannya.

* Selain itu, Anda dapat "melipat" distribusi hasil di sepanjang sumbu dengan mengambil sumbu dan mengurangi hasil rata-rata kemudian menambahkan sumbu. Misalnya, Anda ingin nilai yang lebih rendah menjadi lebih umum, dan katakanlah Anda ingin 15 menjadi nilai minimum Anda dan 35 menjadi nilai maksimal Anda, kisaran 20. Jadi, Anda menghasilkan dan rata-rata bersama dua nilai dengan kisaran 20 ( dua kali rentang yang Anda inginkan), yang akan memberikan bellcurve yang berpusat pada 20 (kami kurangi lima di akhir untuk menggeser kisaran dari 20 menjadi 40, menjadi 15 hingga 35). Ambil angka yang dihasilkan X dan Y.

Angka terakhir,

z =(x+y)/2;// average them
If (z<20){z = (20-z)+20;}// fold if below axis
return z-5;// return value adjusted to desired range

Jika nol adalah minimum Anda, bahkan lebih baik, lakukan ini sebagai gantinya,

z= (x+y)/2;
If (z<20){z = 20-z;}
else {z = z - 20;}
return z;
TheAlicornSage
sumber