樹洞 Tree Hole 2.0

Reading, Caffeine, Alcohol, Peanuts, Cynicism…

數學和摺紙 — December 12, 2017

數學和摺紙

今晨在找 Ted 演講影片的時候,意外發現這個,完全符合領導的要求,而且演講者口齒清晰又幽默,堪稱上品。

 

Advertisements
數學歸納法其實是演繹法 — October 24, 2017

數學歸納法其實是演繹法

三年前在多看平臺上看電子書费马大定理:一个困惑了世间智者358年的谜,書中有一段話是「 Wiles 採用稱為歸納法的一般方法作為他證明的基礎」,我當下就在書裡加上註解,反應給出版社,數學歸納法是演繹,不是歸納。後來整句話被修掉,完全不提 Wiles 的方式是基於歸納還是演繹。現在在多看平臺看這本電子書的讀者,還可以看到我加的註,但是本文已經和截圖的內容不同了。

-

為什麼特別注意到數學歸納法,因為 Udi Manber 有本演算法課本 Introduction to Algorithms: Creative Approach,花了很長的篇幅講數學歸納法。很久以前準備演算法考試的時候,從圖書館借了這本書參考。看到計算機科學家,以不同於數學家的敘述方式講數學歸納法,覺得很有意思,後來那本書只有那一章是真正認真讀完的。

在準備考試期間,順便查了包括維基百科在內的許多網路資料,寫了讀書筆記《Creative Approach 有什麼不同 (2) – 談談數學歸納法

所謂的歸納推理,是基於對特定目標觀察的結果,把「性質」或「關係」類推至類型,或者是基於對反覆現象的觀察,所推理出來的規律或公式。歸納推理的結論只是有較大的機率為真,但不代表一定為真。

而演繹推理則是從已知事實為前提,必然得出的結論,如果前提為真,則結論必然為真。數學歸納法是基於一組已知的前提,推演出一個必然為真的結論,所以這個證明方法的精神是 deductive reasosing ,不是 inductive reasoning。

維基百科關於數學歸納法的中文頁面,講的更是斬釘截鐵,但是這一刀似乎切的太猛:

数学归纳法并非不严谨的归纳推理法,它属于完全严谨的演绎推理法。事實上,所有數學證明都是演繹法。

-

今早在圖書館找資料,看到曹亮吉教授寫的推廣書籍《阿草的葫蘆 — 文化活動中的數學 》,書裡講到數學家不是只在乎演繹,同樣也會使用歸納思考方式;同樣地,其他自然科學領域也不是只歸納不演繹。但是他同樣直接了當的說:數學歸納法,是個如假包換演繹法

專業數學家鐵口直斷,period。

-

不知道給「假設 n 成立,證 n + 1 也成立」這種證明方式取名 mathematical induction 的是那位先賢,如假包換的標題黨啊!

為什麼是 37% — October 16, 2017

為什麼是 37%

Hannah Fry 的《愛情數學》第七章寫到如何應用「最優停止理論(Optimal Stopping)」,決定什麼該「定下來」,確定結婚的對象。如果你一生中打算談 n 次戀愛,或者你打算從25歲到35歲之間盡可能認識更多的人,到了35歲再決定你的他(她),怎麼做可以讓你找到最佳拍檔的機率最高。。

-

這個題目有許多不同版本,比如說 Algorithms to Live By: The Computer Science of Human Decisions 就問如果你搬到一個新城市,需要找地方住,找到你最合意的公寓的找房策略是什麼?或者你想找一個新祕書,你要面試多少人才找到合適的祕書呢(這問題有個名字叫「祕書問題」)。

If you want the best odds of getting the best apartment, spend 37% of your apartment hunt (eleven days, if you’ve given yourself a month for the search) noncommittally exploring options. Leave the checkbook at home; you’re just calibrating. But after that point, be prepared to immediately commit—deposit and all—to the very first place you see that beats whatever you’ve already seen. This is not merely an intuitively satisfying compromise between looking and leaping. It is the provably optimal solution.

-

那麼這個問題的最佳策略是什麼呢?從數學觀點,確實有最佳策略,就是大名鼎鼎的37%法則。Hannah Fry 告訴我們,如果你一生要談10次戀愛,找到最佳對象的機率發生在拒絕4個人之後;如果你有無數個伴侶,拒絕前37%的人,成功率最高。如果以時間軸來考量,在你遊戲花叢時間的前37%,千萬不要定下來,但是過了 37% 的時間,遇到第一個比前 37% 時間遇到的「可能對象」都好的先生或女士,就是他(她)啦。

37 這個數字,怎麼算出來的?Hannah Fry 在書裡講的很簡略,告訴我們最優停止理論給了我們一個極為簡潔的公式,用這個公式算出來的數字就是 37%。書末的參考文獻指向一篇1997年出版的論文《Searching for the Next Best Mate1》,這篇論文的摘要(abstract)也只是直接說出 37 這個數字,沒有解釋來由。這篇論文的訂價是 24.95 歐元(Oops),直接放棄購買或下載的打算。

