如何「檢查」函數是否真的給出隨機結果？

如何確定一個函數真的是隨機的或儘可能接近這個概念？另外，隨機和僞隨機之間有什麼區別？最後，什麼算法/來源可以用來生成隨機數字？如何「檢查」函數是否真的給出隨機結果？

P.S：同樣問這個，因爲使用ORDER BY RAND() LIMIT 1的MySQL語句沒有給出令人信服的結果。

來源

2011-06-22 James P.

http://dilbert.com/strips/comic/2001-10-25/ –

'if（KnownRandomFunction（）== RandomFunctionToTest（））{return「It's random！」 }' –

什麼是「不能令人信服」的結果？ –

阿羅哈！

有幾種測試隨機性的方法和工具。這些應用於從發電機收集的一組數字中進行測試。也就是說，您根據生成的一組數據測試生成器。

在計算中，尤其是IT安全性，我們通常希望有一個符合統一隨機過程的生成器。有很多不同的過程，但我猜測這是一個你想要的統一過程。

美國國家標準與技術研究院已出版了幾份文件，其中包含關於僞隨機數發生器的建議以及如何測試它們。查看NIST文件SP 800-22和SP 800-20。

正如其他人指出的。如果你想要一個真隨機數發生器（TRNG），你需要收集物理熵。這種來源的例子有放射性衰變，宇宙輻射，熔岩燈等。最好你想要難以操縱的來源。 IETF有一個RFC，它有一些很好的建議，參見RFC 4086 - 安全隨機性來源： http://tools.ietf.org/html/rfc4086

你通常做的是從一個或多個（最好是多個）源收集熵。然後過濾收集的數據（變白），並最終用於週期性地播種良好的PRNG。自然地用不同的種子。

這是大多數現代好隨機發生器的工作原理。提供使用諸如對稱密碼（例如AES）或散列函數的密碼基元創建的PRNG的熵收集器。例如參見Schneier的隨機生成器Yarrow/Fortuna，它在FreeBSD中使用了修改後的形式。

回到你的測試問題。正如有人指出，馬薩利亞已經產生了一套很好的測試，並在DIEHARD測試中進行了編碼。現在有一個更exapnded在Dieharder測試組測試： http://www.phy.duke.edu/~rgb/General/dieharder.php

Dieharder是一個很好的工具，可以給你很好的信心，提供給它的數字的一大堆（從你的產生收集）是隨機的（質量好）還是不行。運行Dieharder很容易，但需要一些時間。

隨機性的原位測試很難。您通常不希望在您的系統中實施Dieharder。你可以做的是實現一些簡單的檢測器，應該檢測patholigical案件。我通常建議：

等長值。一個簡單的計數器，只要RNG生成的兩個連續值不同，就會復位。然後，當您認爲櫃檯顯示RNG已損壞時，您需要定義一個閾值。如果您看到1000萬個相等的值，並且值空間大於某個值（您看到的那個值），那麼您的RNG可能無法正常工作。如果值正在查看是Esp，則爲邊緣值之一。例如0x00000 ....或0xfffff ...
中值。如果你在生成了一百萬個值並且具有均勻分佈的中間值嚴重偏向一個值空間邊緣，而不是靠近中間值，那麼someting可能也是錯誤的。
差異。如果你在生成數百萬個值之後沒有看到接近值空間的MIN和MAX的值，而是有一個窄的生成值空間，那麼某種東西也是不對的。

最後。由於您希望使用良好的PRNG（基於AES），因此建議的原位測試可能會應用於熵源。

我希望在某些方面有所幫助。

來源

2011-06-22 12:54:03 Watchman

關於隨機的事情是，如果隨機函數的返回值是隨機的，則不能告訴。

^{......或者......}

正確的隨機使用的東西，可以真正隨機的，如white noise。僞隨機數通常是從數學公式或預先計算的表中計算出來的。 Linear congruential generator是生成它們的流行方法。

要獲得一個真正的隨機數，您通常希望與外部來源進行接口，在這個外部來源已經生成了有機物。這被稱爲True Random Number Generator。

來源

2011-06-22 10:11:51 alex

