Pertanyaan Memahami "keacakan"


Saya tidak bisa memahami hal ini, yang lebih acak?

rand()

ATAU

rand() * rand()

Saya menemukan itu teaser otak asli, bisakah Anda membantu saya?

EDIT:

Secara intuitif saya tahu bahwa jawaban matematisnya adalah bahwa mereka sama-sama acak, tetapi saya tidak dapat membantu tetapi berpikir bahwa jika Anda "menjalankan algoritma angka acak" dua kali saat Anda mengalikan keduanya, Anda akan membuat sesuatu yang lebih acak daripada hanya melakukan sekali saja.


822
2017-10-18 03:40


asal


Jawaban:


Hanya klarifikasi

Meskipun jawaban sebelumnya benar setiap kali Anda mencoba melihat keacakan dari variabel pseudo-random atau perkaliannya, Anda harus menyadari bahwa sementara Acak() biasanya didistribusikan secara merata, Acak () * Acak () tidak.

Contoh

Ini adalah sebuah sampel distribusi acak seragam disimulasikan melalui variabel pseudo-random:

Histogram of Random() 

        BarChart[BinCounts[RandomReal[{0, 1}, 50000], 0.01]]

Meskipun ini adalah distribusi yang Anda dapatkan setelah mengalikan dua variabel acak:

Histogram of Random() * Random() 

        BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] * 
                                 RandomReal[{0, 1}, 50000], {50000}], 0.01]]

Jadi, keduanya "acak", tetapi distribusinya sangat berbeda.

Contoh lain

Sementara 2 * Acak () terdistribusi secara merata:

Histogram of 2 * Random()

        BarChart[BinCounts[2 * RandomReal[{0, 1}, 50000], 0.01]]

Random () + Random () tidak!

Histogram of Random() + Random()

        BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] + 
                                 RandomReal[{0, 1}, 50000], {50000}], 0.01]]

Teorema Batas Tengah

Itu Teorema Batas Tengah menyatakan bahwa jumlah dari Acak() cenderung a distribusi normal sebagai istilah meningkat.

Hanya dengan empat istilah yang Anda dapatkan:

Histogram of Random() + Random() + Random() + Random()

BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] + RandomReal[{0, 1}, 50000] +
                   Table[RandomReal[{0, 1}, 50000] + RandomReal[{0, 1}, 50000],
                   {50000}],
         0.01]]  

Dan di sini Anda dapat melihat jalan dari seragam ke distribusi normal dengan menambahkan 1, 2, 4, 6, 10, dan 20 variabel acak terdistribusi secara merata:

Histogram of different numbers of random variables added

Edit

Beberapa kredit

Terimakasih untuk Thomas Ahle untuk menunjukkan dalam komentar bahwa distribusi probabilitas yang ditunjukkan dalam dua gambar terakhir dikenal sebagai Distribusi Irwin-Hall 

Terimakasih untuk Heike untuknya yang luar biasa sobek [] fungsi


1464
2017-10-18 04:03



Saya kira kedua metode itu sama acaknya meskipun gutfeel saya akan mengatakan itu rand() * rand() kurang acak karena akan menghasilkan lebih banyak nol. Segera setelah satu rand() aku s 0, totalnya menjadi 0 


151
2017-10-18 03:45



Tidak ada yang 'lebih acak'.

rand() menghasilkan kumpulan angka yang dapat diprediksi berdasarkan benih psuedo-random (biasanya berdasarkan waktu saat ini, yang selalu berubah). Mengalikan dua angka berurutan dalam urutan menghasilkan urutan angka yang berbeda, tetapi dapat diprediksi.

Mengatasi apakah ini akan mengurangi tabrakan, jawabannya tidak. Ini benar-benar akan meningkatkan tabrakan karena efek mengalikan dua angka di mana 0 < n < 1. Hasilnya akan menjadi pecahan yang lebih kecil, menyebabkan bias dalam hasil ke arah ujung bawah spektrum.

Beberapa penjelasan lebih lanjut. Berikut ini, 'tidak dapat diprediksi' dan 'acak' mengacu pada kemampuan seseorang untuk menebak apa nomor berikutnya akan didasarkan pada angka sebelumnya, yaitu. sebuah oracle.

Diberi benih x yang menghasilkan daftar nilai berikut:

0.3, 0.6, 0.2, 0.4, 0.8, 0.1, 0.7, 0.3, ...

rand() akan menghasilkan daftar di atas, dan rand() * rand() akan menghasilkan:

0.18, 0.08, 0.08, 0.21, ...

Kedua metode akan selalu menghasilkan daftar angka yang sama untuk benih yang sama, dan karenanya sama-sama dapat diprediksi oleh oracle. Tetapi jika Anda melihat hasil untuk mengalikan dua panggilan, Anda akan melihat mereka semua di bawah 0.3meskipun distribusi yang layak dalam urutan aslinya. Angka-angka itu bias karena efek mengalikan dua fraksi. Jumlah yang dihasilkan selalu lebih kecil, karena itu jauh lebih mungkin menjadi tabrakan meskipun masih sama tidak dapat diprediksi.


81
2017-10-20 22:43



Oversimplification untuk menggambarkan suatu titik. 

Asumsikan hanya output fungsi acak Anda saja 0 atau 1.

random() adalah salah satunya (0,1), tapi random()*random() adalah salah satunya (0,0,0,1) 

Anda dapat dengan jelas melihat bahwa peluang untuk mendapatkan 0 dalam kasus kedua sama sekali tidak sama dengan yang didapat 1.


Ketika saya pertama kali memposting jawaban ini saya ingin membuatnya sesingkat mungkin sehingga orang yang membacanya akan mengerti dari pandangan perbedaan antara random() dan random()*random(), tetapi saya tidak dapat menahan diri dari menjawab pertanyaan asli litteram iklan:

Mana yang lebih acak?


78
2017-10-18 15:31



Inilah jawaban sederhana. Pertimbangkan Monopoli. Anda melempar dua dadu enam sisi (atau 2d6 bagi Anda yang lebih memilih notasi permainan) dan mengambil jumlah mereka. Hasil yang paling umum adalah 7 karena ada 6 kemungkinan cara Anda dapat menggulung 7 (1,6 2,5 3,4 4,3 5,2 dan 6,1). Sedangkan 2 hanya dapat digulirkan pada 1,1. Sangat mudah untuk melihat bahwa rolling 2d6 berbeda dari rolling 1d12, bahkan jika kisarannya sama (mengabaikan bahwa Anda bisa mendapatkan 1 pada 1d12, intinya tetap sama). Mengalikan hasil Anda alih-alih menambahkannya akan membuat sketsa mereka dengan cara yang sama, dengan sebagian besar hasil Anda muncul di tengah kisaran. Jika Anda mencoba mengurangi pencilan, ini adalah metode yang baik, tetapi itu tidak akan membantu membuat pemerataan.

(Dan anehnya itu akan meningkatkan gulungan rendah juga. Dengan asumsi keacakan Anda dimulai pada 0, Anda akan melihat lonjakan pada 0 karena akan mengubah apa pun gulungan lainnya menjadi 0. Pertimbangkan dua angka acak antara 0 dan 1 (inklusif) ) dan mengalikan. Jika salah satu hasilnya adalah 0, semuanya menjadi 0 tidak peduli hasil yang lain. Satu-satunya cara untuk mendapatkan 1 dari itu adalah untuk kedua gulungan menjadi 1. Dalam prakteknya ini mungkin tidak masalah. tapi itu membuat grafik aneh.)


67
2017-10-18 20:25



Yang wajib xkcd ...
return 4; // chosen by fair dice roll, guaranteed to be random.


51
2017-10-18 04:03



Mungkin membantu untuk memikirkan ini dalam jumlah yang lebih diskrit. Pertimbangkan untuk membuat angka acak antara 1 dan 36, jadi Anda memutuskan cara termudah adalah melempar dua dadu yang adil dan berukuran 6-sisi. Anda mendapatkan ini:

     1    2    3    4    5    6
  -----------------------------
1|   1    2    3    4    5    6
2|   2    4    6    8   10   12
3|   3    6    9   12   15   18
4|   4    8   12   16   20   24   
5|   5   10   15   20   25   30
6|   6   12   18   24   30   36

Jadi kami memiliki 36 angka, tetapi tidak semuanya cukup terwakili, dan beberapa tidak muncul sama sekali. Angka di dekat pusat diagonal (sudut kiri bawah ke pojok kanan atas) akan terjadi dengan frekuensi tertinggi.

Prinsip yang sama yang menggambarkan distribusi yang tidak adil antara dadu berlaku sama untuk angka-angka floating point antara 0,0 dan 1,0.


34
2017-10-18 03:45



Beberapa hal tentang "keacakan" bersifat kontra-intuitif.