…In this paper, we analyze the third approach of mate choice as applicant screening and show through simulation analyses that a traditional optimal solution to this problem-the 37% rude-can be beaten along several dimensions by a class of simple “satisficing” algorithms we call the Take the Next Best mate choice rules. Thus, human mate search behavior should not necessarily be compared to the lofty optimal ideal, but instead may be more usefully studied through the development and analysis of possible “fast and frugal” mental mechanisms.

透過谷歌,在 plus.math.org 找到兩篇文章《Strategic dating: The 37% rule》和《Kissing the frog: A mathematician’s guide to mating》解釋答案為什麼是 37%,看完推導,只能說一個字:維基百科的解釋看起來不一樣,其實精神和 plus.math.org 提出來的解法是一致的。翻譯成數學語言,就是訂出你的「停止」策略,然後計算成功的機率,若你的約會對象有 N 個選擇,當你審視過 r 個約會對象後,找到你的最佳拍檔的機率可以寫成下面的算式:

-

簡而言之,這公式其實就是求 1/x 的積分,當 N 接近無窮大,最後我們得到

-

P 的最佳值在 x=1/e 的時候出現,大約等於 0.3679


  1. Todd P.M. (1997) Searching for the Next Best Mate. In: Conte R., Hegselmann R., Terna P. (eds) Simulating Social Phenomena. Lecture Notes in Economics and Mathematical Systems, vol 456. Springer, Berlin, Heidelberg 
德瑞克方程式與費米方法 — October 11, 2017

德瑞克方程式與費米方法

1961 年,天文學家 Frank Drake,提出一個問題,銀河系裡有多少願意和我們聯繫的文明?他不僅提出問題,還提供了一個答案,建議大家使用一個估算方式。我們稱這個計算方法叫德瑞克方程式(Drake Equation),方程式的計算很簡單,沒有用到高深的數學技巧,就是簡單的乘法而已:

-

本公式的每個參數解釋是這樣的:

  • N = 銀河系統中可以通訊的文明數目
  • R* = 每年銀河系產生的星體數目(平均)
  • fp = 恆星系統擁有行星環繞的比例
  • ne = 行星系統裡有多少「宜居」的行星
  • fl = 「宜居」行星發展出生命的比例
  • fi = 擁有生命的星球,能發展出智慧文明的比例
  • fc = 擁有智慧文明,且發展出對外通訊技術的比例
  • L = 該對外通訊科技延續的時間(the length of time over which such civilizations release detectable signals)

把算式右邊的數值乘起來,就是銀河系中可以聯絡的文明數目的估計值。當時德瑞克估計可能願意和我們聯絡的文明數約有 10 個,時至今日,最新的估計值已經降低到 2.3 了。

上週提到 Peter Backus 在 2010 年用德瑞克方程式的精神,估算他的「可能伴侶」的數字,Hannah Fry 在她的書 Mathematics of Love 中說 Peter Backus 估算他追女機率的計算方式就是費米方法,為什麼 Hannah Fry 這麼說?費米方法是什麼?

關於 Enrico Fermi1 的傳說很多,費米方法是他衆多傳說之一,傳說是這樣的,據說他在芝加哥大學的課堂上,問他的學生「芝加哥市裡有多少鋼琴調音師?」,當他的學生們抓耳撓腮之際,他對學生說明了估算的訣竅,很快學生就掌握了這個方法的精髓。

在美國亞馬遜網站評價非常高的 Superforecasting 這本書用淺顯易懂的文字解釋費米方法的精神,這裡引用大陸中信出版社出的簡體中文版翻譯本《超預測》的文字:

-

為了計算芝加哥鋼琴調音師的人數,我們必須知道什麼呢?唔,鋼琴調音師的數量取決於給鋼琴調音的工作量和僱用一位調音師可以做的工作。因此,如果我知道以下4個數據,這個問題就迎刃而解:

(1)芝加哥的鋼琴數量;

(2)每年給鋼琴調音的次數;

(3)給鋼琴調音需要的時間;

(4)鋼琴調音師每年平均工作時間。

有了前三個數據,我可以算出在芝加哥鋼琴調音的總工作量。接著,用這個數值除以最後一個數據。就這樣,我可以非常自信地說出芝加哥有多少位鋼琴調音師。

我們很容易就看出,這個邏輯和上面德瑞克方程式的計算方式完全一樣,德瑞克方式就是費米方法論的一個具體範例。回到 Peter Backus 的伴侶數目問題,彼得先生在小論文《為什麼我沒有女朋友》裡的計算方式是這樣的,

  1. 住在我附近的女性有多少?(倫敦:400萬)
  2. 多少人有可能年齡上適合?(20%:80萬)
  3. 多少人有可能是單身?(50%:40萬)
  4. 多少人有可能擁有大學文憑?(26%:104,000)
  5. 多少人有可能有魅力?(5%:5,200)
  6. 多少人有可能覺得我有魅力?(5%:260)
  7. 多少人有可能和我合得來?(10%:26)

