Apa sebenarnya keacakan itu

Saya seorang mahasiswa Ilmu Komputer dan saat ini terdaftar dalam kursus Simulasi Sistem & Pemodelan. Ini melibatkan berurusan dengan sistem sehari-hari di sekitar kita dan mensimulasikan mereka dalam skenario yang berbeda dengan menghasilkan angka acak dalam kurva distribusi yang berbeda, seperti IID, Gaussian dll misalnya. Saya telah mengerjakan proyek boids dan sebuah pertanyaan mengejutkan saya bahwa sebenarnya "acak" itu? Maksudku, misalnya, setiap angka acak yang kita hasilkan, bahkan dalam bahasa pemrograman kita seperti melalui Math.random()metode di Jawa, pada dasarnya dihasilkan dengan mengikuti "algoritma".

Bagaimana kita benar-benar tahu bahwa urutan angka yang kita hasilkan sebenarnya, acak dan apakah itu akan membantu kita, untuk mensimulasikan model tertentu seakurat mungkin?

Jawaban singkatnya adalah tidak ada yang tahu apa keacakan sebenarnya, atau jika hal seperti itu ada. Jika Anda ingin mengukur atau mengukur keacakan objek diskrit, Anda biasanya akan beralih ke kompleksitas Kolmogorov . Sebelum kompleksitas Kolmogorov, kami tidak memiliki cara untuk mengukur keacakan dari mengatakan urutan angka tanpa mempertimbangkan proses yang melahirkannya.

Berikut ini adalah contoh intuitif yang benar-benar mengganggu orang-orang pada masa itu. Pertimbangkan urutan lemparan koin. Hasil dari satu lemparan adalah kepala ( ) atau ekor ( T ). Katakanlah kita melakukan dua percobaan, di mana kita melempar koin 10 kali. Percobaan pertama E 1 memberi kita H , H , H , H , H , H , H , H , H , H . Eksperimen kedua E 2 memberi kita T , T , H , T , H $H$$T$$E_1$$H,H,H,H,H,H,H,H,H,H$$E_2$ . Setelah melihat hasilnya, Anda mungkin tergoda untuk mengklaim ada sesuatu yang salah dengan koin di E 1 , atau setidaknya untuk beberapa alasan aneh apa yang Anda punya tidak acak. Tetapi jika Anda menganggap kedua H dan T adalah sebagai kemungkinan (koin adil), probabilitas mendapatkan baik E 1 atau E 2 adalah sama dengan ( 1 / 2 ) 10 . Faktanya, mendapatkanurutan spesifikapa pundimungkinkan! Namun, E 2 terasa$T,T,H,T,H,T,T,H,T,H$$E_1$$H$$T$$E_1$$E_2$$(1/2)^{10}$$E_2$ acak, dan tidak.$E_1$

Secara umum, karena kompleksitas Kolmogorov tidak dapat dihitung, kita tidak dapat menghitung seberapa acak urutan angka-angkanya, tidak peduli apa pun jenis proses yang diklaim "benar-benar acak" itu.

