Apakah semua generator bilangan pseudo-acak akhirnya periodik?

Apakah semua generator bilangan pseudo-acak akhirnya periodik? Atau apakah mereka berkala pada akhirnya?

Secara periodik yang saya maksudkan adalah, seperti bilangan rasional, mereka pada akhirnya menghasilkan urutan periodik ...

Dan pseudo-acak berarti generasi algoritmik / matematis angka acak ...

Semua generator pseudorandom yang tidak bergantung pada keacakan luar dan menggunakan jumlah memori terbatas pada akhirnya harus periodik karena mereka memiliki kondisi terbatas. Anda dapat menganggap mereka sebagai automata terbatas deterministik besar yang memiliki status "output" khusus di mana mereka memberikan output. Semua automata terbatas pada akhirnya periodik, sehingga semua generator pseudorandom akhirnya menghasilkan output periodik.

Namun, panjang periode bisa sangat besar. Sebagai contoh, sebuah PRNG dengan keadaan kriptografi 128 bit hanya dapat berputar sekali setiap bit output, dan bahkan jika mengeluarkan satu bit setiap nanosecond, tata surya akan mati sebelum PRNG mengulangi.$2^{128}$

$\sqrt{2}$$\sqrt{2}$

PRNG adalah mesin negara. Jika mereka hanya berbasis pada input internal (berbeda dengan Poker Stars RNG yang merupakan kombinasi perangkat keras dan perangkat lunak, penyemaian sendiri secara terus-menerus dari ... sampel suara) Anda akan mendapatkan (C, S1, ...) di mana C adalah nilai saat ini (atau sebelumnya) dan S1, ... bisa berupa serangkaian status:

Jika ada kemungkinan nilai N (karena memori dibatasi) dari C dan Anda mengulangi N + 1 kali, Anda akan menekan nilai yang sama untuk C setidaknya dua kali. Jika Anda mengulangi 2N + 1 kali, Anda akan menekan nilai yang sama untuk C setidaknya 3 kali.

Misalkan T = (Ct, S1t, S2t) menjadi status tertentu (nilai saat ini dan status lainnya).
Biarkan M = # {nilai untuk S1} X {nilai untuk S2} X {...} menjadi kardinal dari kemungkinan kombinasi keadaan (sekali lagi: karena memori dibatasi).

Jika Anda mengulang NM + 1 kali algoritme, Anda akan mencapai setidaknya dua kali status yang sama (Ct, S1t, S2t, ...), sehingga menghasilkan nilai output yang sama dan urutan keadaan berikut yang sama dari yang pertama kali, dan jadi menjadi berkala.

Contoh sederhana dari urutan pseudo-acak yang tidak periodik: menyatukan representasi biner dari semua bilangan bulat positif, dengan urutan:

110111001011101111000...

(Sebutkan "." Dan ini disebut konstanta biner Champernowne .)

Tentu saja ini bukan kualitas yang sangat tinggi sejauh urutan pseudo-random pergi, tetapi ini menunjukkan bahwa itu mungkin tanpa menggunakan banyak memori.

$\pi$$\sqrt{2}$

Persyaratan memori tanpa batas bukanlah masalah untuk mesin turing, dan mungkin juga tidak ada masalah dalam praktiknya, karena pertumbuhannya sangat lambat, tetapi tergantung pada apa Anda berniat menggunakannya.

$2^{128}$

$2^{128}$