關於隨機數字序列的產生

我是隨機算法的新手，並通過閱讀書籍自己學習。我正在閱讀一本由Mark Allen Wessis提供的數據結構和算法分析書。關於隨機數字序列的產生

假設我們只需要翻轉一枚硬幣;因此，我們必須隨機生成0或1個。一種方法是檢查系統時鐘。時鐘可能將時間記錄爲一個整數，該整數計算自1970年1月1日以來（至少在Unix系統上）的秒數。然後我們可以使用最低位。問題是，如果需要隨機數字的序列，那麼這不起作用。一秒很長時間，並且在程序運行時時鐘可能根本不會改變。即使時間是以微秒爲單位記錄的，如果程序是由本身運行的，那麼將生成的數字序列將遠離隨機的，因爲對發生器的調用之間的時間將是，程序調用。那麼，我們看到真正需要的是一系列隨機數。這些號碼應該顯得獨立。如果硬幣翻轉並出現頭部，則下一個硬幣翻轉應該仍然可能出現頭部或尾部。

以下是對上述文本片段的疑問。

在上面的文字片段「爲秒，我們可以使用最低位計數」，筆者提的是，這是行不通一秒鐘的時間很長，和時鐘可能不會改變」，我的問題是，爲什麼一秒鐘是很長的時間和時鐘會每秒改變，並在什麼情況下作者提到時鐘不變？請求幫助瞭解簡單的例子。
作者如何提及即使是微秒，我們也沒有得到隨機數字序列？

謝謝！

來源

2011-12-15 venkysmarty

這兩條評論都意味着計算機在時鐘方面的運行速度非常快，計算機第二個時間很長。在程序所做的調用之間，時鐘可能不會改變。 – hackartist 2011-12-15 08:23:02

計算機的速度快。我過於簡化了，但如果您的時鐘速度以GHz爲單位進行測量，那麼它可以在1秒內完成數十億次操作。相對而言，1秒是永恆的，所以它有可能不會改變。
如果您的程序正在進行常規操作，則不能保證隨機抽樣時鐘。因此，你不會得到一個隨機數字。

來源

2011-12-15 08:29:04

不要忘記，對於一臺電腦，一秒鐘可以是'永恆'。程序/算法通常在幾毫秒內執行。（第二的千分之一。）

下面的僞代碼：

for(int i = 0; i < 1000; i++) 
    n = rand(0, 1000)

與0和1000之間的隨機數在一個典型的機器填充N A千倍，此腳本執行幾乎立刻。

雖然你通常只在初始化開始種子：

下面的僞代碼：

srand(time()); 
for(int i = 0; i < 1000; i++) 
    n = rand(0, 1000)

一旦初始化種子，然後執行代碼，生成一個看似隨機組數字。當你多次執行代碼時，問題就出現了。可以說，代碼在3毫秒內執行。然後代碼再次以3毫秒執行，但都在同一秒內執行。結果是一組相同的數字。

對於第二點：作者probabaly假定一臺FAST計算機。上面的問題仍然存在......

來源

2011-12-15 08:25:50

使用隨機（或在這種情況下，僞隨機）數字的程序通常需要很多在短時間內。這就是爲什麼簡單地使用時鐘不起作用的原因之一，因爲系統時鐘不會像您的代碼請求新數字一樣快地更新，因此很可能會一遍又一遍地得到相同的結果，直到時鐘變化。在Unix系統中，通常獲取時間的方法只能提供第二個精度，這可能更爲明顯。甚至微秒也沒有真正的幫助，因爲電腦比現在快得多。

要避免的第二個問題是僞隨機值的線性相關性。想象一下，你想隨機地在一個正方形中放置許多點。您將選擇一個x和一個y座標。如果你的僞隨機值是一個簡單的線性序列（就像你從一個時鐘天真地獲得的那樣），你會得到一個對角線，許多點聚集在同一個地方。這並不真正奏效。

僞隨機數發生器的最簡單類型之一，Linear Congruental Generator也有類似的問題，即使它一見不明顯。由於非常簡單的公式

enter image description here