神譯局是36氪旗下編譯團隊，關注科技、商業、職場、生活等領域，重點介紹國外的新技術、新觀點、新風向。
編者按：生活當中看似到處都是隨機。但真正的隨機比你想像的要難得多。其實，我們接觸的絕大多數都是偽隨機數。即便如此，偽隨機數的生成也是個很耗時間和內存的事情。但最近，MIT的研究人員找到了一種經典隨機數生成算法的改進辦法，令隨機數的生成效率提高了很多，確定論的計算機有望將隨機性植入到自己的建構塊裡面。Stephen Ornes對此進行了報導，原文發表在quantamagazine上，標題是：How and Why Computers Roll Loaded Dice
劃重點
計算機軟體和硬體運行的基礎是布爾邏輯，不是概率
FLDR提出了一種將隨機數集成到內置了確定性的軟體和硬體裡面的方法
大部分的隨機數生成算法都是偽隨機，是根據複雜的公式生成的
FLDR算法中時間和內存消耗上都非常高效
對於計算機來說，模擬投擲灌鉛骰子一直是一個難題。
這是一個看似很簡單的練習：讓你想出一個隨機的電話號碼。選出七位數的序列，每一位都要等可能，並且選擇一個數字不會影響到下一個數字。很有可能你選不出來。（不過我的話也不要全信：可以追溯到1950年代的研究表明，我們在數學上其實跟隨機的關係不大，雖然我們都意識不到這一點。）
不要放在心上。計算機在生成隨機性這件事情上做得也不好。本來我們也不指望它們能夠做好：計算機軟體和硬體運行的基礎是布爾邏輯，不是概率。麻省理工學院Probabilistic Computing Project（概率計算項目）的負責人Vikash Mansinghka表示：「計算文化以確定性為中心。這一點表現在幾乎每一個層面上。」
但是計算機科學家希望程序能夠處理好隨機性，因為有時候這就是問題的需要。多年以來，有些人開發出了新穎的算法，儘管這些算法本身不會生成隨機數，但卻提供了巧妙而有效的方式來利用和操縱隨機性。麻省理工學院Mansinghka小組最近就取得了一項最新成果，他們提出了一種算法，叫做「快速搖灌鉛骰子」（Fast Loaded Dice Roller ，FLDR）。這項成果將於今年八月份的在網上舉行的國際人工智慧與統計會議（Conference on Artificial Intelligence and Statistics）上進行展示。
簡而言之，FLDR利用了一個隨機序列來完美地模擬搖一顆灌鉛骰子的情形。（或者是一枚加重的硬幣，或被操縱的卡片組。紐奧良大學的數學家Peter Bierhorst說：「算法展示了怎麼把拋硬幣從完全隨機變成有偏向的。」Bierhorst並非研究的貢獻者，但是他說FLDR成功背後的前提「很吸引人」。
FLDR不會讓你在《地產大亨》遊戲裡面獲得優勢，也不會增加你去拉斯維加斯賭場擲骰子獲勝的機會。但是算法的發明者說，它提出了一種將隨機數集成到內置了確定性的軟體和硬體裡面的方法。給軟硬體引入這種不確定性可以幫助機器做出像人一樣的預測，並能更好地模擬依賴概率的現象，比如氣候或金融市場等。
隨機性是一個很棘手的概念，比乍看之下要棘手。在看不出模式的隨機數序列裡面，每個數字都有相同的出現概率。比方說，Pi本身並不是一個隨機數，但是pi的每一位數字被認為是隨機出現的（數學家稱之為「正規數」）：從0到9，每個整數出現的次數相同。
是，Google搜索「隨機數生成器」你是可以找到，但那些生成器生成的並不是純粹的隨機性。現在的處理器也好，搜尋引擎以及密碼生成器也好，它們用的都是「偽隨機」的方法。當然，這些方法對於大多數用途而言都已經足夠接近隨機了，那是根據複雜的公式生成的，但是從理論上來講，如果你知道那個公式的話，就可以預測序列。
科學家嘗試將真正的隨機性植入到機器裡面至少已有80年的歷史了。（在此之前，隨機數來自傳統的備用品，如擲骰子，從混勻的袋子裡面取出編號球，或其他的機械練習。1927年，統計學家對人口普查數據進行採樣，從而得到了一張有40000個隨機數字的表格。）
麻省理工學院的Vikash Mansinghka表示，新的FLDR算法可以幫助科學家把概率植入到確定性計算機當中。
早期的隨機數的來源是物理機器。第一臺產生隨機數的機器是英國統計學家莫裡斯·喬治·肯德爾（Maurice George Kendall）和伯納德·巴賓頓·史密斯（Bernard Babington Smith）的發明。1938年，他們對此進行了描述。機器被放進一間黑屋裡面，然後旋轉一個分成10等分的圓盤，每一份分別用0到9的數字標記。當某人用不規則的間隔敲擊按鍵時，一道霓虹燈或火花就會照亮圓盤，讓它看起來好像被定格了一樣，但只有一個數字可見。後來又發明了另一臺機器，叫做Ernie，這次則是在氖管中用了信號噪聲。從1957年開始，英國的某個彩票就是用它來選出中獎號碼的。
Bierhorst 說，最近以來，為了得到真正的隨機序列，計算機科學家必須研究自然現象，比如宇宙背景輻射或量子系統的不可預測行為才行。他說：「自然界中存在可以利用的隨機過程，這確實是不可預測的。那些忽左忽右躲閃騰挪的電子甚至事先都不知道自己要做什麼。」
但是隨機性只能帶你走那麼遠了。到1940年代後期，物理學家開始生成隨機數來擬合給定的概率分布。這樣的工具（滾灌鉛骰子的理論版）可以更準確地用於模擬現實情況，比方說交通流量或者化學反應。1976年，計算機科學家先驅Donald Knuth和Andrew Yao提出了一種算法，這種算法可以用一串隨機數生成任意加權結果數組的隨機樣本。Mansinghka實驗室的博士生Feras Saad 說：「這是有史以來最省時的算法。」
但不幸的是，Saad 說，這種算法要進行一定的折衷，那種計算機科學家都很熟悉的取捨權衡：很多跑得快的應用使用了大量內存，而使用內存較少的應用則可能需要很長的運行時間。Knuth和Yao的算法屬於第一類，所以算法是很優雅，但是實際使用要佔用大量內存。
但是去年春天時，Saad找到了一種聰明的解決方法。他意識到，當骰子的權重加起來等於2的冪次時，這一算法在時間和內存消耗上都非常高效。因此，對於一個六面骰子，假設滾出數字1到6的機率分別賦予1、2、3、4、5和1的加權。這意味著比方說滾出1的概率為1/16，滾出2的概率為2/16。由於權重的總和是2的冪次（16是2的4次方），所以這套系統的算法在時間和內存消耗上都很高效。
麻省理工學院博士生Feras Saad 幫助設計了一種新的算法，這種算法可以高效、準確地模擬搖灌鉛骰子。
但是，假設權重取值改為1、2、3、2、4、2，總和為14的情況。由於14不是2的冪次方，所以Knuth-Yao算法需要佔用更多的內存。Saad 意識到他可以增加一個權重，從而使得它們的總和總是2的冪次。在這種情況下，他只需給骰子增加一面——讓假設的這一面權重為2，這樣權重加起來就是16了。如果算法選到了原先的6面之一，就記錄下相應的數值。如果選到了莫須有的那一面，就丟棄掉，然後再次運行算法。
這就是FLDR算法效率的關鍵，使得它成為了仿真的一個強大的工具：與原先一般需要佔用大量內存的算法相比，多餘的滾骰子所需佔用的額外內存很小。
FLDR提高了Knuth-Yao算法的效率，並為改善一系列應用指明了方向。氣候變化模擬，作物產量預測，粒子行為模擬，金融市場模型，甚至核武器地下爆炸的探測都取決於按照加權概率分布的隨機數。隨機數是用來保護通過網際網路發送的數據的加密機制的支柱。
Mansinghka說，FLDR還可以幫助研究人員找到將概率整合到計算機處理器裡面的方法，這是他在麻省理工學院實驗室工作的重點。有了這一算法，軟體庫和新的硬體體系結構的設計就可以生成隨機數並以有效的方式去利用這些隨機數。這跟我們過去使用的確定性布爾機器將大相逕庭。
他說：「 我們很可能即將把隨機性集成到軟體和硬體的構建塊當中。」
譯者：boxi。