推 sunev:就怕偽亂數太偽嘛...:P 05/19 02:55
> -------------------------------------------------------------------------- <
作者: H45 (!H45) 看板: ask-why
標題: Re: [請益] 亂數表有沒有規律??
時間: Tue May 19 03:47:12 2009
※ 引述《StaticVortex ()》之銘言：
: ※ 引述《semop (semop)》之銘言：
: : 電腦可以產生合乎各種亂數檢測方法、基本上無法逆推的 "真實亂數" (當然
: : 有人不同意這是 "真實" 亂數，但這是定義問題) 。
: : 只是一般來說，產生這種亂數的運算成本甚高。
: : 一個簡單的例子是拿 pi 或 e 值或更不常見的無理數作為基準來製作亂數，
: : 它們沒有常用的亂數方法的循環問題，永遠不會重複產生資料。
: : 但除非是使用硬體方法，無法產生 "自然亂數" 。
: : 現在已經有 http://random.org 這類網站出現，免費公開地提供硬體產生的
: : 自然亂數，以後電腦程式使用的亂數資料應該會逐漸改以自然亂數為主了。
: : 所以大家以後就別說電腦所使用的亂數都一定是假亂數了。這觀念要改一改。
: 對不起我是個門外漢,
: 如果避免了重複使用同一個亂數種子,
: 以及同一個亂數種子產生的亂數不要多過週期,
: 為什麼還需要這種自然亂數呢?
: 譬如以使用者的 input 時間間隔來取種子等等方式, 會遇到什麼限制嗎?
: 使用偽亂數還會遇到什麼樣的問題與困擾呢?
此問題應回歸於：為何需要亂數？
因實際需求，有些亂數要求無法預測以提升系統安全
有些亂數要求分佈足夠均勻以提升搜尋效果
而有些亂數要求模擬真實環境以測試系統容錯能力
基於以上需求，有些情況並非虛擬亂數可以滿足
無法預測的特性乃自然亂數優於虛擬亂數的原因之一
在一般的情況下
虛擬亂數 (如 Java 內建 Random 類別所含演算法) 已經足以應付大部分的需求
好比說：隨機從題庫抓練習題、隨機閱讀網路的一篇文章
並不需要多麼難以預測的亂數源，只要虛擬亂數即可。
然而，需要絕對無法被猜到的情況下，自然亂數比虛擬亂數更加可靠
好比說：隨機產生加密金鑰、隨機產生雜訊
自然亂數保證任何人都無法準確地猜到未來的亂數是多少
畢竟人類還沒有能力預言這個世界的所有細節。
回到原發問者的問題：以使用者的 input 時間間隔來取種子的方式會遇到什麼限制？
假設使用者 input 時間間隔足夠稱為自然亂數 (不是由機器精準地以固定時間輸入)
那麼，此種子即為自然亂數，後面的種種運算都是基於自然亂數的結果
此時間間隔不能說是偽亂數。
然而，如果將自然亂數再做一次虛擬亂數演算法所得到的數值，並不能稱之為自然亂數
因為每一次運算所得到數值都與自然亂數相關
連續做多次虛擬亂數演算法所得到一連串數字彼此之間有關聯
這些數字只能代表同一個自然亂數的衍生物
只要知道第一個數字是多少，後面的數字全部都可以推算出來
相對地，一連串真正的自然亂數是知道第一個數字，仍然無法推算出其他亂數是多少。
舉例而言，你有辦法知道另一個使用者 (人) input 的時間間隔嗎？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.116.247.13
→ HuangJC:亂數的亂度也很重要,以前拿到一個 0x00~0xFF 的亂數時,都 05/19 12:48
→ HuangJC:自己任意擴展到 0x0000~0xFFFF 使用,老實說沒數學底子,心 05/19 12:48
→ HuangJC:裏很虛,不知有沒有造成某一區特別偏重的問題 05/19 12:48
→ HuangJC:人輸入的時間間隔也會受 clock 取樣影響,出現數位化的邊界 05/19 12:49
→ HuangJC:當然如果能以量子級的取樣,那我絕不擔心 :P 05/19 12:50
> -------------------------------------------------------------------------- <
作者: H45 (!H45) 看板: ask-why
標題: Re: [請益] 亂數表有沒有規律??
時間: Tue May 19 19:37:22 2009
:
: 然而，如果將自然亂數再做一次虛擬亂數演算法所得到的數值，並不能稱之為自然亂數
: 因為每一次運算所得到數值都與自然亂數相關
: 連續做多次虛擬亂數演算法所得到一連串數字彼此之間有關聯
: 這些數字只能代表同一個自然亂數的衍生物
: 只要知道第一個數字是多少，後面的數字全部都可以推算出來
: 相對地，一連串真正的自然亂數是知道第一個數字，仍然無法推算出其他亂數是多少。
:
: 舉例而言，你有辦法知道另一個使用者 (人) input 的時間間隔嗎？
:
: --
: ※ 發信站: 批踢踢實業坊(ptt.cc)
: ◆ From: 140.116.247.13
: → HuangJC:亂數的亂度也很重要,以前拿到一個 0x00~0xFF 的亂數時,都 05/19 12:48
: → HuangJC:自己任意擴展到 0x0000~0xFFFF 使用,老實說沒數學底子,心 05/19 12:48
: → HuangJC:裏很虛,不知有沒有造成某一區特別偏重的問題 05/19 12:48
亂度我不清楚是什麼，但是我知道均勻度可以用數字簡單估測。
假設你說的亂度就是我說的均勻度
我必須提出一點：
自然亂數的分佈不太均勻
若自然亂數比任何虛擬亂數都均勻
那麼下一個時間點的自然亂數比虛擬亂數更容易預測
然而事實卻是自然亂數比虛擬亂數還要難預測，而且自然亂數的分佈並沒有比較均勻
換言之，以均勻為目標的虛擬亂數反而比自然亂數還要均勻。
回到你的問題，0x00~0xFF 擴展至 0x0000~0xFFFF 是非 onto 的對映關係
也就是說，有些對應域的數值不會被定義域的數值對映到。
如果你早就知道這一點的話，下一個問題是「會不會有某一區特別偏重」
答案是視你的亂數產生法而定，就我所知的三個亂數產生法而言
有些亂數產生法非常不均勻，但是很難預測下一個時間點運算出來的亂數
也有些亂數產生法非常均勻，可是用人腦都知道下一個時間點算出來的會是多少。
以你擔心某一區偏重的問題而言
可以用均勻分佈之亂數產生器來解決
(附帶一提，Java 內建的 Random 之演算法是屬於不均勻，但是很難預測的那種)
: → HuangJC:人輸入的時間間隔也會受 clock 取樣影響,出現數位化的邊界 05/19 12:49
: → HuangJC:當然如果能以量子級的取樣,那我絕不擔心 :P 05/19 12:50
取樣得愈細，某位數以下的數值愈可以當作亂數 (想像細至 1E-10 cm)
這麼小的數值，幾乎可以歸至誤差或是雜訊
只要誤差或雜訊干擾大到某個程度 (想像誤差是 -1E-9 ~ 1E-9 cm)
下一個時間點的取樣結果幾乎不可能被預測，畢竟人類還沒辦法完全掌握誤差和雜訊。
以你說的 clock 取樣影響，人輸入的時間間隔之最小單位就是一個 clock
但是人輸入的時間間隔難以預測，再加上其他電路的干擾
可以讓誤差大過 clock 取樣的好幾倍……這樣還需要擔心亂數不亂嗎？
我是不太懂為什麼一定要到量子級才不用擔心，難道 clock 還不夠細...?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.117.172.148
推 HuangJC:實際上繪圖時會出現一些特定形狀;是由此再反推猜測的 05/19 22:31
→ HuangJC:比如求 PI 值的一個統計方法,是用正方型和圓形面積的比值 05/19 22:32
→ HuangJC:我如果跑完所有 pixel,當然可以求出比值;但不想跑所有點時 05/19 22:32
→ HuangJC:我會用亂數去跑點,而又希望亂數夠平均,可當統計上的取樣 05/19 22:33
→ HuangJC:總之有很多方法可以繪圖,但圖裏卻出現一條直線.. 05/19 22:34
→ H45:以亂數在二維平面上隨機取點卻繪出一條直線的機率也太低了吧 05/20 05:16
推 HuangJC:因為沒有很均勻呀.. 05/20 10:33
→ H45:不對，不均勻和繪出一條直線是極不相似的概念 05/20 11:14
→ H45:我看到你回文了，請先無視我上面這行推文 05/20 11:24
→ HuangJC:好的式子可以解決直線啦;一定有解,只是我要數學家幫忙呀 05/20 11:39
→ HuangJC:我是在說,以一般功力來講,我懷疑我解得好不好.. 05/20 11:40
→ HuangJC:所以我後來對有序的偽亂數公式很佩服 ~^_^~ 05/20 11:40
> -------------------------------------------------------------------------- <
作者: HuangJC (吹笛牧童) 看板: ask-why
標題: Re: [請益] 亂數表有沒有規律??
時間: Wed May 20 11:17:34 2009
: 回到你的問題，0x00~0xFF 擴展至 0x0000~0xFFFF 是非 onto 的對映關係
這個 onto 我不會翻譯..
: 也就是說，有些對應域的數值不會被定義域的數值對映到。
: 如果你早就知道這一點的話，下一個問題是「會不會有某一區特別偏重」
: : → HuangJC:人輸入的時間間隔也會受 clock 取樣影響,出現數位化的邊界 05/19 12:49
: : → HuangJC:當然如果能以量子級的取樣,那我絕不擔心 :P 05/19 12:50
: → H45:以亂數在二維平面上隨機取點卻繪出一條直線的機率也太低了吧 05/20 05:16
: 推 HuangJC:因為沒有很均勻呀.. 05/20 10:33
int r=random(); // 0x00~0xFF
//欲擴擴至 0x0000~0xFFFF,從前的精典做法是用乘法擴展
//而我用過的 basic 指令是從浮點數開始的
double R=r/256.0; // 0.0~1.0
int result=R*65536; //0x0000~0xFFFF
事實上 result 只會有 256 種變化,也許這就是你說的 非onto
把這 256 種變化撒在繪圖平面上,就變出 256 條直線了
當然直線只是隱隱約約,但眼睛看得出來
一個很簡單的方法是直接移位擴展
int r=random()<<8|random(); //0x0000~0xFFFF
但我不清楚前8位元如果和後8位元間形成某種數學關係
(因為想要均勻,且沒引入任何外部種子,所以我只好用虛擬亂數)
會不會出現的亂數冒出很巧的規律
比如,第 0,2,4,6 偶數次的亂數是外部引入(鍵盤點擊時間)亂數好了
而第 1,3,5,7 奇數次的亂數是前一次直接乘2(溢位丟棄) XD
是的,我故意用了可觀察的邏輯,但的確造出很慘的效果
r=0x0000;
r=0x0102;
r=0x0204;
r=0x0408; //比如這個,前面04時,後面就只可能 08,不可能有其他值
點擊鍵盤和取樣頻率間的關係也類似這樣
雖然我點擊鍵盤的速度有無限種可能 (限制在 0~1秒間,但速度仍有無限多種)
但我的取樣頻率只有 10次/1秒 ,那取回的亂數值就只有 10種
雖然你主張頻率本身也會受雜訊干擾
但總之我的讀值只有 1~10
雜訊並不會進入我的讀值,這就是數位化呀~
另一種講法是我讀回的是秒數,所以 10次/1秒 可讀回的點是
0.1,0.2,0.3~~~ 1.0 這樣好了,但讀值不是 0.1秒
因為雜訊使 clock 飄移,可能讀回 0.11秒 或 0.09秒
這其實是有兩組不同的頻率才做得到
一個做 wait ,一個去讀秒,所以才能讀到 0.11 or 0.09
不然再怎麼漂我也不會讀到小數下兩位
而即使如此,雜訊也不會太大,不足以把讀值打散到均勻
我們將會看到繪出的直線在 0.1 的附近抖動(總共有十條直線)
這怎麼辦?還是不能用的
事實上我可以用前面談的移位擴展來做(這次談十進制)
random() spec : 1~10 ,剛才說鍵盤亂數只有這樣的辨識度
int R=(random()-1)*10+(random()-1); //這樣擴展成 0~99 了
好像蠻理想的 XD
不過同一個人打字有相似的均勻度
會不會連續取樣時都落在 0.3~0.7 之間
而 0.1 一直沒出現呢?
一直沒出現我還是不能用啊,結果是要把統計及權重搬出來
幫我把亂數拉散變成平均分佈嗎?
(讀到 0.3 變 0.1,讀到 0.7 變 1.0;而且不是線性擴展)
總之,一個來源不均勻的東西,還要用一堆數學式去搓它
搓不好在繪圖時就看到一條一條有序的線
就說雜訊好了,在 EMI 實驗室也會看到不像雜訊的雜訊
一般解釋當然是環境噪音
不過環境噪音在反射的過程中可能會特別出現整數倍的共鳴
(好像有輛車的喇叭發出 Do,結果高八度低八度的 Do 同時都共鳴了)
一般我們測的 IC 如果在某頻率有雜訊
那麼整數倍的頻率也可以觀察一下是不是也有雜訊
更別說全天下都在流行某頻率時 (比如 GSM 雙頻手機,你帶進來不就專搞這雙頻?)
一起開機..一起來,變得很規律 *_*
結果雜訊就好像海浪,它不是均勻的
它是一波一波的,還會漲潮退潮 XD
你說海浪的成因很複雜嗎?受全世界所有生物泡澡排洩的影響
但你明明看到它的拍打還蠻有頻率的不是?
我看這堆雜訊還是有共鳴的 *_*
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.219.65.16
推 Aipr:onto: 映成。個人意見, 不翻譯比較好懂 05/20 12:41
→ StaticVortex:你說的線像下面那個網站裡那樣嚴重嗎? 05/21 00:21
→ HuangJC:對 *_*,你以為做出亂數了,但眼睛又看得到規則.. 05/21 00:36
推 KanoLoa:真是太有趣了 XD 05/21 19:37
> -------------------------------------------------------------------------- <
作者: H45 (!H45) 看板: ask-why
標題: Re: [請益] 亂數表有沒有規律??
時間: Wed May 20 11:43:12 2009
※ 引述《HuangJC (吹笛牧童)》之銘言：
: : 回到你的問題，0x00~0xFF 擴展至 0x0000~0xFFFF 是非 onto 的對映關係
: 這個 onto 我不會翻譯..
: : 也就是說，有些對應域的數值不會被定義域的數值對映到。
: : 如果你早就知道這一點的話，下一個問題是「會不會有某一區特別偏重」
: : → H45:以亂數在二維平面上隨機取點卻繪出一條直線的機率也太低了吧 05/20 05:16
: : 推 HuangJC:因為沒有很均勻呀.. 05/20 10:33
: int r=random(); // 0x00~0xFF
: //欲擴擴至 0x0000~0xFFFF,從前的精典做法是用乘法擴展
: //而我用過的 basic 指令是從浮點數開始的
: double R=r/256.0; // 0.0~1.0
: int result=R*65536; //0x0000~0xFFFF
: 事實上 result 只會有 256 種變化,也許這就是你說的 非onto
: 把這 256 種變化撒在繪圖平面上,就變出 256 條直線了
: 當然直線只是隱隱約約,但眼睛看得出來
: 一個很簡單的方法是直接移位擴展
: int r=random()<<8|random(); //0x0000~0xFFFF
: 但我不清楚前8位元如果和後8位元間形成某種數學關係
: (因為想要均勻,且沒引入任何外部種子,所以我只好用虛擬亂數)
: 會不會出現的亂數冒出很巧的規律
: 比如,第 0,2,4,6 偶數次的亂數是外部引入(鍵盤點擊時間)亂數好了
: 而第 1,3,5,7 奇數次的亂數是前一次直接乘2(溢位丟棄) XD
: 是的,我故意用了可觀察的邏輯,但的確造出很慘的效果
: r=0x0000;
: r=0x0102;
: r=0x0204;
: r=0x0408; //比如這個,前面04時,後面就只可能 08,不可能有其他值
我直接和你說結論：虛擬亂數不是這樣做的。
一個看似很亂的亂數，必須做很大的質數運算
為了計算量的效率，通常會只取最小的幾個位數來運算。
以你的例子而言好了，想要從 0x00 ~ 0xFF 擴展到 0x0000 ~ 0xFFFF
為了符合亂數的大質數運算原則，最好連續取 2 次亂數
再將這兩個亂數排在一起即可。
舉例而言：第一次取的亂數是 0x01, 第二次取的亂數是 0x02
那麼此次得到的亂數擴展到 0x0000 ~ 0xFFFF 就是 0x0102
如果你真的懂亂數產生法的話
應該知道第二次取的亂數是從第一次取完亂數之後的種子做大質數運算而得的吧。
: 點擊鍵盤和取樣頻率間的關係也類似這樣
: 雖然我點擊鍵盤的速度有無限種可能 (限制在 0~1秒間,但速度仍有無限多種)
: 但我的取樣頻率只有 10次/1秒 ,那取回的亂數值就只有 10種
: 雖然你主張頻率本身也會受雜訊干擾
: 但總之我的讀值只有 1~10
: 雜訊並不會進入我的讀值,這就是數位化呀~
: 另一種講法是我讀回的是秒數,所以 10次/1秒 可讀回的點是
: 0.1,0.2,0.3~~~ 1.0 這樣好了,但讀值不是 0.1秒
: 因為雜訊使 clock 飄移,可能讀回 0.11秒 或 0.09秒
: 這其實是有兩組不同的頻率才做得到
: 一個做 wait ,一個去讀秒,所以才能讀到 0.11 or 0.09
: 不然再怎麼漂我也不會讀到小數下兩位
: 而即使如此,雜訊也不會太大,不足以把讀值打散到均勻
: 我們將會看到繪出的直線在 0.1 的附近抖動(總共有十條直線)
: 這怎麼辦?還是不能用的
: 事實上我可以用前面談的移位擴展來做(這次談十進制)
: random() spec : 1~10 ,剛才說鍵盤亂數只有這樣的辨識度
: int R=(random()-1)*10+(random()-1); //這樣擴展成 0~99 了
: 好像蠻理想的 XD
: 不過同一個人打字有相似的均勻度
: 會不會連續取樣時都落在 0.3~0.7 之間
: 而 0.1 一直沒出現呢?
: 一直沒出現我還是不能用啊,結果是要把統計及權重搬出來
: 幫我把亂數拉散變成平均分佈嗎?
: (讀到 0.3 變 0.1,讀到 0.7 變 1.0;而且不是線性擴展)
: 總之,一個來源不均勻的東西,還要用一堆數學式去搓它
: 搓不好在繪圖時就看到一條一條有序的線
: 就說雜訊好了,在 EMI 實驗室也會看到不像雜訊的雜訊
: 一般解釋當然是環境噪音
: 不過環境噪音在反射的過程中可能會特別出現整數倍的共鳴
: (好像有輛車的喇叭發出 Do,結果高八度低八度的 Do 同時都共鳴了)
: 一般我們測的 IC 如果在某頻率有雜訊
: 那麼整數倍的頻率也可以觀察一下是不是也有雜訊
: 更別說全天下都在流行某頻率時 (比如 GSM 雙頻手機,你帶進來不就專搞這雙頻?)
: 一起開機..一起來,變得很規律 *_*
: 結果雜訊就好像海浪,它不是均勻的
: 它是一波一波的,還會漲潮退潮 XD
: 你說海浪的成因很複雜嗎?受全世界所有生物泡澡排洩的影響
: 但你明明看到它的拍打還蠻有頻率的不是?
: 我看這堆雜訊還是有共鳴的 *_*
我只回一句話，看能不能了解：
巨觀下，看似一切平靜；微觀下，卻非常混亂。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.116.247.13
推 HuangJC:如果巨觀起伏的值可以取出直流成份予以濾除,我可以承認這 05/20 20:27
→ HuangJC:個亂數夠均勻;但取直流成份的公式,還是有賴數學家.. 05/20 20:28
> -------------------------------------------------------------------------- <
作者: littleshan (我要加入劍道社!) 看板: ask-why
標題: Re: [請益] 亂數表有沒有規律??
時間: Wed May 20 11:49:23 2009
※ 引述《HuangJC (吹笛牧童)》之銘言：
: 點擊鍵盤和取樣頻率間的關係也類似這樣
: 雖然我點擊鍵盤的速度有無限種可能 (限制在 0~1秒間,但速度仍有無限多種)
: 但我的取樣頻率只有 10次/1秒 ,那取回的亂數值就只有 10種
我只能說
你在這邊的做法就錯了
一般是這樣
1. GetLocalTime() // 或是 gettimeofday() 或是 RDTSC, whatever
2. 等待 user 敲鍵盤
3. GetLocalTime()，然後和 1. 取得的值相減
Windows 上 GetLocalTime 精確度是 0.001 秒，
POSIX 的 gettimeofday 精確度是 0.000001 秒，
RDTSC 更猛，是看 CPU clock rate 的，
1G 的 CPU 就是以 0.0000000001 秒為單位
以這種方法取得時間差的個位數字
基本上相當難以預測
若你的手能夠以亳秒為單位做動作
只能說你有一雙神之手
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.87.151.2
推 HuangJC:取十次的精度是為了描述問題,並不是真的只取十次 05/20 12:15
→ HuangJC:而且若出現靶心集中,那就不夠均勻 05/20 12:15
→ HuangJC:以前有一個亂數表就是讓你丟筆,看戳中什麼就是亂數,該表愈 05/20 12:16
→ HuangJC:近靶心,格子愈小 05/20 12:16
→ HuangJC:去頭去尾取中間當然是不錯,但也只是不錯而已.. 05/20 12:17
→ littleshan:我是說，你提到「打字間隔集中在0.3~0.7秒」的問題 05/20 12:30
→ littleshan:只要用高精確度的 timer 就可以解決 05/20 12:31
→ littleshan:除非你的手能控制打字間隔落在 X.XX3 秒至 X.XX7 秒間 05/20 12:32
> -------------------------------------------------------------------------- <
作者: HuangJC (吹笛牧童) 看板: ask-why
標題: Re: [請益] 亂數表有沒有規律??
時間: Wed May 20 20:24:06 2009
: → littleshan:我是說，你提到「打字間隔集中在0.3~0.7秒」的問題 05/20 12:30
: → littleshan:只要用高精確度的 timer 就可以解決 05/20 12:31
: → littleshan:除非你的手能控制打字間隔落在 X.XX3 秒至 X.XX7 秒間 05/20 12:32
首先說,我看不懂前一篇的質數;我就是需要一個數學家來幫我
(這樣我就不必多回一篇了)
再來我提一下我不懂的細節,而且我不認為夠密就當然夠均勻
舉例來說,如果我有一個夠均勻的亂數,十種變化
int r=random(); // 0~9
我要把它縮小到 9種變化
int R= (r/9.0)*8; // 0~8
這樣,因為不是擴展,絕對不可能有變化太少的問題
但可能偏重於某幾個變化
假設亂數函式並不亂,只是均勻,只是我做證明的工具
我當然可以給它一個偽函式,就簡單遞增,到最大值時繞捲為 0 好了
於是,r= 0,1,2,3,4,5,6,7,8,9 依序十次
而 R= 0,0,1,2,3,4,5,6,7,8 以無條件捨去來做浮點轉換
反正就算你要四捨五入也會有一樣的問題
好,以上 0 出現兩次
亂數的均勻度要大量才能趨近,否則我只有9種值卻要求做10次,當然不可能公平
那我們做90次好了 (9和10的公倍數;我隱隱聞到質數的道理,但又無法了解)
這90次裏,我希望 r 均勻出現 0~9 九次
然後 R=f(r) 這個公式要改一下,就可以讓 0~8 均勻出現十次
(九十次做完次數才對就好了;但簡單的答案中,循環出現也是可以接受的
因為我不討論有多亂,只先討論均勻)
從這裏可以看出,如果我只有簡單的公式做 R=f(r)
那麼做十次,R=0 會重覆出現兩次
做90次呢?它重覆出現 20次
而畫成圖會怎樣?就是在 R=0 的位置比較粗,變一條直線
不均勻就是這樣呀~
因為只有用簡單的公式去把原始亂數擴展或縮小到我要的範圍
原本的 0x00~0xFF 擴展成 0x0000~0xFFFF,我還算有直覺去解
然後我可以把 65536 的變化程度向內縮,去滿足任何一種(小於65536)範圍的亂數需求
但是這條不均勻惹出的直線,始終會非常明顯
光要亂數是有啦
但好像尾牙抽獎,0號那位同仁每次都比別人多一個中獎機會
你說,這亂數公平嗎?
或者我不要用乘法,用捨去法可以嗎?
R=r,但當 r=9 時,重抽一次
這樣我可不可以聲明 R 的均勻度公平了?
只是有 1/10 的機率會使計算減慢(重抽一次)
當然,大部份時候,這樣設計程式都叫想太多
我們很簡單的把原始亂數除到變成 0~1 的浮點數再乘開就好了
沒有人會知道其實他天生中獎率就比別人低了
只怪他命不好 :P
不好意思,也有黑心程式 XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.219.65.16
推 sunev:把9丟掉就好啦？ 05/20 21:20
如果可以,好像最省事 XD,但如果我要縮至 0~3..總之小心累死,不斷重抽..
※ 編輯: HuangJC 來自: 61.219.65.16 (05/20 22:14)
> -------------------------------------------------------------------------- <
作者: littleshan (我要加入劍道社!) 看板: ask-why
標題: Re: [請益] 亂數表有沒有規律??
時間: Wed May 20 23:48:58 2009
※ 引述《HuangJC (吹笛牧童)》之銘言：
[deleted]
: 當然,大部份時候,這樣設計程式都叫想太多
: 我們很簡單的把原始亂數除到變成 0~1 的浮點數再乘開就好了
: 沒有人會知道其實他天生中獎率就比別人低了
: 只怪他命不好 :P
: 不好意思,也有黑心程式 XD
我大概了解了你的意思
然而隨著 random number 的值域愈大
你所說的機率偏差也會隨之縮小
一般程式設計師並不會拿 0.0~0.9 僅有十種變化的 random variable
直接拿去乘 9.0 再做個 floor()
然後就說這是個 0~8 之間的 uniform random integer
若你的原始亂數是 0.000 ~ 0.999 有 1000 種可能
那麼經過運算後
出現 0 的機率僅比出現其它數字的機率大了 0.001
若你的原始亂數是小於 1.0 的 IEEE754 single-precision floating point
機率偏差為 2^-23
這個數字...八百萬分之一
說實話已經很小了 浮點運算誤差造成的影響還比較大
如果不滿意，你還可以改用 double
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.217.30.156
※ 編輯: littleshan 來自: 61.217.30.156 (05/20 23:55)
推 HuangJC:不只 R=0 那兒會重覆,事實上有可能出現週期性的重覆 05/21 00:47
→ HuangJC:比如要把原本三個值塞進兩個值裏,那麼兩個值中就有一個是 05/21 00:47
→ HuangJC:另一個的兩倍機率;然後週期性的畫成條紋圖了.. 05/21 00:48
> -------------------------------------------------------------------------- <
作者: StaticVortex () 看板: ask-why
標題: Re: [請益] 亂數表有沒有規律??
時間: Wed May 20 23:52:34 2009
感謝回應,
提供幾點迴響,
也許有誤或不足,
希望不吝指教.
關於以使用者擊鍵時間間隔為亂數種子,
可能會由於作業系統對鍵盤緩存的設計,
使得當程式要求讀值時,
在緩存中的幾筆資料在很短的時間內送往程式,
也就失去了原來自然亂數的性質.
https://www.random.org/randomness/
For example, it can be tricky to use keystrokes in this fashion,
because keystrokes are often buffered by the computer's operating system,
meaning that several keystrokes are collected
before they are sent to the program waiting for them.
To a program waiting for the keystrokes,
it will seem as though the keys were pressed almost simultaneously,
and there may not be a lot of randomness there after all.
http://msdn.microsoft.com/en-us/library/aa459265.aspx
Keystrokes occur asynchronously with user action
while the I/O Manager sends the driver an IRP for the read request.
The driver gives the appearance of simultaneously receiving input
from the device and passing the keystroke data to I/O Manager
by maintaining a buffer of keystrokes.
在應用自然亂數於資訊安全時,
如果重複使用虛擬亂數產生器作為新種子,
通常會使產生的亂數品質變差,
http://www.lavarnd.org/faq/prng.html
To achieve output unpredictability of high quality PRNG,
one must start with an unpredictable seed.
Using second PRNG to create the seed does not help
because that simply transfers the problem of seeding onto the second PRNG.
Worse yet, using a PRNG to repeatedly seed another (or even worse the same)
PRNG usually degrades the quality of the output.
但在這篇專利 http://www.google.com/patents?id=ou0gAAAAEBAJ
(
www.lavarnd.org 前身 lavarand 使用的技術
參見 http://www.wired.com/wired/archive/11.08/random.html
Lavarand, a patented system that used Lava Lites to help generate random
numbers. (Patent 5,732,138: "Method for seeding a pseudo-random number
generator with a cryptographic hash of a digitization of a chaotic system.")
)
它將經由渾沌系統產生的自然亂數先雜湊過後再作為種子,
" the present invention pertains to an apparatus and method
for producing a seed for a pseudo-random number generator
from hashing the digitization of a chaotic source.
其理由這麼說
" The cryptographic hashing function serves several purposes.
The cryptographic hash make it difficult to predict the chaotic system.
Furthermore, small variations in the digitized chaotic system
will produce extremely different binary strings.
In addition, knowledge about the cryptographic hash
yields no information regarding the chaotic system.
其舉了 state of clouds 作為例子說明
locality inherent 使渾沌系統在某些程度上可以被預測,
而使用 hash function 轉換 後 可以消抹 locality inherent 性質.
( given hash(x) , it is hard to find hash(x+1) )
不過經過一次雜湊, 為什麼不會像前面引文所指,反而使亂數品質變差呢?
如果跳過雜湊, 直接將自然亂數作為亂數種子丟到虛擬亂數產生器所產生的金鑰,
沒辦法有效消抹 locality inherent 性質 嗎?
※ 引述《H45 (!H45)》之銘言：
: 此問題應回歸於：為何需要亂數？
: 因實際需求，有些亂數要求無法預測以提升系統安全
: 有些亂數要求分佈足夠均勻以提升搜尋效果
: 而有些亂數要求模擬真實環境以測試系統容錯能力
: 基於以上需求，有些情況並非虛擬亂數可以滿足
: 無法預測的特性乃自然亂數優於虛擬亂數的原因之一
: 在一般的情況下
: 虛擬亂數 (如 Java 內建 Random 類別所含演算法) 已經足以應付大部分的需求
: 好比說：隨機從題庫抓練習題、隨機閱讀網路的一篇文章
: 並不需要多麼難以預測的亂數源，只要虛擬亂數即可。
: 然而，需要絕對無法被猜到的情況下，自然亂數比虛擬亂數更加可靠
: 好比說：隨機產生加密金鑰、隨機產生雜訊
: 自然亂數保證任何人都無法準確地猜到未來的亂數是多少
: 畢竟人類還沒有能力預言這個世界的所有細節。
: 回到原發問者的問題：以使用者的 input 時間間隔來取種子的方式會遇到什麼限制？
: 假設使用者 input 時間間隔足夠稱為自然亂數 (不是由機器精準地以固定時間輸入)
: 那麼，此種子即為自然亂數，後面的種種運算都是基於自然亂數的結果
: 此時間間隔不能說是偽亂數。
: 然而，如果將自然亂數再做一次虛擬亂數演算法所得到的數值，並不能稱之為自然亂數
: 因為每一次運算所得到數值都與自然亂數相關
: 連續做多次虛擬亂數演算法所得到一連串數字彼此之間有關聯
: 這些數字只能代表同一個自然亂數的衍生物
: 只要知道第一個數字是多少，後面的數字全部都可以推算出來
: 相對地，一連串真正的自然亂數是知道第一個數字，仍然無法推算出其他亂數是多少。
: 舉例而言，你有辦法知道另一個使用者 (人) input 的時間間隔嗎？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.42.20.13
→ StaticVortex:對了, 如果自然亂數不比某些虛擬亂數均勻, 05/21 00:07
→ StaticVortex:那麼在運用 random sampling 時, 應該用哪種呢? 05/21 00:07
推 HuangJC:我倒認為對取樣來說,只要均勻就有價值了;而 random 是防止 05/21 03:03
→ HuangJC:投機;比如取樣100次,得到的數據放大到10000次,如果我的取 05/21 03:04
→ HuangJC:樣方式被摸透,就有人會投機塞樣本給我;只擔心這件事而已 05/21 03:04
推 HuangJC:另外,只要知道第一個數就可以推出一連串亂數,這很好破呀 05/21 03:07
→ HuangJC:改用第一及第二個數同時運算產生第三個數就好;不必引入自 05/21 03:07
→ HuangJC:然亂數啦 :P 05/21 03:08
→ HuangJC:我是說,不必永遠依賴自然亂數 05/21 03:08
> -------------------------------------------------------------------------- <
作者: littleshan (我要加入劍道社!) 看板: ask-why
標題: Re: [請益] 亂數表有沒有規律??
時間: Thu May 21 17:46:17 2009
※ 引述《littleshan (我要加入劍道社!)》之銘言：
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.217.30.156
※ 編輯: littleshan 來自: 61.217.30.156 (05/20 23:55)
推 HuangJC:不只 R=0 那兒會重覆,事實上有可能出現週期性的重覆 05/21 00:47
以 r=0.000~0.999 的例子來看
的確就只有 R=0 的機率比其它值高一點點
P( R=0 ) = P( 0.000 <= r <= 0.111 ) = 0.112
P( R=1 ) = P( 0.112 <= r <= 0.222 ) = 0.111
...
P( R=8 ) = P( 0.889 <= r <= 0.999 ) = 0.111
→ HuangJC:比如要把原本三個值塞進兩個值裏,那麼兩個值中就有一個是 05/21 00:47
→ HuangJC:另一個的兩倍機率;然後週期性的畫成條紋圖了.. 05/21 00:48
你一直把焦點集中在這種極端情況 當然偏差會很明顯
像這種情況 取十次 3-state random variable 再去轉換成 2-state random variable
那麼機率偏差是 3^-10 大約是六萬分之一
甚至你可以用 rejection sampling
0, 1, 2 三種情況，抽到 2 就重新 sample
看起來重新 sample 的機率達 1/3 似乎效率很差
但平均而言，僅需 1.5 次的 sampling 就可以取得無偏差的 random variable
效率甚至比前述取十次的方法還好 (以 amortized analysis 的角度)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.87.151.2