Mengapa tidak mungkin menghasilkan angka yang benar-benar acak?

Saya sedang mencoba untuk menyelesaikan masalah hobi yang membutuhkan menghasilkan jutaan angka acak. Tetapi saya segera menyadari, menjadi sulit untuk menjadikannya unik. Saya mengambil Manual Desain Algoritma untuk membaca tentang pembuatan angka acak.

Ini memiliki paragraf berikut yang saya sepenuhnya tidak bisa mengerti.

Sayangnya, menghasilkan angka acak terlihat jauh lebih mudah daripada yang sebenarnya. Memang, pada dasarnya mustahil untuk menghasilkan angka yang benar-benar acak pada perangkat deterministik apa pun. Von Neumann [Neu63] mengatakan yang terbaik: "Siapa pun yang menganggap metode aritmetika untuk menghasilkan angka acak, tentu saja, dalam keadaan berdosa." jika mereka dihasilkan secara acak.

Mengapa tidak mungkin menghasilkan angka yang benar-benar acak di perangkat deterministik apa pun? Apa arti kalimat ini?

Seseorang harus mencari generator nomor pseudo-acak kriptografis aman . Kebanyakan PRNG adalah generator kongruensi linier (demikian next numberjuga fungsi liniernya previous number), jadi jika Anda memplot next numbervs previous numberAnda akan mendapatkan bagan garis paralel. CSPRNG tidak akan melakukan itu. Imbalannya adalah mereka lambat.

Saya mengelompokkan generator nomor acak ke dalam 3 kategori :

1. Cukup bagus untuk pekerjaan rumah.
2. Cukup bagus untuk mempertaruhkan perusahaan Anda.
3. Cukup bagus untuk mempertaruhkan negara Anda.

Mengapa tidak mungkin untuk menghasilkan angka acak dalam perangkat deterministik?

Perangkat deterministik akan selalu menghasilkan output yang sama ketika diberi kondisi awal dan input yang sama - itulah artinya deterministic. "Angka yang benar-benar acak" adalah lebih dari sudut pandang filosofis, karena apa artinya menjadi randominti dari pandangan pusar filosofis (orang-orang bahkan tidak yakin apakah pembusukan atom adalah acak atau mengikuti beberapa pola yang kita tidak tahu. namun). Generator nomor acak yang aman secara kriptografis akan mengambil beberapa sumber eksternal entropi untuk membuat perangkat ini tidak deterministik.

Keacakan benar menyiratkan nondeterminisme. Jika deterministik, dapat diprediksi secara akurat (inilah yang dimaksud determinisme); jika bisa diprediksi, itu tidak acak.

Hal terbaik yang bisa Anda dapatkan dari generator angka pseudo-acak deterministik adalah aliran angka yang memiliki siklus yang sangat panjang (non-berulang tidak mungkin kecuali perangkat RNG Anda memiliki penyimpanan tidak terbatas) yang, selama siklus, menghasilkan nomor aliran yang memenuhi semua properti lain dari urutan acak (distribusi nilai yang seragam menjadi yang paling menarik).

Untuk mengatasi masalah ini, banyak UNIX dan suka Unix modern memiliki kernel RNG yang menggunakan sumber noise fisik untuk menghasilkan keacakan yang sebenarnya.

Pendekatan umum lainnya adalah mengambil waktu saat ini sebagai benih untuk RNG deterministik ( srand(time(NULL));dalam C); secara kriptografis, ini tidak berharga, karena waktu sekarang bukan rahasia, tetapi untuk hal-hal seperti simulasi fisik atau video game, itu cukup baik.

Bab kedua dari buku Discrete-Event Simulation: A First Course oleh Lawrence Leemis memberikan pengantar yang fantastis untuk generator nomor acak (atau lebih tepatnya, generator nomor psuedo-acak).

Kutipan dari bukunya menjelaskan dengan baik menurut pendapat saya:

Secara historis tiga jenis generator bilangan acak telah dianjurkan untuk aplikasi komputasi: (a) generator look-up tabel gaya tahun 1950-an seperti, misalnya, tabel perusahaan RAND dengan sejuta digit acak; (B) generator perangkat keras seperti, misalnya, perangkat "white noise" termal; dan (c) generator algoritmik (perangkat lunak). Dari ketiga jenis ini, hanya generator algoritmik yang telah diterima secara luas. Alasan untuk ini adalah bahwa hanya generator algoritmik yang memiliki potensi untuk memenuhi semua kriteria generasi nomor acak yang diterima secara umum berikut. Generator harus:

• acak - mampu menghasilkan output yang melewati semua uji statistik keacakan yang wajar;
• terkendali - dapat mereproduksi outputnya, jika diinginkan;
• portabel - mampu menghasilkan output yang sama pada berbagai sistem komputer;
• efisien - cepat, dengan kebutuhan sumber daya komputer minimal;
• didokumentasikan - dianalisis secara teoritis dan diuji secara ekstensif.

Jadi walaupun dimungkinkan untuk menggunakan generator white-noise untuk mendapatkan angka acak "lebih baik", mereka belum mendapatkan penerimaan karena mereka tidak mengikuti sebagian besar kriteria di atas.

Saya akan merekomendasikan agar Anda mengambil salinan buku itu (atau sesuatu yang serupa). Memahami dengan tepat bagaimana kerja PRNG pasti akan membantu Anda dalam upaya Anda.

Karena Anda perlu menulis kode untuk menghasilkan angka acak dan Kode TIDAK acak. (Ini deterministik)

Jadi, Anda akhirnya mulai dengan "Nilai benih" yang diambil pada "Acak" (biasanya cap waktu saat ini) kemudian menggunakannya dalam algoritma untuk mulai menghasilkan angka. Tetapi seluruh rangkaian didasarkan pada nilai Seed asli!

Jadi jika Anda menjalankan kode Anda lagi dengan nilai Seed yang sama persis, Anda akan mendapatkan SET angka yang sama persis! Bagaimana orang yang masuk akal bisa menyebutnya acak? Tapi itu pasti terlihat acak.

Mengenai membuat mereka unik, Setelah menghasilkan nomor cukup periksa apakah Anda sudah memiliki nomor itu, jika Anda melakukannya, buang dan buat yang baru.

Karena Anda menghasilkan angka acak, Anda harus mengharapkan nilai yang dihasilkan menjadi tidak unik. Ini adalah sifat keacakan - Anda tidak bisa mengatakan urutan angka yang benar-benar acak (atau bahkan pseudo-acak) adalah unik, karena persyaratan itu akan memungkinkan nilai akhir dalam kisaran diprediksi, serta mengubah probabilitas semua nomor yang tidak dipilih setiap kali yang baru dipilih.

Saya memiliki definisi Pseudo Random yang sangat sederhana :

Terlalu banyak variabel yang tidak diketahui untuk diprediksi.

Saya juga memiliki definisi sederhana True Random :

Variabel tak dikenal tak terbatas.

Masalah dengan komputer adalah bahwa ia selalu mengetahui SEMUA variabel. Angka acak hanyalah fungsi matematika dari beberapa nilai seed .
Yang terbaik yang bisa kita lakukan adalah memberikan komputer nilai seed pseudo-random, yang biasanya didasarkan pada variabel yang tidak dapat kita prediksi (seperti waktu yang tepat).

Meskipun komputer benar-benar tidak dapat membuat angka acak, ada baiknya memperkenalkan terlalu banyak variabel untuk diprediksi!

Menghasilkan angka acak dalam perangkat lunak memang tidak mungkin seperti yang ditunjukkan orang lain, namun dimungkinkan dengan perangkat keras untuk membangun perangkat yang dapat menghasilkan angka acak *. Ada beberapa contoh tentang hal ini di internet, dan ada berbagai metode yang digunakan, mulai dari membaca waktu antara kutu pada penghitung Geiger hingga mengambil sampel white noise (sebagian besar radiasi latar belakang dari alam semesta) dari penerima yang tidak dikunci. Saya sendiri telah membangun beberapa menggunakan beberapa metode yang tersedia.