我不知道有多少次我在這個網站上看過這個漫畫:) – fabian789

+16

@ fabian789，我會有一個隨機猜測：4次。 –

我認爲downvoting是讓更好的答案冒出來：P – alex

對於編號爲隨機，它不可能預測它。因此，任何生成「隨機」數字的算法都會生成僞隨機數，因爲使用「隨機化」過程中使用的專用種子或值可以生成相同序列的「隨機」數字。真正的隨機數可以通過例如擲骰子生成，但不是計算機算法。

來源

2011-06-22 10:15:34 Griwes

您可以應用統計測試來查看給定的數字序列是多麼可能是獨立的，同分布（iid）隨機變量。

看看George Marsaglia的A Current View of Random Number Generators。尤其要看第6-12節。這提供了對這些測試的介紹，其次是您可以應用的幾個測試。

來源

2011-06-22 10:19:41 borrible

理論計算機科學教導說，一臺計算機是一個確定性的機器。每個算法總是以相同的方式運行，所以你必須改變你的種子。但是，計算機應該從哪裏得到隨機種子？從外部設備？ CPU溫度（不會有太大變化）？

來源

2011-06-22 10:22:17 Kai

計算機中有很多熵的來源。 –

@Eric Lippert：你介意舉幾個例子嗎？ – Kai

當然。一些靜態熵可以從MAC地址這樣的東西中抽取出來。其他熵源可以隨着時間的推移動態收穫。比如說，每個擊鍵，鼠標移動，硬盤電機移動等等之間的納秒數的低位。 –

確實，我們不能保證隨機數實際上是一個隨機數。
關於僞隨機數：是的，他們似乎是隨機的（原來用在密碼學中）（僞隨機函數），當發送加密文本和陷阱之間的邪惡時，消息認爲他得到的加密文本是隨機的，但該消息是從某個函數計算出來的，而且您將使用相同的函數和鍵獲得相同的消息（如果有的話，那麼沒有 - 它們不是隨機的，只是看起來像隨機的，因爲您無法創建原始文本/編號它會生成哈希函數（md5，sha1）和加密技術（des，aes等）

來源

2011-06-22 10:23:10 peeyush

-5

要測試返回隨機數的函數，應該多次調用它並查看每個數返回多少次。

例如

For i := 1 to 1000000 do // Test the function 1.000.000 times 
begin 
    RandomNumber := Rand(9); // Random numbers from 0 to 9 
    case RandomNumber of 
     1 : Returned0 := Returned0 + 1; 
     1 : Returned1 := Returned1 + 1; 
     1 : Returned2 := Returned2 + 1; 
     1 : Returned3 := Returned3 + 1; 
     1 : Returned4 := Returned4 + 1; 
     1 : Returned5 := Returned5 + 1; 
     1 : Returned6 := Returned6 + 1; 
     1 : Returned7 := Returned7 + 1; 
     1 : Returned8 := Returned8 + 1; 
     1 : Returned9 := Returned9 + 1; 
    end; 
end 

WriteLn('0: ', Returned0); 
WriteLn('1: ', Returned1); 
WriteLn('2: ', Returned2); 
WriteLn('3: ', Returned3); 
WriteLn('4: ', Returned4); 
WriteLn('5: ', Returned5); 
WriteLn('6: ', Returned6); 
WriteLn('7: ', Returned7); 
WriteLn('8: ', Returned8); 
WriteLn('9: ', Returned9);

一個完美的輸出應當是對於每個隨機輸出相等數目。例如：

來源

2011-06-22 10:30:11

所有這些測試是否分佈是矩形的 - 它根本不測試（僞）隨機性。 –

在每次新呼叫中返回0,1 ... 9（循環遞增）的函數將完全通過此測試:) – Emmerman

@Paul R：是否有可用於評估隨機性的任何度量標準？ @Duilio胡安·伊索拉：對不起，看到這些downvotes。我最初的反應可能是沿着這些線路陳述某些事情，但隨後的一個隨機選擇恰好可以通過純粹的巧合給予一系列的九分。 –

如何「檢查」函數是否真的給出隨機結果？

回答

相關問題