Dengan asumsi distribusi datar rand(), berikut ini akan membuat Anda distribusi non-flat:

  • bias tinggi: sqrt(rand(range^2))
  • bias memuncak di tengah: (rand(range) + rand(range))/2
  • rendah: bias: range - sqrt(rand(range^2))

Ada banyak cara lain untuk membuat kurva bias tertentu. Saya melakukan tes cepat rand() * rand()dan itu memberi Anda distribusi yang sangat non-linear.


26
2017-10-18 04:10



"acak" vs. "lebih acak" sedikit seperti menanyakan Zero mana yang lebih nol.

Pada kasus ini, rand adalah PRNG, jadi tidak sepenuhnya acak. (sebenarnya, cukup dapat diprediksi jika benihnya diketahui). Mengalikannya dengan nilai lain membuatnya tidak lebih atau kurang acak.

RNG tipe crypto yang sebenarnya akan benar-benar acak. Dan menjalankan nilai melalui fungsi apa pun tidak dapat menambahkan lebih banyak entropinya, dan mungkin sangat mungkin menghapus entropi, membuatnya tidak lebih acak.


23
2017-10-18 19:01



Sebagian besar implementasi rand () memiliki beberapa periode. Yaitu. setelah sejumlah besar panggilan berurutan mengulangi. Urutan output dari rand() * rand() mengulang dalam separuh waktu, jadi "kurang acak" dalam arti itu.

Juga, tanpa konstruksi yang hati-hati, melakukan aritmatika pada nilai acak cenderung menyebabkan lebih sedikit keacakan. Sebuah poster di atas dikutip "rand() + rand() + rand() ... "(k kali, katakanlah) yang sebenarnya akan cenderung k kali nilai rata-rata kisaran nilai rand() kembali. (Ini berjalan acak dengan langkah-langkah simetris tentang maksud itu.)

Asumsikan konkret bahwa fungsi rand Anda () mengembalikan bilangan real acak terdistribusi seragam dalam rentang [0,1). (Ya, contoh ini memungkinkan ketepatan yang tidak terbatas. Ini tidak akan mengubah hasilnya.) Anda tidak memilih bahasa tertentu dan bahasa yang berbeda dapat melakukan hal yang berbeda, tetapi analisis berikut ini berlaku dengan modifikasi untuk setiap rand yang tidak disalahartikan ( ). Produk rand() * rand() juga dalam kisaran [0,1) tetapi tidak lagi terdistribusi secara merata. Bahkan, produk ini mungkin berada dalam interval [0,1 / 4) seperti pada interval [1 / 4,1). Lebih banyak perkalian akan membuat hasil lebih condong ke nol. Ini membuat hasil lebih mudah diprediksi. Dalam stroke luas, lebih mudah diprediksi == kurang acak.

Hampir semua urutan operasi pada input acak seragam akan tidak acak, yang menyebabkan peningkatan prediktabilitas. Dengan hati-hati, seseorang dapat mengatasi properti ini, tetapi kemudian akan lebih mudah untuk menghasilkan nomor acak terdistribusi seragam dalam kisaran yang sebenarnya Anda inginkan daripada membuang-buang waktu dengan aritmatika.


23
2017-10-19 12:02



Konsep yang Anda cari adalah "entropi", "tingkat" gangguan tali bit. Ide ini paling mudah dipahami dalam hal konsep "entropi maksimum".

Definisi perkiraan string bit dengan entropi maksimum adalah bahwa ia tidak dapat diekspresikan secara tepat dalam bentuk string bit yang lebih pendek (mis. Menggunakan beberapa algoritma untuk rentangkan string yang lebih kecil kembali ke string asli).

Relevansi entropi maksimum dengan keacakan berasal dari fakta itu jika Anda memilih nomor "secara acak", Anda hampir pasti akan memilih nomor bit string yang hampir memiliki entropi maksimum, yaitu, tidak dapat dikompresi. Ini adalah pemahaman terbaik kami tentang apa yang mencirikan nomor "acak".

Jadi, jika Anda ingin membuat nomor acak dari dua sampel acak yang "dua kali" sebagai acak, Anda akan menggabungkan dua string bit bersama. Secara praktis, Anda baru saja masukkan sampel ke dalam bagian tinggi dan rendah dari kata panjang ganda.

Pada catatan yang lebih praktis, jika Anda menemukan diri Anda dibebani dengan rand yang jelek (), itu bisa kadang-kadang membantu untuk beberapa sampel bersama-sama --- meskipun, jika benar-benar rusak prosedur itu tidak akan membantu.


19
2017-10-18 21:25