Dalam kasus Java (atau bahasa serupa), kita tahu algoritma yang digunakan untuk membuat angka acak. Jika dimulai dengan satu biji, jumlahnya tidak acak sama sekali, yaitu jika kita tahu dalam urutan yang 0 , ... , a n , kita tahu sebuah i + 1 , atau dinyatakan sebagai probabilitas bersyarat: ∀ k , l , i : P ( a $a_i$$a_0,\dots,a_n$$a_{i+1}$

Namun demikian seri tersebut dapat memenuhi properti (lihat misalnya WP: Autocorrelation ) yang dipenuhi oleh angka acak dan properti ini sering cukup untuk menyelesaikan tugas, di mana kami ingin menggunakan "nyata" (mis. Dihasilkan oleh beberapa proses fisik) angka acak, tetapi tidak dapat t usaha mereka.

Tidak mungkin untuk mengetahui dengan pasti apakah urutan yang diberikan adalah acak atau tidak. Anda dapat, bagaimanapun, melihat karakteristik (atau parameter) dari suatu sekuens dan menghitung probabilitas dari sekuens tersebut mengingat distribusi bunga.

Jika Anda dapat menghasilkan urutan yang sangat panjang menggunakan generator acak Anda, itu harus memiliki parameter yang sama dengan distribusi acak. Misalnya, jika Anda menggunakan distribusi Gaussian standar , maka urutan Anda harus mendekati rata-rata 0 dan standar deviasi 1 . Jadi, satu cara awal untuk memeriksa generator Anda adalah untuk menghasilkan urutan yang sangat panjang dan memeriksa untuk melihat bahwa itu mendekati distribusi acak yang diinginkan.$(\mu=0,\sigma=1)$$1$

Anda dapat menambahkan momen tambahan dari distribusi (seperti kemiringan) yang menarik untuk validasi lebih lanjut. Untuk angka IID, Anda juga bisa mencoba melatih algoritme pembelajaran mesin untuk memprediksi elemen urutan yang akan datang dan kemudian menguji hipotesis nol bahwa riwayat meningkatkan kinerja. Tidak satu pun dari metode ini, bagaimanapun, dapat membuktikan bahwa urutan benar-benar acak dan, paling-paling, dapat mengenali kapan urutan TIDAK acak (sampai tingkat kepastian tertentu).

Teori modern jawaban komputasi adalah "sumber acak adalah sumber yang terlihat acak untuk kelas algoritma favorit Anda". Ini adalah perspektif utilitarian: jika sumber keacakan tampak seperti keacakan yang sebenarnya untuk semua algoritma yang Anda pedulikan, maka tidak ada hal lain yang penting. Anda dapat menganalisis algoritme Anda seolah-olah mereka diberikan lemparan koin benar-benar acak, dan analisis Anda akan memberikan jawaban yang benar.

Untuk menjadi sedikit lebih tepat, mari kita mengatakan bahwa Anda peduli tentang semua algoritma di kelas . A bisa saja$\mathcal{A}$$\mathcal{A}$

• semua mesin Turing yang selalu berhenti
• semua keluarga sirkuit ukuran polinomial
• semua polinomial waktu mesin Turing
• semua mesin Turing logspace

$\mathcal{A}$$(X_n)$$X_n$$\{0, 1\}^n$$\epsilon$$\mathcal{A}$$A \in \mathcal{A}$

Gagasan ini ada di balik setiap gagasan formal modern tentang pseudorandomness.

Ini dua sen lagi.

Salah satu cara untuk berpikir tentang algoritma acak adalah dengan menggambarkan sebuah kotak yang mengambil beberapa input, melakukan hal-hal misterius untuk input itu, dan menghasilkan beberapa ("tak terduga") output.

Tetapi sebaliknya, mungkin bermanfaat untuk menganggapnya sebagai algoritma deterministik yang mengambil dua input: input "benar", dan beberapa input "acak" yang kita dapatkan dari fungsi seperti Math.Random() .

$[0,1]$$n \log n$ " atau "dengan probabilitas tinggi jawabannya benar".

$[0,1]$$n \log n$ atau benar atau sebagainya).

Seperti yang disebutkan Jonathan dan frafl, ada beberapa cara untuk menyortir memeriksa apakah sumber acak berperilaku "secara acak". Tapi yang akan mereka lakukan adalah memengaruhi apa yang Anda yakini tentang informasi masa depan yang berasal dari sumber acak ini. Jika Anda berpikir bahwa setiap bit kemungkinan sama dengan nol atau satu, terlepas dari bit sebelumnya, maka untuk yang terbaik dari pengetahuan dan keyakinan Anda, sumber itu secara acak seragam dan independen dan oleh karena itu, sesuai dengan pengetahuan dan keyakinan Anda, itu akan berjalan cepat atau benar atau seterusnya. Lagi pula, itulah pandangan filosofis saya.