* Fisika geek mana pun yang baik akan menunjukkan bahwa mengingat cara alam semesta beroperasi, tidak ada yang hiper-teknis yang benar-benar acak tetapi tidak ada cara yang masuk akal untuk memprediksi hasilnya sehingga demi diskusi ini mereka cukup.

Tidak mungkin Anda dapat menghasilkan nomor acak tanpa perangkat keras khusus. Pada tahun pertama saya, beberapa teman sekelas dan saya mengusulkan generator angka acak yang pada dasarnya memiliki penerima AM dan disetel ke 4 saluran yang berbeda, dapatkan input ke konverter A ke D dan tambahkan semuanya (modulo nomor maks Anda). Karena kombinasi input analog dari sembarang jumlah stasiun adalah acak dan kami dapat menghasilkan sejumlah besar nomor acak dari konverter A2D kami mengusulkan ini bisa menjadi generator yang baik. Tentu saja, bahkan ini tidak benar-benar acak dalam arti filosofis, meskipun untuk sebagian besar tujuan praktis ini bisa berhasil.

Determinisme pada dasarnya adalah suatu fungsi. Ingat dari Aljabar bahwa suatu fungsi adalah korespondensi antara domain dan rentang sedemikian rupa sehingga setiap anggota domain berkorespondensi dengan tepat satu anggota rentang.

Jadi jika f (x) = z, f (x)! = Y kecuali y adalah z. Itu adalah sebuah fungsi. Bayangkan JavaScript:

function Add(A, B) {
      return A + B;
}

var addedNumber = Add(2,3);//returns 5
addedNumber = Add(2,3);//still 5

Tidak peduli berapa kali Anda menyebutnya Add(2,3)akan selalu kembali 5. Dengan kata lain, Tambah () adalah fungsi deterministik.

Faktor eksternal dapat membuat Add berperilaku dengan cara yang tidak deterministik. Misalnya, jika Anda memasukkan multithreading ke dalam persamaan. Input manusia juga menyebabkan non-determinisme.

Sekarang, di sinilah segalanya menjadi menarik.

"Siapa pun yang menganggap metode aritmatika menghasilkan angka acak, tentu saja, dalam keadaan berdosa."

Catatan Von Neumann menyatakan, "metode aritmatika untuk menghasilkan [...]". Ini tidak berbicara tentang input manusia, konkurensi, kecepatan angin sampel yang dibaca dari instrumen yang tepat atau cara non-algoritmik lainnya untuk menghasilkan input acak ke fungsi deterministik.

Ini hanya menyatakan suatu fungsi atau sistem fungsi tidak akan tiba-tiba menjadi non-deterministik. Dengan kata lain, Tambah (2,3) tidak akan mengembalikan 6 atau apapun selain 5 dengan input yang sama . Itu tidak mungkin.

Penulis kutipan mengambilnya selangkah lebih maju.

Yang terbaik yang bisa kita harapkan adalah angka pseudo-acak, aliran angka yang muncul seolah-olah mereka dihasilkan secara acak.

Konteksnya sebelumnya didefinisikan sebagai "pada perangkat deterministik". Saya bisa mengakhiri argumen di sini. Tetapi, bagaimana jika kita mengubah konteks dengan memperkenalkan elemen baru ke sistem? Unsur non-deterministik ditambahkan sebagai input membuat sistem menjadi sistem non-deterministik. Meskipun, dengan menghilangkan elemen non-deterministik, kita direduksi kembali menjadi sistem deterministik. Jika kita entah bagaimana dapat melacak atau mereproduksi input kita dapat mereproduksi hasilnya. Tetapi seluruh paragraf ini adalah tangetenial dengan apa yang penulis katakan. Ingat konteksnya.

Orang bisa berdebat tentang makna non-determinisme. Sekali lagi, tangetenial. Ingat konteksnya.

Jadi dia benar. Pada perangkat deterministik apa pun , mustahil bagi sistem deterministik untuk menghasilkan hasil acak yang sebenarnya.