「華人戴明學院」是戴明哲學的學習共同體 ,致力於淵博型智識系統的研究、推廣和運用。 The purpose of this blog is to advance the ideas and ideals of W. Edwards Deming.

2016年5月29日 星期日

New Method of Producing Random Numbers. A Million Random Digits THE SEQUEL: with Perfectly Uniform Distribution




A Million Random Digits THE SEQUEL: with Perfectly Uniform Distribution [Paperback] David Dubowski (Author)
Finally, after 56 years the saga continues! Here is the next book of random numbers, pseudorandom actually, this time generated purely by mathematics. The familiar table form continues, but this set has perfectly uniform distribution. Using the Pi Crust Shuffler algorithm, a modern PC quietly churned out these 400 pages of delightful digits, ready for action in the real world. Any math lover would be delighted to receive this book as a gift! The algorithm's BASIC source code is included.


These Amazon Products Are No Joke, But the Online Reviews Are
Whether on Books About Random Digits Or Toilet Seats, Everybody's a Comedian
By MICHAEL M. PHILLIPS
What is it about the book "A Million Random Digits With 100,000 Normal Deviates" that brings out the wiseguy in people?

Smart-aleck customers are flexing their comedy muscles on Amazon, with snarky reviews and silly photos of products like banana slicers and fresh whole rabbit. WSJ's Michael M. Phillips reports.
Rand Corp.'s 600-page paperback, which delivers exactly what it promises, sells for $64.60 on Amazon.com AMZN -2.20% . Yet 400 people have submitted online Amazon reviews, most of them mocking the 60-year-old reference book for mathematicians, pollsters and lottery administrators.
"Almost perfect," said one reviewer. "But with so many terrific random digits, it's a shame they didn't sort them, to make it easier to find the one you're looking for."
Five stars from this commenter: "[T]he first thing I thought to myself after reading chapter one was, 'Look out, Harry Potter!' "
Several reviewers complained that while most of the numbers in the book appeared satisfactorily random, the pages themselves were in numerical order.
Amazon's online superstore has become the unlikely stage for 21st-century amateur comedy, where thousands of customers have submitted reviews for products ranging from the self-explanatory explanatory book "How to Avoid Huge Ships" to the Hutzler 571 banana slicer, a yellow plastic banana-shaped device that cuts bananas into even slices.
Rand said its long list of random numbers, first published in 1955, is one of its all-time best sellers. "It's a tool of some sort, but it's beyond my clear understanding," a Rand spokesman admitted.
One Amazon reviewer panned a real-life copycat publication called "A Million Random Digits THE SEQUEL: with Perfectly Uniform Distribution." "Let's be honest, 4735942 is just a rehashed version of 64004382, and 32563233 is really nothing more than 97132654 with an accent."
"We are always amazed by the creativity of our customers," said an Amazon spokeswoman...

 more: http://online.wsj.com/article/SB10001424127887323528404578454763919379102.html?mod=djemITPE_h


-----

New Method of Producing Random Numbers Could Improve ...

news.utexas.edu/2016/.../computer-science-breakthrough-could-improve-cybersecurit...

May 16, 2016 - Computer science professor David Zuckerman and graduate student Eshan Chattopadhyay will present research about their method in June at ...

Academics Make Theoretical Breakthrough in Random Number ...

https://threatpost.com/academics-make-theoretical-breakthrough...random.../118150/

May 17, 2016 - David Zuckerman, a computer science professor, and Eshan Chattopadhyay, a graduate student, published a paper in March that will be ...


隨機亂數生成演算法獲突破 五月 28, 2016 (photo by James Bowe)


本文來自於 sciencenews.org《New technique produces real randomness》,36氪翻譯

隨機亂數在軟體的應用非常廣泛。比如說抽獎程式就是一下能想到的應用之一。但是在一些更加重要的應用當中隨機亂數也發揮著重要的作用,比如加密敏感訊息、對地球天氣等複雜系統建模以及數據的公正採樣等都離不開隨機亂數。

不過電腦生成隨機亂數要比擲骰子困難得多,而且那些隨機亂數實際上並不是完全不可預測的,而是在隨機種子的基礎上結合演算法自動生成的「數」,這些「數」實際上是可複製的,算不上真正的隨機(偽隨機亂數)。所以隨機亂數的隨機性問題是基礎演算法面臨的一大難題。

不過最近德州大學的兩位電腦科學家 Eshan Chattopadhyay 和 David Zuckerman 開發出了一種改進的隨機抽樣器,這種算法只需要兩種隨機性不強的來源即可生成真正隨機的數字,被認為是基礎算法取得的一大突破。

一般的隨機算法為了提高隨機性會在演算法中引入環境的隨機性,比如滑鼠或鍵盤的位置等。電腦會採樣若干時間點的滑鼠位置然後轉化為一串數字。但這仍然算不上真正的隨機,比如前一刻滑鼠位置如果是在螢幕左側的話,下一刻滑鼠跑到右側的可能性是很低的。因此這樣生成的隨機亂數序列仍然具有相關性的,或者是可能會偏向特定值的。也就是說,這種隨機性還是很弱。

而隨機抽取器則是通過這些隨機性較弱的來源來發掘隨機性。用 MIT 電腦科學家 Dana Moshkovitz 的話來說,隨機性是一種資源,獲取隨機性的過程就像是挖金礦一樣—先開採礦石,然後排沙篩金。

而兩位科學家的算法是對隨機抽樣器的改進。這種隨機抽取器將兩種獨立的弱隨機亂數來源組合為一個接近隨機的集合,並且只有細微偏差。然後再利用彈性函數(一種訊息組合方法)將一串數字轉化為真正的隨機位 —1 或 0。

利用彈性函數進行訊息組合可以防止偏差的出現。比方說在大選裡面,一些蓄意的投票者有可能會把結果引向想要的方向。但彈性函數可以保護誠實的投票者。因為它不是選取簡單多數,而是先把數據分成 3 組,然後選取每組中的多數,再把選出來的數分成 3 組然後再抽取每組中的多數,以此類推直到最後。這種做法使得選舉可以容忍大量盲點的存在,而在隨機亂數生成方面,這種做法可以把偏差數過濾掉。

跟以往需要接近隨機輸入的隨機抽取器相比,這種新的辦法正是通過在隨機性非常非常弱的來源當中「淘金」來挖掘真正的隨機亂數,從而實現了隨機性的實質性改進,其結果已經接近於理想情況。對於加密、複雜系統模擬等應用來說,這是一個非常好的消息。



The technical details are described in the academics’ paper “Explicit Two-Source Extractors and Resilient Functions.” The academics’ introduction of resilient functions into their new algorithm built on numerous previous works to arrive at landmark moment in theoretical computer science. Already, one other leading designer of randomness extractors, Xin Li, has built on their work to create sequences of many more random numbers.

See more at: Academics Make Theoretical Breakthrough in Random Number Generation https://wp.me/p3AjUX-uJE

沒有留言:

網誌存檔