像剝洋蔥一樣,一層層剝下來,他得到 26 這個答案。在英國境內找到這 26 個可能對象,難不難?比發現外星文明還難嗎?

答案在每個人心中,至於彼得自己的答案,從他 2013 年就結婚的事實,我們可以「感受」到彼得的答案是什麼!


  1. Enrico Fermi 是1938年諾貝爾物理獎得主 
從 Missing Bullets Holes 看出「本來就應該是這樣」啊 —

從 Missing Bullets Holes 看出「本來就應該是這樣」啊

奉領導之命,要找些數學和統計的「有趣」故事,做為教案設計的素材,也可供課堂上調節氣氛之用。

比 Peter Backus君子好逑故事更早浮現腦海的,是 Jordan Ellenberg 寫的 How Not To Be Wrong1 書中導言章裡提到的 Abraham Wald 的故事。出版這本書的企鵝出版社在他們的企業部落格,刊出書中故事的節錄,故事名稱叫做 Abraham Wald and the Missing Bullet Holes 亞伯拉罕瓦爾德與失蹤的彈孔

-

簡而言之,這又是一個典型的在二戰期間從德國逃出的猶太人用他們的智慧幫助同盟國在戰場打擊德國的故事,Jordan Ellenberg 把這個發生在美國軍方組織的祕密計畫 Statistical Research Group (SRG)2 的故事講的頗精彩,簡潔漂亮,直面問題核心的數學洞見固然令人讚歎,戰爭期間國家機器各種七彎八拐的算計、懷疑則點到為止,讓你自己慢慢回味。

Abraham Wald 身為一個剛從戰時敵對國逃出的精英數學家,雖然身份敏感疑慮未除,但是為了勝利,美國軍方怎麼能放棄這樣一個智慧瑰寶呢?於是一邊用他,一邊防他,所以有了這麼一個笑話:據說他寫報告的時候,要有專人在旁伺候,每寫一張紙,在旁伺候的祕書就要把剛寫好的報告抽走,因為他的身份敏感,不能閱讀這麼「敏感」的機密檔案材料(即使這個機密檔案是他自己撰寫的)。

Still an “enemy alien,” he was not technically allowed to see the classified reports he was producing; the joke around SRG was that the secretaries were required to pull each sheet of notepaper out of his hands as soon as he was finished writing on it.

有一天,軍方要求 SRG 的專家們研究怎樣最有效率的在飛機上配置「裝甲(armour)」,裝甲越多越能保護飛機和飛行員的安全,但是裝甲越多飛機越重,不利於飛行,更耗油,也使用了更多的鋼材資源。

於是學者調查從戰場回到基地的飛機上的彈孔分佈,得到下面的數字,他們計算出飛機各部位,每平方英尺的彈孔有多少,顯然引擎部位的彈孔分佈比機身其他部位少很多。

軍官們認為(期望),把裝甲集中在受攻擊最多的部位,這樣做可以減少裝甲總量,對飛機的防護也不會減少。但是被認為是 SRG 小組中數一數二聰明的 Abraham Wald 告訴軍方,需要增加裝甲的地方不是留有彈孔的地方,而是沒有彈孔的地方。答案是引擎部位。

-

Wald 假設,飛機各部位受到損壞的概率是均等的,那為什麼引擎罩上的彈孔比其餘部位少呢?答案是,那些我們沒看到的彈孔,都在未能返航的飛機上

Jordan Ellenberg 把佚失彈孔問題的問題,稱作倖存者偏差(survivorship bias),我們知道彈孔與飛行員的生存機率相關,Wald 把問題抽象化,首先要有一個合理的假設(飛機各部位收到攻擊的機率是均等),然後穿過問題表象看到問題實質,看到解決問題的方向。

To a mathematician, the structure underlying the bullet hole problem is a phenomenon called survivorship bias. It arises again and again, in all kinds of contexts. And once you’re familiar with it, as Wald was, you’re primed to notice it wherever it’s hiding.

這個故事,經過許多人的傳播,對於許多人不再陌生,現在聽來不會再像 1944 年那時首次聽報告的軍方長官們那麼震撼,甚至會覺得「本來就是這樣」啊。其實,「本來就應該是這樣」的思維是別人幫我們掃清了遮眼的迷霧才這麼清楚的。培養掃清迷霧的思維,就是學數學的目的,也是數學的魅力所在啊。


  1. 這本書有繁體中文翻譯版,書名叫做《數學教你不犯錯》,簡體中文版的書名比較勁爆,叫做《魔鬼數學》 
  2. SRG 是美國軍方 National Defense Research Committee 為了利用數學界的研究力量,提升國防力量的祕密計畫,有點類似研發原子彈的曼哈頓計畫。SRG 的辦公室設立在哥倫比亞大學。