Kami tidak dapat menghasilkan angka yang benar-benar acak. Ada berbagai metode untuk menghasilkan bilangan pseudo-acak menggunakan persamaan yang ditentukan dan nilai benih tertentu. Jadi urutan angka acak tergantung pada nilai seed. Setelah kita mengetahui nilai seed, kita bisa memprediksi seperti apa urutannya. Terlepas dari ini, ada metode lain untuk menghasilkan angka acak. Orang-orang sekarang menggunakan beberapa metode untuk menghasilkan angka acak yang benar seperti menggunakan waktu pergerakan kepala disk dan metode fisik lainnya yang dapat dimasukkan ke dalam komputer. Lihat: http://en.wikipedia.org/wiki/Random_number_generation#Generation_methods

dengan metode yang diberikan seperti yang Anda katakan
Math.random () di Java
Randomize; Acak (n); dalam Delphi

Anda dapat menerapkan struktur dan logika Anda sendiri untuk menghasilkan angka acak, di
mana "algoritma" tersebut dapat bekerja dengan spesifikasi yang Anda berikan untuk hasil acak yang lebih baik.
dan membangun logika itu.

Terima kasih.

jawaban lain baik, inilah beberapa sudut lain dari pertanyaan yang sangat penting / tidak sengaja ini. ilmuwan komputer telah mempelajari keacakan selama beberapa dekade dan cenderung terus mempelajarinya. ia memiliki banyak koneksi mendalam dan pertanyaan terbuka utama yang tersisa di seluruh bidang. berikut adalah beberapa petunjuk.

• "true / real randomness" terjadi dengan proses fisik tingkat rendah & "noise" seperti di dioda zener, mekanika kuantum dll. yang dapat dimanfaatkan dalam RNG berbasis perangkat keras

• angka lain yang dihasilkan di ranah komputer adalah apa yang dikenal sebagai "pseudorandom" yang disimulasikan dan tidak pernah dapat menyamai "keacakan benar". ini disebut PRNG

• ada arti penting dari "kekerasan kriptografi generator angka acak" yang dalam arti mengukur "kualitas" atau "keamanan" mereka lihat misalnya PRNG yang aman secara kriptografis . pada dasarnya generator "lemah" tidak memiliki kompleksitas komputasi sebanyak generator "keras" dan generator "lemah" lebih mudah dipecahkan.

• rasa lain yang agak terkait muncul adalah "kekerasan bukti". bayangkan bukti untuk membuktikan bahwa RNG adalah waktu linier$O(n)$. that proof would seem to be simpler than one required to prove it is quadratic $O(n^2)$ and so on. this concept is still in the process of being formalized/researched but it actually impinges on deep questions like P$\stackrel{?}{=}$NP in a famous paper called Natural Proofs. roughly, the authors show a P$\neq$NP proof must have a certain "complexity" otherwise the same analysis technique could be used to break PRNGs, and moreover, somewhat surprisingly, most or maybe all complexity class separations/techniques known at that date (or possibly even afterwards, to date) do not have sufficient complexity.

• an important research topic in TCS is randomized and derandomized algorithms. the idea is, roughly, to study how much the algorithm is altered by replacing "true randomness" with a PRNG and there are various deep theorems on the subject. here is a highranked cstheory.se question that gives some flavor of research in this area: efficient and simple randomized algorithms where determinism is difficult

• another key related topic in TCS is information entropy— originally introduced in physics long ago— which studies a closely related concept of "information dis-order" and like some other important concepts in (T)CS seems be one of the key ideas that crosscuts the boundary between applied and theoretical analysis, even some of the formulas are the same.

• again attesting to the status of active research, there are other high-ranked questions on cstheory.se that relate to this question. here is one close, almost the same: is a truly random number generator Turing computable