Saya tidak bisa memahami hal ini, mana yang lebih acak?
rand()
ATAU :
rand() * rand()
Saya menganggapnya sebagai penggoda otak nyata, dapatkah Anda membantu saya?
EDIT:
Secara intuitif saya tahu bahwa jawaban matematisnya adalah bahwa keduanya sama-sama acak, tetapi saya tidak bisa tidak berpikir bahwa jika Anda "menjalankan algoritma bilangan acak" dua kali ketika Anda mengalikan keduanya bersama-sama, Anda akan menciptakan sesuatu yang lebih acak daripada hanya melakukan sekali.
math
language-agnostic
random
Trufa
sumber
sumber
Jawaban:
Hanya klarifikasi
Meskipun jawaban sebelumnya benar setiap kali Anda mencoba untuk menemukan keacakan variabel pseudo-acak atau perkaliannya, Anda harus menyadari bahwa sementara Random () biasanya terdistribusi secara seragam, Random () * Random () tidak.
Contoh
Ini adalah sampel distribusi acak seragam yang disimulasikan melalui variabel pseudo-acak:
Meskipun ini adalah distribusi yang Anda dapatkan setelah mengalikan dua variabel acak:
Jadi, keduanya “acak”, tetapi distribusinya sangat berbeda.
Contoh lain
Sementara 2 * Acak () didistribusikan secara seragam:
Acak () + Acak () tidak!
Teorema Batas Pusat
The Central Teorema Limit menyatakan bahwa jumlah dari Random () cenderung ke distribusi normal sebagai istilah peningkatan.
Hanya dengan empat istilah yang Anda dapatkan:
Dan di sini Anda dapat melihat jalan dari seragam ke distribusi normal dengan menjumlahkan 1, 2, 4, 6, 10 dan 20 variabel acak terdistribusi seragam:
Edit
Beberapa kredit
Terima kasih kepada Thomas Ahle untuk menunjukkan dalam komentar bahwa distribusi probabilitas yang ditunjukkan dalam dua gambar terakhir dikenal sebagai distribusi Irwin-Hall
Terima kasih kepada Heike untuk fungsinya yang tercabik []
sumber
rand()+rand()
, Anda akan berakhir dengan distribusi tipe "2d6" dengan pusat lemak.Saya kira kedua metode ini bersifat acak meskipun kata saya akan mengatakan itu
rand() * rand()
kurang acak karena akan lebih banyak biji nol. Begitu saturand()
adalah0
, total menjadi0
sumber
Tidak ada yang 'lebih acak'.
rand()
menghasilkan seperangkat angka yang dapat diprediksi berdasarkan pada benih psuedo-acak (biasanya berdasarkan waktu saat ini, yang selalu berubah). Mengalikan dua angka berurutan dalam urutan menghasilkan urutan angka yang berbeda, tetapi dapat diprediksi sama.Mengatasi apakah ini akan mengurangi tabrakan, jawabannya adalah tidak. Ini benar-benar akan meningkatkan tabrakan karena efek mengalikan dua angka di mana
0 < n < 1
. Hasilnya akan menjadi fraksi yang lebih kecil, menyebabkan bias pada hasil menuju ujung bawah spektrum.Beberapa penjelasan lebih lanjut. Berikut ini, 'tidak dapat diprediksi' dan 'acak' merujuk pada kemampuan seseorang untuk menebak apa nomor berikutnya akan didasarkan pada angka sebelumnya, yaitu. sebuah oracle.
Diberikan seed
x
yang menghasilkan daftar nilai berikut:rand()
akan menghasilkan daftar di atas, danrand() * rand()
akan menghasilkan:Kedua metode akan selalu menghasilkan daftar angka yang sama untuk seed yang sama, dan karenanya dapat diprediksi oleh oracle. Tetapi jika Anda melihat hasil untuk mengalikan dua panggilan, Anda akan melihat semuanya ada di bawah
0.3
meskipun distribusi yang layak dalam urutan asli. Jumlahnya bias karena efek mengalikan dua fraksi. Jumlah yang dihasilkan selalu lebih kecil, oleh karena itu jauh lebih mungkin menjadi tabrakan meskipun masih tak terduga.sumber
rand()+rand()+rand()...
semakin "kurang acak" (jika secara acak maksud Anda terdistribusi secara merata).rand()
untuk benar-benar acak, dan jangan mencoba untuk 'meningkatkan' keacakan itu. Jangan atur seed berulang kali. Setiap benih individu baik-baik saja, asalkan itu semi-acak itu sendiri. Banyak implementasi yang saya lihat menggunakan zaman UNIX sebagai seed, yang berubah setiap detik dan unik setiap kali ia berubah.Penyederhanaan berlebih untuk menggambarkan suatu hal.
Asumsikan fungsi acak Anda hanya keluaran
0
atau1
.random()
adalah salah satu(0,1)
, tetapirandom()*random()
merupakan salah satu dari(0,0,0,1)
Anda dapat dengan jelas melihat bahwa peluang untuk mendapatkan
0
dalam kasus kedua sama sekali tidak sama dengan peluang untuk mendapatkan1
.Ketika saya pertama kali memposting jawaban ini, saya ingin membuatnya sesingkat mungkin sehingga seseorang yang membacanya akan mengerti dari perbedaan antara
random()
danrandom()*random()
, tetapi saya tidak bisa menahan diri dari menjawab pertanyaan litteram iklan asli:Mana yang lebih acak?
Menjadi bahwa
random()
,random()*random()
,random()+random()
,(random()+1)/2
atau kombinasi lain yang tidak mengarah pada hasil tetap memiliki sumber yang sama entropi (atau keadaan awal yang sama dalam kasus generator pseudorandom), jawabannya akan bahwa mereka sama-sama acak (Perbedaannya dalam distribusi mereka). Contoh sempurna yang bisa kita lihat adalah permainan Craps. Jumlah yang Anda dapatkan adalahrandom(1,6)+random(1,6)
dan kita semua tahu bahwa mendapatkan 7 memiliki peluang tertinggi, tetapi itu tidak berarti hasil dari menggulirkan dua dadu lebih atau kurang acak daripada hasil dari menggulirkan satu.sumber
Inilah jawaban sederhana. Pertimbangkan Monopoli. Anda melempar dua dadu enam sisi (atau 2d6 bagi Anda yang lebih suka notasi game) dan mengambil jumlah mereka. Hasil yang paling umum adalah 7 karena ada 6 cara yang memungkinkan Anda dapat menggulung 7 (1,6 2,5 3,4 4,3 5,2 dan 6,1). Sedangkan 2 hanya dapat bergulir pada 1,1. Sangat mudah untuk melihat bahwa rolling 2d6 berbeda dari rolling 1d12, bahkan jika rentangnya sama (mengabaikan bahwa Anda bisa mendapatkan 1 pada 1d12, intinya tetap sama). Melipatgandakan hasil Anda alih-alih menambahkannya akan membuat mereka condong dengan cara yang serupa, dengan sebagian besar hasil Anda muncul di tengah rentang. Jika Anda mencoba mengurangi outlier, ini adalah metode yang bagus, tetapi itu tidak akan membantu membuat distribusi yang merata.
(Dan anehnya itu akan meningkatkan gulungan rendah juga. Dengan asumsi keacakan Anda mulai dari 0, Anda akan melihat lonjakan pada 0 karena itu akan mengubah apa pun gulungan lainnya menjadi 0. Pertimbangkan dua angka acak antara 0 dan 1 (termasuk ) dan mengalikan. Jika salah satu hasil adalah 0, semuanya menjadi 0 tidak peduli hasil lainnya. Satu-satunya cara untuk mendapatkan 1 dari itu adalah untuk kedua gulungan menjadi 1. Dalam prakteknya ini mungkin tidak masalah tapi itu membuat grafik yang aneh.)
sumber
Wajib xkcd ...
sumber
Mungkin membantu untuk memikirkan hal ini dalam angka yang lebih berbeda. Pertimbangkan ingin membuat angka acak antara 1 dan 36, sehingga Anda memutuskan cara termudah adalah melempar dua dadu yang adil, 6 sisi. Anda mendapatkan ini:
Jadi kami memiliki 36 angka, tetapi tidak semuanya terwakili secara adil, dan beberapa tidak muncul sama sekali. Angka di dekat tengah diagonal (sudut kiri bawah ke sudut kanan atas) akan muncul dengan frekuensi tertinggi.
Prinsip yang sama yang menggambarkan distribusi yang tidak adil antara dadu berlaku untuk angka-angka floating point antara 0,0 dan 1,0.
sumber
Beberapa hal tentang "keacakan" bersifat kontra-intuitif.
Dengan asumsi distribusi flat
rand()
, berikut ini akan memberi Anda distribusi non-flat:sqrt(rand(range^2))
(rand(range) + rand(range))/2
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.sumber
Sebagian besar implementasi rand () memiliki beberapa periode. Yaitu setelah sejumlah besar panggilan urutan berulang. Urutan output dari
rand() * rand()
pengulangan dalam setengah waktu, sehingga "kurang acak" dalam arti itu.Juga, tanpa konstruksi yang hati-hati, melakukan aritmatika pada nilai acak cenderung menyebabkan lebih sedikit keacakan. Poster di atas mengutip "
rand()
+rand()
+rand()
..." (k kali, katakanlah) yang sebenarnya cenderung k kali nilai rata-rata rentang nilai yangrand()
dikembalikan. (Ini jalan acak dengan langkah simetris tentang nilai tengah itu.)Asumsikan konkret bahwa fungsi rand () Anda mengembalikan bilangan real acak terdistribusi seragam dalam kisaran [0,1). (Ya, contoh ini memungkinkan ketelitian yang tak terbatas. Ini tidak akan mengubah hasilnya.) Anda tidak memilih bahasa tertentu dan bahasa yang berbeda dapat melakukan hal yang berbeda, tetapi analisis berikut berlaku untuk modifikasi implementasi rand yang tidak sesat ( ). Produk
rand() * rand()
ini juga berada dalam kisaran [0,1) tetapi tidak lagi didistribusikan secara merata. Faktanya, produk tersebut cenderung 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 dapat diprediksi. Dalam sapuan lebar, == lebih mudah diprediksi kurang acak.Cukup banyak urutan operasi pada input acak yang seragam akan menjadi acak yang tidak seragam, yang mengarah pada peningkatan prediktabilitas. Dengan hati-hati, seseorang dapat mengatasi properti ini, tetapi kemudian akan lebih mudah untuk menghasilkan angka acak yang terdistribusi secara merata dalam rentang yang sebenarnya Anda inginkan daripada membuang-buang waktu dengan aritmatika.
sumber
"acak" vs. "lebih acak" sedikit mirip dengan menanyakan Zero mana yang lebih nol.
Pada kasus ini,
rand
adalah PRNG, jadi tidak sepenuhnya acak. (sebenarnya, cukup bisa diprediksi jika benihnya diketahui). Mengalikannya dengan nilai lain membuatnya tidak lebih atau kurang acak.RNG tipe crypto yang sebenarnya sebenarnya akan acak. Dan menjalankan nilai melalui fungsi apa pun tidak dapat menambahkan lebih banyak entropi ke dalamnya, dan sangat mungkin menghapus entropi, menjadikannya tidak lebih acak.
sumber
Konsep yang Anda cari adalah "entropi," "derajat" kekacauan dari serangkaian bit. Idenya paling mudah dipahami dalam hal konsep "entropi maksimum".
Definisi perkiraan string bit dengan entropi maksimum adalah bahwa itu tidak dapat diekspresikan secara tepat dalam hal string bit yang lebih pendek (mis. Menggunakan beberapa algoritma untuk memperluas string yang lebih kecil kembali ke string asli).
Relevansi entropi maksimum dengan keacakan berasal dari fakta bahwa jika Anda memilih angka "secara acak", Anda hampir pasti akan memilih nomor yang string bitnya hampir memiliki entropi maksimum, yaitu, ia tidak dapat dikompresi. Ini adalah pemahaman terbaik kami tentang apa yang menjadi ciri nomor "acak".
Jadi, jika Anda ingin membuat angka acak dari dua sampel acak yang "dua kali" sebagai acak, Anda akan menyatukan kedua string bit tersebut. Secara praktis, Anda hanya perlu memasukkan sampel ke bagian tinggi dan rendah dari kata panjang ganda.
Pada catatan yang lebih praktis, jika Anda menemukan diri Anda dibebani dengan rand jelek (), kadang-kadang dapat membantu untuk menggabungkan beberapa sampel bersama-sama --- walaupun, jika benar-benar rusak bahkan prosedur itu tidak akan membantu.
sumber
4
atau biner @CurtainDog xkcd0100
dapat dikompresi menjadi nol bit. Program dekompresi hanya akan mengembalikan '4'. Tidak ada yang kurang acak dari itu. Masalah dengan dilbert adalah, kita tidak tahu apakah kita bisa mengompresnya ke nol bit (dekompresi dengan selalu mengembalikan 'sembilan'). Mungkin mengembalikan delapan juga, maka kita bisa kompres menjadi 1 bit. Dekompresi dengan: 0-> sembilan, 1-> delapan. Kami akan memiliki 1 bit acak.Jawaban yang diterima cukup bagus, tetapi ada cara lain untuk menjawab pertanyaan Anda. Jawaban PachydermPuncher sudah mengambil pendekatan alternatif ini, dan saya hanya akan memperluas sedikit.
Cara termudah untuk memikirkan teori informasi adalah dalam hal unit informasi terkecil, sedikit pun.
Di pustaka standar C,
rand()
mengembalikan bilangan bulat dalam rentang 0 hinggaRAND_MAX
, batas yang dapat didefinisikan secara berbeda tergantung pada platform. MisalkanRAND_MAX
kebetulan didefinisikan sebagai di2^n - 1
manan
bilangan bulat (ini terjadi pada implementasi Microsoft, di manan
15). Maka kita akan mengatakan bahwa implementasi yang baik akan mengembalikann
bit informasi.Bayangkan bahwa
rand()
membangun angka acak dengan membalik koin untuk menemukan nilai satu bit, dan kemudian ulangi hingga memiliki batch 15 bit. Kemudian bit-bit itu independen (nilai bit apa pun tidak mempengaruhi kemungkinan bit-bit lain dalam batch yang sama memiliki nilai tertentu). Jadi setiap bit yang dipertimbangkan secara independen seperti angka acak antara 0 dan 1 inklusif, dan "terdistribusi secara merata" pada rentang itu (kemungkinan 0 sebagai 1).Kemandirian bit memastikan bahwa angka-angka yang diwakili oleh kumpulan bit juga akan didistribusikan secara merata pada kisarannya. Ini jelas secara intuitif: jika ada 15 bit, rentang yang diizinkan adalah nol hingga
2^15 - 1
= 32767. Setiap angka dalam rentang itu adalah pola bit yang unik, seperti:dan jika bit independen maka tidak ada pola yang lebih mungkin terjadi daripada pola lainnya. Jadi semua kemungkinan angka dalam kisaran sama-sama mungkin. Dan sebaliknya adalah benar: jika
rand()
menghasilkan bilangan bulat terdistribusi secara merata, maka angka-angka itu dibuat dari bit independen.Jadi anggaplah
rand()
sebagai jalur produksi untuk membuat bit, yang kebetulan melayani mereka dalam batch ukuran sewenang-wenang. Jika Anda tidak suka ukurannya, pisahkan bets menjadi bit individual, dan kemudian kumpulkan kembali dalam jumlah apa pun yang Anda suka (meskipun jika Anda memerlukan kisaran tertentu yang bukan kekuatan 2, Anda perlu mengecilkan angka Anda , dan sejauh ini cara termudah untuk melakukannya adalah dengan mengkonversi ke floating point).Kembali ke saran awal Anda, misalkan Anda ingin beralih dari 15 batch menjadi 30 batch, minta
rand()
nomor pertama, geser sedikit dengan 15 tempat, lalu tambahkan yang lainrand()
. Itu adalah cara untuk menggabungkan dua panggilanrand()
tanpa mengganggu distribusi yang merata. Ini berfungsi hanya karena tidak ada tumpang tindih antara lokasi tempat Anda meletakkan bit informasi.Ini sangat berbeda dengan "merentangkan" kisaran
rand()
dengan mengalikan dengan konstanta. Misalnya, jika Anda ingin menggandakan rentangrand()
Anda dapat mengalikan dua - tetapi sekarang Anda hanya akan mendapatkan angka genap, dan tidak pernah angka ganjil! Itu bukan distribusi yang lancar dan mungkin menjadi masalah serius tergantung pada aplikasinya, misalnya game seperti roulette yang seharusnya memungkinkan taruhan ganjil / genap. (Dengan berpikir dalam bentuk bit, Anda akan menghindari kesalahan itu secara intuitif, karena Anda akan menyadari bahwa mengalikan dua dengan sama dengan menggeser bit ke kiri (signifikansi lebih besar) di satu tempat dan mengisi celah dengan nol. Jadi jelas jumlah informasinya sama - hanya bergerak sedikit.)Kesenjangan tersebut dalam rentang nomor tidak dapat mengomel tentang di floating aplikasi nomor titik, karena floating rentang titik inheren memiliki kesenjangan di dalamnya yang tidak bisa diwakili sama sekali: sebuah terbatas jumlah hilang bilangan real ada di celah antara setiap dua representable mengambang angka titik! Jadi kita tetap harus belajar hidup dengan celah.
Seperti yang telah diperingatkan orang lain, intuisi berisiko di bidang ini, terutama karena matematikawan tidak dapat menahan daya pikat bilangan real, yang merupakan hal-hal membingungkan yang penuh dengan ketidakterbatasan tanpa batas dan paradoks yang jelas.
Tetapi setidaknya jika Anda menganggapnya sedikit, intuisi Anda mungkin membuat Anda sedikit lebih jauh. Bit sangat mudah - bahkan komputer dapat memahaminya.
sumber
Seperti yang dikatakan orang lain, jawaban singkat yang mudah adalah: Tidak, itu tidak lebih acak, tetapi itu mengubah distribusi.
Misalkan Anda sedang memainkan permainan dadu. Anda memiliki beberapa dadu yang benar-benar adil dan acak. Akankah gulungan mati menjadi "lebih acak" jika sebelum setiap gulungan mati, pertama-tama Anda meletakkan dua dadu dalam mangkuk, mengocoknya, mengambil salah satu dadu secara acak, dan kemudian menggulungnya? Jelas itu tidak ada bedanya. Jika kedua dadu memberikan angka acak, maka memilih secara acak salah satu dari dua dadu tidak akan membuat perbedaan. Apa pun cara Anda akan mendapatkan angka acak antara 1 dan 6 dengan distribusi yang merata atas jumlah gulungan yang cukup.
Saya kira dalam kehidupan nyata prosedur seperti itu mungkin berguna jika Anda curiga bahwa dadu TIDAK mungkin adil. Jika, katakanlah, dadu sedikit tidak seimbang sehingga seseorang cenderung memberi 1 lebih sering dari 1/6 waktu, dan dadu lainnya cenderung memberi 6 lebih sering, maka memilih secara acak di antara keduanya akan cenderung mengaburkan bias. (Meskipun dalam kasus ini, 1 dan 6 masih akan muncul lebih dari 2, 3, 4, dan 5. Yah, saya kira tergantung pada sifat ketidakseimbangan.)
Ada banyak definisi keacakan. Salah satu definisi dari serangkaian acak adalah bahwa itu adalah serangkaian angka yang dihasilkan oleh proses acak. Dengan definisi ini, jika saya melempar dadu yang adil 5 kali dan mendapatkan angka 2, 4, 3, 2, 5, itu adalah seri acak. Jika saya kemudian menggulirkan fair die yang sama 5 kali lebih banyak dan mendapatkan 1, 1, 1, 1, 1, maka itu juga merupakan seri acak.
Beberapa poster menunjukkan bahwa fungsi acak pada komputer tidak benar-benar acak melainkan pseudo-acak, dan jika Anda mengetahui algoritme dan seed, mereka sepenuhnya dapat diprediksi. Ini benar, tetapi sebagian besar waktu sama sekali tidak relevan. Jika saya mengocok setumpuk kartu dan kemudian membalikkannya satu per satu, ini harus menjadi seri acak. Jika seseorang mengintip kartu, hasilnya akan sepenuhnya dapat diprediksi, tetapi oleh sebagian besar definisi keacakan ini tidak akan membuatnya kurang acak. Jika seri melewati uji statistik keacakan, fakta bahwa saya mengintip kartu tidak akan mengubah fakta itu. Dalam praktiknya, jika kita mempertaruhkan uang dalam jumlah besar pada kemampuan Anda untuk menebak kartu berikutnya, maka fakta bahwa Anda mengintip kartu itu sangat relevan. Jika kami menggunakan seri ini untuk mensimulasikan pilihan menu pengunjung ke situs web kami untuk menguji kinerja sistem, maka fakta bahwa Anda mengintip tidak akan membuat perbedaan sama sekali. (Selama Anda tidak memodifikasi program untuk memanfaatkan pengetahuan ini.)
EDIT
Saya tidak berpikir saya bisa menanggapi masalah Monty Hall menjadi komentar, jadi saya akan memperbarui jawaban saya.
Bagi mereka yang tidak membaca tautan Belisarius, intinya adalah: Seorang kontestan game show diberi pilihan 3 pintu. Di belakang satu adalah hadiah yang berharga, di belakang yang lain ada sesuatu yang tidak berharga. Dia mengambil pintu # 1. Sebelum mengungkapkan apakah itu pemenang atau kalah, tuan rumah membuka pintu # 3 untuk mengungkapkan bahwa itu adalah pecundang. Dia kemudian memberi kontestan kesempatan untuk beralih ke pintu # 2. Haruskah kontestan melakukan ini atau tidak?
Jawabannya, yang menyinggung intuisi banyak orang, adalah ia harus beralih. Probabilitas bahwa pick aslinya adalah pemenang adalah 1/3, bahwa pintu lainnya adalah pemenangnya adalah 2/3. Intuisi awal saya, bersama dengan banyak orang lain, adalah bahwa tidak akan ada untungnya beralih, bahwa peluangnya baru saja diubah menjadi 50:50.
Lagi pula, anggaplah seseorang menyalakan TV tepat setelah tuan rumah membuka pintu yang hilang. Orang itu akan melihat dua pintu tertutup yang tersisa. Dengan asumsi dia tahu sifat permainan, dia akan mengatakan bahwa ada peluang 1/2 setiap pintu menyembunyikan hadiah. Bagaimana peluang untuk penonton menjadi 1/2: 1/2 sedangkan peluang untuk kontestan 1/3: 2/3?
Saya benar-benar harus memikirkan ini untuk mengalahkan intuisi saya. Untuk mengatasinya, pahami bahwa ketika kita berbicara tentang probabilitas dalam masalah seperti ini, maksud kami, probabilitas yang Anda tetapkan diberikan informasi yang tersedia. Untuk anggota kru yang meletakkan hadiah di belakang, katakanlah, pintu # 1, probabilitas bahwa hadiah berada di belakang pintu # 1 adalah 100% dan probabilitas bahwa itu di belakang salah satu dari dua pintu lainnya adalah nol.
Peluang anggota kru berbeda dari peluang kontestan karena dia tahu sesuatu yang tidak diketahui kontestan, yaitu pintu yang dia letakkan di belakang hadiah. Demikian juga, peluang kontestan berbeda dari peluang pemirsa karena ia tahu sesuatu yang tidak dilihat oleh pemirsa, yaitu pintu mana yang awalnya ia pilih. Ini tidak relevan, karena pilihan tuan rumah untuk membuka pintu tidak acak. Dia tidak akan membuka pintu yang dipilih kontestan, dan dia tidak akan membuka pintu yang menyembunyikan hadiah. Jika ini adalah pintu yang sama, itu meninggalkannya dua pilihan. Jika mereka pintu yang berbeda, hanya menyisakan satu.
Jadi bagaimana kita menghasilkan 1/3 dan 2/3? Ketika kontestan awalnya memilih pintu, ia memiliki peluang 1/3 untuk memilih pemenang. Saya pikir itu sudah jelas. Itu berarti ada peluang 2/3 bahwa salah satu pintu lainnya adalah pemenangnya. Jika tuan rumah memberinya peluang untuk beralih tanpa memberikan informasi tambahan, tidak akan ada untungnya. Sekali lagi, ini harus jelas. Tetapi satu cara untuk melihatnya adalah dengan mengatakan bahwa ada peluang 2/3 bahwa ia akan menang dengan beralih. Tapi dia punya 2 alternatif. Jadi masing-masing hanya memiliki 2/3 dibagi dengan 2 = 1/3 peluang untuk menjadi pemenang, yang tidak lebih baik dari pilihan aslinya. Tentu saja kami sudah tahu hasil akhirnya, ini hanya menghitung dengan cara yang berbeda.
Tetapi sekarang tuan rumah mengungkapkan bahwa salah satu dari dua pilihan itu bukanlah pemenang. Jadi dari kesempatan 2/3 bahwa sebuah pintu yang tidak dia pilih adalah pemenangnya, dia sekarang tahu bahwa 1 dari 2 alternatif bukan. Yang lain mungkin atau mungkin tidak. Jadi dia tidak lagi memiliki 2/3 dibagi 2. Dia tidak memiliki nol untuk pintu terbuka dan 2/3 untuk pintu tertutup.
sumber
Pertimbangkan Anda memiliki masalah flip koin sederhana di mana bahkan dianggap kepala dan aneh dianggap ekor. Implementasi logisnya adalah:
Lebih dari distribusi yang cukup besar, jumlah bilangan genap harus sama dengan jumlah bilangan ganjil.
Sekarang pertimbangkan sedikit penyesuaian:
Jika salah satu hasilnya genap, maka seluruh hasil harus genap. Pertimbangkan 4 hasil yang mungkin (even * even = even, even * odd = even, odd * even = even, odd * odd = odd). Sekarang, dengan distribusi yang cukup besar, jawabannya harus mencapai 75%.
Aku berani bertaruh kalau aku jadi kamu.
Komentar ini benar-benar lebih merupakan penjelasan mengapa Anda tidak boleh menerapkan fungsi acak khusus berdasarkan metode Anda daripada diskusi tentang sifat matematika dari keacakan.
sumber
rand()%2
mungkin tidak terlalu acak; itu benar-benar tergantung pada keacakan bit rendah, dan beberapa PRNG tidak begitu baik. (Tentu saja, dalam beberapa bahasa Anda mendapatkan hasil floating-pointrand()
sehingga Anda tidak bisa melakukannya dengan cara sama sekali ...)Ketika ragu tentang apa yang akan terjadi pada kombinasi angka acak Anda, Anda dapat menggunakan pelajaran yang Anda pelajari dalam teori statistik.
Dalam situasi OP dia ingin tahu apa hasil X * X = X ^ 2 di mana X adalah variabel acak yang didistribusikan bersama Uniform [0,1]. Kami akan menggunakan teknik CDF karena ini hanya pemetaan satu-ke-satu.
Karena X ~ Seragam [0,1] itu cdf adalah: f X (x) = 1 Kami ingin transformasi Y <- X ^ 2 sehingga y = x ^ 2 Temukan kebalikan x (y): sqrt (y) = x ini memberi kita x sebagai fungsi dari y. Selanjutnya, cari turunan dx / dy: d / dy (sqrt (y)) = 1 / (2 sqrt (y))
Distribusi Y diberikan sebagai: f Y (y) = f X (x (y)) | dx / dy | = 1 / (2 sqrt (y))
Kami belum selesai, kami harus mendapatkan domain Y. karena 0 <= x <1, 0 <= x ^ 2 <1 sehingga Y berada dalam kisaran [0, 1). Jika Anda ingin memeriksa apakah pdf dari Y memang pdf, integrasikan dengan domain: Integrasikan 1 / (2 sqrt (y)) dari 0 hingga 1 dan memang, muncul sebagai 1. Juga, perhatikan bentuk dari fungsi kata seperti apa yang diposting memposting.
Adapun hal-hal seperti X 1 + X 2 + ... + X n , (di mana X i ~ Seragam [0,1]) kita dapat mengajukan banding ke Teorema Limit Pusat yang bekerja untuk distribusi mana pun yang momennya ada. Inilah sebabnya mengapa uji-Z sebenarnya ada.
Teknik lain untuk menentukan pdf yang dihasilkan termasuk transformasi Jacobian (yang merupakan versi umum dari teknik cdf) dan teknik MGF.
EDIT: Sebagai klarifikasi, perhatikan bahwa saya sedang berbicara tentang distribusi hasil transformasi dan bukan keacakannya . Itu sebenarnya untuk diskusi terpisah. Juga apa yang sebenarnya saya peroleh untuk (rand ()) ^ 2. Untuk rand () * rand () itu jauh lebih rumit, yang, dalam hal apa pun tidak akan menghasilkan distribusi seragam apa pun.
sumber
Ini tidak terlalu jelas, tetapi
rand()
biasanya lebih acak daripadarand()*rand()
. Yang penting adalah ini sebenarnya tidak terlalu penting untuk sebagian besar penggunaan.Tetapi pertama-tama, mereka menghasilkan distribusi yang berbeda. Ini bukan masalah jika itu yang Anda inginkan, tetapi itu penting. Jika Anda membutuhkan distribusi tertentu, abaikan seluruh pertanyaan “mana yang lebih acak”. Jadi mengapa
rand()
lebih acak?Inti dari itu
rand()
lebih acak (dengan asumsi bahwa itu menghasilkan angka acak floating-point dengan kisaran [0..1], yang sangat umum) adalah bahwa ketika Anda mengalikan dua nomor FP bersama-sama dengan banyak informasi di mantissa, Anda mendapatkan beberapa kehilangan informasi pada akhirnya; hanya ada tidak cukup bit dalam float presisi ganda IEEE untuk menampung semua informasi yang ada di dua float presisi ganda IEEE yang dipilih secara acak dari [0..1], dan bit informasi tambahan tersebut hilang. Tentu saja, itu tidak masalah karena Anda (mungkin) tidak akan menggunakan informasi itu, tetapi kerugiannya nyata. Juga tidak masalah distribusi mana yang Anda hasilkan (yaitu, operasi mana yang Anda gunakan untuk melakukan kombinasi). Masing-masing angka acak memiliki (paling-paling) 52 bit informasi acak - bahwa 'Sebagian besar penggunaan angka acak tidak menggunakan bahkan mendekati keacakan sebanyak yang sebenarnya tersedia di sumber acak. Dapatkan PRNG yang baik dan jangan terlalu khawatir tentang hal itu. (Tingkat "kebaikan" tergantung pada apa yang Anda lakukan dengannya; Anda harus berhati-hati ketika melakukan simulasi atau kriptografi Monte Carlo, tetapi jika tidak, Anda mungkin dapat menggunakan PRNG standar karena biasanya lebih cepat.)
sumber
Floating randoms umumnya didasarkan pada algoritma yang menghasilkan bilangan bulat antara nol dan rentang tertentu. Dengan demikian, dengan menggunakan rand () * rand (), Anda pada dasarnya mengatakan int_rand () * int_rand () / rand_max ^ 2 - artinya Anda tidak menyertakan bilangan prima / rand_max ^ 2.
Itu mengubah distribusi acak secara signifikan.
rand () terdistribusi secara merata di sebagian besar sistem, dan sulit diprediksi jika diunggulkan dengan benar. Gunakan itu kecuali Anda memiliki alasan khusus untuk menghitungnya (yaitu, membentuk distribusi ke kurva yang diperlukan).
sumber
rand()*rand()
lebih kecil dari ruang hasilrand()
- karena tidak termasuk bilangan prima. Mendapat suara saya ...Mengalikan angka akan berakhir dalam kisaran solusi yang lebih kecil tergantung pada arsitektur komputer Anda.
Jika tampilan komputer Anda menunjukkan 16 digit
rand()
dapat dikatakan 0,1234567890123 dikalikan satu detikrand()
, 0,1234567890123, akan memberikan 0,0152415 sesuatu yang Anda pasti akan menemukan lebih sedikit solusi jika Anda mengulangi percobaan 10 ^ 14 kali.sumber
Sebagian besar distribusi ini terjadi karena Anda harus membatasi atau menormalkan angka acak.
Kami menormalkannya agar semuanya positif, cocok dalam kisaran, dan bahkan agar sesuai dengan batasan ukuran memori untuk tipe variabel yang ditugaskan.
Dengan kata lain, karena kita harus membatasi panggilan acak antara 0 dan X (X menjadi batas ukuran variabel kita), kita akan memiliki kelompok angka "acak" antara 0 dan X.
Sekarang ketika Anda menambahkan angka acak ke angka acak lain jumlahnya akan berada di suatu tempat antara 0 dan 2X ... ini membuat nilai-nilai menjauh dari titik tepi (probabilitas menambahkan dua angka kecil bersama-sama dan dua angka besar bersama-sama sangat kecil ketika Anda memiliki dua angka acak dalam kisaran besar).
Pikirkan kasus di mana Anda memiliki angka yang mendekati nol dan Anda menambahkannya dengan nomor acak lain, angka itu pasti akan semakin besar dan menjauh dari 0 (ini akan berlaku untuk angka besar serta tidak mungkin memiliki dua angka besar (angka dekat dengan X) dikembalikan oleh fungsi acak dua kali.
Sekarang jika Anda mengatur metode acak dengan angka negatif dan angka positif (merentang sama di sumbu nol) ini tidak lagi menjadi kasus.
Katakan misalnya
RandomReal({-x, x}, 50000, .01)
maka Anda akan mendapatkan pemerataan angka pada sisi positif sisi negatif dan jika Anda menambahkan angka acak bersama-sama mereka akan mempertahankan "keacakan" mereka.Sekarang saya tidak yakin apa yang akan terjadi dengan
Random() * Random()
rentang negatif ke positif ... itu akan menjadi grafik yang menarik untuk dilihat ... tapi saya harus kembali menulis kode sekarang. :-Psumber
Tidak ada yang namanya lebih acak. Entah itu acak atau tidak. Acak berarti "sulit diprediksi". Itu tidak berarti non-deterministik. Acak () dan acak () * acak () sama-sama acak jika acak () adalah acak. Distribusi tidak relevan sejauh keacakan. Jika distribusi tidak seragam terjadi, itu hanya berarti bahwa beberapa nilai lebih mungkin daripada yang lain; mereka masih tidak dapat diprediksi.
Karena pseudo-randomness terlibat, jumlahnya sangat deterministik. Namun, pseudo-randomness seringkali cukup dalam model probabilitas dan simulasi. Sudah cukup dikenal bahwa membuat generator bilangan pseudo-acak hanya membuat sulit untuk menganalisis. Ini tidak mungkin untuk meningkatkan keacakan; sering menyebabkan gagal tes statistik.
Sifat-sifat yang diinginkan dari bilangan acak adalah penting: pengulangan dan reproduktifitas, keacakan statistik, (biasanya) terdistribusi secara seragam, dan periode besar sedikit.
Mengenai transformasi pada angka acak: Seperti kata seseorang, jumlah dua atau lebih yang terdistribusi secara merata menghasilkan distribusi normal. Ini adalah teorema batas pusat aditif . Ini berlaku terlepas dari distribusi sumber selama semua distribusi independen dan identik. Itu perkalianteorema limit pusat mengatakan produk dari dua atau lebih variabel acak independen dan terdistribusi indentik adalah lognormal. Grafik yang dibuat orang lain terlihat eksponensial, tetapi benar-benar lognormal. Jadi acak () * acak () terdistribusi secara lognormal (meskipun mungkin tidak independen karena angka ditarik dari aliran yang sama). Ini mungkin diinginkan di beberapa aplikasi. Namun, biasanya lebih baik untuk menghasilkan satu nomor acak dan mengubahnya menjadi nomor yang didistribusikan secara lognormal. Acak () * acak () mungkin sulit untuk dianalisis.
Untuk informasi lebih lanjut, baca buku saya di www.performorama.org. Buku ini sedang dibangun, tetapi bahan yang relevan ada di sana. Perhatikan bahwa nomor bab dan bagian dapat berubah seiring waktu. Bab 8 (teori probabilitas) - bagian 8.3.1 dan 8.3.3, bab 10 (angka acak).
sumber
Kita dapat membandingkan dua array angka mengenai keacakan dengan menggunakan kompleksitas Kolmogorov. Jika urutan angka tidak dapat dikompres, maka itu adalah yang paling acak yang dapat kita capai pada panjang ini ... Saya tahu bahwa jenis pengukuran ini lebih bersifat teoretis. pilihan...
sumber
Sebenarnya, ketika Anda berpikir tentang hal
rand() * rand()
itu kurang acakrand()
. Inilah sebabnya.Pada dasarnya, ada jumlah angka ganjil yang sama dengan angka genap. Dan mengatakan bahwa 0,04325 aneh, dan seperti 0,388 genap, dan 0,4 genap, dan 0,15 aneh,
Itu berarti
rand()
memiliki peluang yang sama untuk menjadi desimal genap atau ganjil .Di sisi lain,
rand() * rand()
peluangnya ditumpuk sedikit berbeda. Katakanlah:a
danb
keduanya memiliki peluang 50% sebelum menjadi genap atau ganjil. Mengetahui bahwaberarti bahwa ada peluang 75% yang
c
genap, sementara hanya peluang 25% itu aneh, membuat nilairand() * rand()
lebih dapat diprediksi daripadarand()
, karenanya kurang acak.sumber
rand()
biasanya memberikan angka antara 0 dan 1. Apakah berbicara tentang apakah itu genap atau ganjil masuk akal?0.2*0.2=0.04
yang menunjukkan kelemahan mendasar dengan pendekatan ini: mengalikan 53 bit dari dua ganda akan menghasilkan sekitar 100 bit dalam hasilnya. Tetapi setengah dari bit-bit ini akan dibuang. Jadi, ketika Anda mengambil dua ganda dengan 1 sebagai bit paling signifikan mereka, Anda tidak bisa mengatakan apa-apa tentang bit paling signifikan dari produk mereka.rand()
adalah sama dengan definisi "genap" dan "ganjil" yang masuk akal untuk distribusi darirand()*rand()
. Jika bukan itu masalahnya, argumen ini gagal. Itu berlaku untuk bilangan bulat, tetapi ini bukan bilangan bulat.Gunakan register geser umpan balik linier (LFSR) yang mengimplementasikan polinomial primitif.
Hasilnya akan menjadi urutan 2 ^ n angka pseudo-acak, yaitu tidak ada yang mengulangi dalam urutan di mana n adalah jumlah bit dalam LFSR .... menghasilkan distribusi yang seragam.
http://en.wikipedia.org/wiki/Linear_feedback_shift_register http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf
Gunakan seed "acak" berdasarkan microsec dari jam komputer Anda atau mungkin sebagian dari hasil md5 pada beberapa data yang terus berubah dalam sistem file Anda.
Sebagai contoh, LFSR 32-bit akan menghasilkan 2 ^ 32 angka unik secara berurutan (no 2 sama) dimulai dengan seed yang diberikan. Urutan akan selalu dalam urutan yang sama, tetapi titik awal akan berbeda (jelas) untuk benih yang berbeda. Jadi, jika urutan yang mungkin berulang antara penyemaian tidak menjadi masalah, ini mungkin pilihan yang baik.
Saya telah menggunakan LFSR 128-bit untuk menghasilkan tes acak dalam simulator perangkat keras menggunakan seed yang merupakan hasil md5 pada terus mengubah data sistem.
sumber
Dengan asumsi bahwa
rand()
mengembalikan angka di antara[0, 1)
itu jelas bahwarand() * rand()
akan menjadi bias terhadap 0. Ini karena mengalikanx
dengan angka di antara[0, 1)
akan menghasilkan angka yang lebih kecil darix
. Berikut adalah distribusi dari 10.000 lebih nomor acak:Tampilkan cuplikan kode
Jika
rand()
mengembalikan bilangan bulat antara[x, y]
maka Anda memiliki distribusi berikut. Perhatikan jumlah nilai ganjil vs genap:Tampilkan cuplikan kode
sumber
OK, jadi saya akan mencoba menambahkan beberapa nilai untuk melengkapi jawaban orang lain dengan mengatakan bahwa Anda membuat dan menggunakan generator angka acak.
Generator angka acak adalah perangkat (dalam arti yang sangat umum) yang memiliki beberapa karakteristik yang dapat dimodifikasi agar sesuai dengan tujuan. Beberapa dari mereka (dari saya) adalah:
Di sebagian besar jawaban di sini, distribusi adalah poin utama yang menarik, tetapi dengan mencampur dan mencocokkan fungsi dan parameter, Anda menciptakan cara baru untuk menghasilkan angka acak yang akan memiliki karakteristik yang berbeda untuk beberapa yang evaluasi mungkin tidak jelas pada pandangan pertama.
sumber
Sangat mudah untuk menunjukkan bahwa jumlah dari dua angka acak belum tentu acak. Bayangkan Anda memiliki 6 sisi die and roll. Setiap angka memiliki peluang 1/6 untuk muncul. Sekarang katakan Anda memiliki 2 dadu dan menyimpulkan hasilnya. Distribusi jumlah itu bukan 1/12. Mengapa? Karena angka-angka tertentu muncul lebih dari yang lain. Ada beberapa partisi di antaranya. Misalnya angka 2 adalah jumlah 1 + 1 saja tetapi 7 dapat dibentuk oleh 3 + 4 atau 4 + 3 atau 5 + 2 dll ... sehingga memiliki peluang lebih besar untuk muncul.
Oleh karena itu, menerapkan transformasi, dalam hal ini penambahan pada fungsi acak tidak membuatnya lebih acak, atau perlu menjaga keacakan. Dalam kasus dadu di atas, distribusi condong ke 7 dan karenanya kurang acak.
sumber
Seperti yang sudah ditunjukkan orang lain, pertanyaan ini sulit dijawab karena kita semua memiliki gambaran keacakan di kepalanya.
Itu sebabnya, saya akan sangat menyarankan Anda untuk meluangkan waktu dan membaca situs ini untuk mendapatkan ide yang lebih baik tentang keacakan:
Untuk kembali ke pertanyaan sebenarnya. Tidak ada yang kurang lebih acak dalam istilah ini:
keduanya hanya muncul secara acak !
Dalam kedua kasus - hanya rand () atau rand () * rand () - situasinya sama: Setelah beberapa miliar angka urutannya akan berulang (!) . Ini tampaknya acak untuk pengamat, karena dia tidak tahu seluruh urutan, tetapi komputer memiliki tidak ada sumber acak yang benar - sehingga ia tidak dapat menghasilkan keacakan baik.
misalnya: Apakah cuacanya acak? Kami tidak memiliki cukup sensor atau pengetahuan untuk menentukan apakah cuaca acak atau tidak.
sumber
Jawabannya tergantung, semoga rand () * rand () akan lebih acak daripada rand (), tetapi sebagai:
Nah, jika Anda memeriksa semua di atas saya sarankan Anda pergi untuk "rand ()" yang sederhana. Karena kode Anda akan lebih mudah dibaca (tidak akan bertanya pada diri sendiri mengapa Anda menulis ini, untuk ... yah ... lebih dari 2 detik), mudah dipelihara (jika Anda ingin mengganti fungsi rand dengan super_rand).
Jika Anda ingin acak yang lebih baik, saya akan merekomendasikan Anda untuk mengalirkannya dari sumber yang menyediakan cukup noise ( radio statis ), dan kemudian yang sederhana
rand()
harus cukup.sumber