AM-GM 不等式的幾個證明（一）
AM-GM 不等式的幾個證明（二）
我們看過 AM-GM 不等式在 n=2 的情況時的一個「無言證明」，和一般情況的一個「反向歸納法」證明。這裡我們看一個使用一般數學歸納法的證明。
設
而
因此 AM-GM 不等式對所有正整數 n 皆成立。使用數學歸納法證明 AM-GM 不等式的技巧還有很多，甚至有些證明可以不必使用數學歸納法，我們下回再看。
2009年9月27日 星期日
AM-GM 不等式的幾個證明（三）
在早前的文章中：
AM-GM 不等式的幾個證明（一）
AM-GM 不等式的幾個證明（二）
我們看過 AM-GM 不等式在 n=2 的情況時的一個「無言證明」，和一般情況的一個「反向歸納法」證明。這裡我們看一個使用一般數學歸納法的證明。
設
、
，其中所有 xi 皆是正數。正如上回所說，我們有 A1 = G1 和 A2 ≧ G2。假設 Ak ≧ Gk。以下證明 Ak+1 ≧ Gk+1：我們有
而
因此 AM-GM 不等式對所有正整數 n 皆成立。使用數學歸納法證明 AM-GM 不等式的技巧還有很多，甚至有些證明可以不必使用數學歸納法，我們下回再看。
AM-GM 不等式的幾個證明（一）
AM-GM 不等式的幾個證明（二）
我們看過 AM-GM 不等式在 n=2 的情況時的一個「無言證明」，和一般情況的一個「反向歸納法」證明。這裡我們看一個使用一般數學歸納法的證明。
設
而
因此 AM-GM 不等式對所有正整數 n 皆成立。使用數學歸納法證明 AM-GM 不等式的技巧還有很多，甚至有些證明可以不必使用數學歸納法，我們下回再看。
2009年9月22日 星期二
洗幾次牌先「夠」？
一幅啤牌52隻，發展出很多趣的遊戲出來，包括橋牌、「鋤大D」、廿一點等等。每盤遊戲結束，指定動作就是洗牌。相信你一定見到有人隨便「cut兩cut」就算，但亦有人洗一次牌洗成分鐘，有點掃興的味道。
究竟，洗牌要洗幾多次先「夠」？
要回答這條問題前，首先要定義甚麼是「夠」。從概率學上，「夠」可以定義為每一個可能性出現的機會都（大約）相等。1992年Bayer和Diaconis研究了以下一種洗牌方法（以下一段不只針對啤牌；一幅牌可以有n隻）：
首先一幅牌排成一疊，然後每隻牌順序抽出，再擲骰仔決定放左面還是右面：若是單數放左面，若是雙數放右面。然後將左面的牌疊在右面的牌的上方。
這種洗牌方法叫inverse Gilbert-Shannon-Reeds shuffle (inverse GSR shuffle)。Bayer和Diaconis証明了若進行大約
次inverse GSR shuffle，副牌就大約「洗勻」了。換言之，對啤牌來說，需要洗牌大約 8.55 次。
當然，現實中用inverse GSR shuffle未免太慢了（擲52次骰仔，每次1秒，再加其餘動作，最少也要1分鐘吧）。但大家想想，若inverse GSR shuffle如兩段前所述，那麼non-inverse GSR shuffle會是怎樣的？大家又是否覺得似曾相識呢？
-----
Below is for more advanced math students. Only people who have some background on Markov Chain theory should continue reading:
For those who know about Markov Chain theory, you may easily see that it is a Markov process. As every element in the symmetric group has an inverse, it is easy to observe that the eigenvector with eigenvalue 1 is indeed the "uniform distribution vector".
The period of the corresponding stochastic matrix must be 1, since there is non-zero probability that the inverse GSR shuffle remains the deck unchanged. Hence by Perron-Frobenius theorem, all other eigenvectors must be with eigenvalue of modulus strictly less than 1. So after shuffling sufficiently many times, no matter how the intial distribution is, it must converge to the unifrom distribution.
In other words, you may say converging to uniform distribution is an immediate result of Perron-Frobenius theorem. Bayer and Diaconis were analyzing how fast the convergence is.
究竟，洗牌要洗幾多次先「夠」？
要回答這條問題前，首先要定義甚麼是「夠」。從概率學上，「夠」可以定義為每一個可能性出現的機會都（大約）相等。1992年Bayer和Diaconis研究了以下一種洗牌方法（以下一段不只針對啤牌；一幅牌可以有n隻）：
首先一幅牌排成一疊，然後每隻牌順序抽出，再擲骰仔決定放左面還是右面：若是單數放左面，若是雙數放右面。然後將左面的牌疊在右面的牌的上方。
這種洗牌方法叫inverse Gilbert-Shannon-Reeds shuffle (inverse GSR shuffle)。Bayer和Diaconis証明了若進行大約
當然，現實中用inverse GSR shuffle未免太慢了（擲52次骰仔，每次1秒，再加其餘動作，最少也要1分鐘吧）。但大家想想，若inverse GSR shuffle如兩段前所述，那麼non-inverse GSR shuffle會是怎樣的？大家又是否覺得似曾相識呢？
-----
Below is for more advanced math students. Only people who have some background on Markov Chain theory should continue reading:
For those who know about Markov Chain theory, you may easily see that it is a Markov process. As every element in the symmetric group has an inverse, it is easy to observe that the eigenvector with eigenvalue 1 is indeed the "uniform distribution vector".
The period of the corresponding stochastic matrix must be 1, since there is non-zero probability that the inverse GSR shuffle remains the deck unchanged. Hence by Perron-Frobenius theorem, all other eigenvectors must be with eigenvalue of modulus strictly less than 1. So after shuffling sufficiently many times, no matter how the intial distribution is, it must converge to the unifrom distribution.
In other words, you may say converging to uniform distribution is an immediate result of Perron-Frobenius theorem. Bayer and Diaconis were analyzing how fast the convergence is.
2009年9月17日 星期四
巧合？造馬？
最近，保加利亞的六合彩（1 至 42 號，每期攪珠抽出六個號碼）連續兩期開出相同的號碼（例如可以參考這篇報導），惹來造馬疑雲。
報導指出，數學家估計兩期相同中獎號碼的機會率是 420 萬分之 1，那是不正確的，因為 C(42,6) = 5245786，因此機會率應是約 520 萬分之 1 才對。（每星期開彩兩次的話，平均每 50000 年這才會發生一次。但如果我們考慮不同國家的彩票的話，出現這情況的頻率會大大提高，例如如果有 1000 個同樣的彩票的話，那麼平均每 50 年便會有一次這樣的事件了。）
有人認為事件乃造馬，其中一個理據是第一次開那六個號碼時沒有人中獎，第二次時卻有 18 人中。這個理據顯然沒有說服力，因為總可能有些人投注時喜歡「照抄」上期的六個號碼，所以有多人中獎並不出奇。（同樣，如果開出「1、2、3、4、5、6」的話，中獎的人必定很多，所以投注這些「特別組合」是不智的。）
那到底事件是巧合還是造馬呢？這個還得等待當地政府的特別調查結果，不過也可以客觀分析一下：整個攪珠過程是電視直播的，現場亦有獨立委員監察，要造馬成功的話，要買通所有監察委員，再要騙過電視觀眾，難度並不低。此外，如果事件真的是造馬的話，那麼造馬的人也未免太傻了：竟然選擇重再之前一期的號碼，不但令事件惹來世界注目，而且正如之前所說，這樣的號碼組合肯定會令中獎人數激增，從而分薄派彩。如果有能力造馬的話，為何不選擇六個平平無奇的號碼，那不但神不知鬼不覺，而且派彩也更加豐厚。
當然，巧合和造馬之間也有一些其他可能性的，例如會否是攪珠機的構造導致某些號碼特別容易被攪出？這個還是留待統計學家、機械學家、工程學家、……用他們的方法驗證吧。
報導指出，數學家估計兩期相同中獎號碼的機會率是 420 萬分之 1，那是不正確的，因為 C(42,6) = 5245786，因此機會率應是約 520 萬分之 1 才對。（每星期開彩兩次的話，平均每 50000 年這才會發生一次。但如果我們考慮不同國家的彩票的話，出現這情況的頻率會大大提高，例如如果有 1000 個同樣的彩票的話，那麼平均每 50 年便會有一次這樣的事件了。）
有人認為事件乃造馬，其中一個理據是第一次開那六個號碼時沒有人中獎，第二次時卻有 18 人中。這個理據顯然沒有說服力，因為總可能有些人投注時喜歡「照抄」上期的六個號碼，所以有多人中獎並不出奇。（同樣，如果開出「1、2、3、4、5、6」的話，中獎的人必定很多，所以投注這些「特別組合」是不智的。）
那到底事件是巧合還是造馬呢？這個還得等待當地政府的特別調查結果，不過也可以客觀分析一下：整個攪珠過程是電視直播的，現場亦有獨立委員監察，要造馬成功的話，要買通所有監察委員，再要騙過電視觀眾，難度並不低。此外，如果事件真的是造馬的話，那麼造馬的人也未免太傻了：竟然選擇重再之前一期的號碼，不但令事件惹來世界注目，而且正如之前所說，這樣的號碼組合肯定會令中獎人數激增，從而分薄派彩。如果有能力造馬的話，為何不選擇六個平平無奇的號碼，那不但神不知鬼不覺，而且派彩也更加豐厚。
當然，巧合和造馬之間也有一些其他可能性的，例如會否是攪珠機的構造導致某些號碼特別容易被攪出？這個還是留待統計學家、機械學家、工程學家、……用他們的方法驗證吧。
2009年9月16日 星期三
拍賣方法的藝術
「潛水」了兩個月，事關七月、八月初都在科大寫paper，忙到不得了，而八月中下旬就要準備出國和參加一連串的farewell。對了，我現在身處New York，正在New York University的Courant Institute讀PhD in Computer Science。
雖然讀的博士銜頭表面上轉了科，但做的事還是跟數學脫不了勾；這也証明了在科學的學術界上數學幾乎是無處不在的。最近在看一本上，講algorithmic game theory。我見到一個結果很漂亮的，想在這裏和大家分享一下。
有以下這個情況：有一幅名畫要拍賣，而有n個買家。設買家Bi心中看這幅畫的價值是pi。若買家最後買不到畫，他最終的「滿足度」為0；若他以價格p買了這幅畫，他的「滿足度」為pi-p。而買家們的目標都是令滿足度盡量大。所以，買家Bi是絕不會以高於pi的價錢買畫的，因為他不買的話滿足度為0，但他以高於pi的價錢買畫，滿足度就變了負數。拍賣以「投暗標」方式進行，即每名買家只可向拍賣行提一次價，而這個價是保密的——其他買家是不知道的。
決定名畫誰屬的第一種方法就是大家所想的：價高者得。這個方法叫first price auction。假設買家們都不知道其他買家心中看名畫的價值，那麼他們應如何出價呢？他們就要估其他畫家看這幅畫的價值，對不對？若看這幅畫價值最高的幾個買家都錯誤地低估其他買家的叫價，名畫賣出的價錢恐怕就要大大降低。
有沒有其他方法令買家投標價就是他們各自的pi呢？有！這個方法叫second price auction。方法是：各買家投暗標後，投標價最高者以投標第二高價購得名畫。即是說，若四名買家投標價分別是14M、12M、8M和6M，第一名買家將以12M價格購得名畫。
這時，大家要仔細想一想。買家的確是會以各自的pi投標的；因為無論其他人投標價如何，若他們以低於pi的價格投標，都不可能會有better benefit。以上一段的例子來說，第一名買家不論以14M或13M投標，他最後的滿足度都是14M-12M = 2M；但若他以11M投標，他們滿足度就是0。以低於pi投標只會令滿足度有減少的風險。
現在回到first price auction。假設買家們還是不知道其他買家心中對名畫的價格，但現時卻有多一點的資料：買家心中價格滿足一個probability distribution。那麼，買家們應該怎樣投標呢？我們可以見到一個很漂亮與second price auction呼應的答案：假設自己心中價格是最高，然後以second highest bidding的預期值（expected value）投標。舉例說，若那個probability distribution是說買家心中價格在6M至18M之間平均分佈，那麼心中價格是14M的買家就應以(6+14)M/2 = 10M的價格投標。
雖然讀的博士銜頭表面上轉了科，但做的事還是跟數學脫不了勾；這也証明了在科學的學術界上數學幾乎是無處不在的。最近在看一本上，講algorithmic game theory。我見到一個結果很漂亮的，想在這裏和大家分享一下。
有以下這個情況：有一幅名畫要拍賣，而有n個買家。設買家Bi心中看這幅畫的價值是pi。若買家最後買不到畫，他最終的「滿足度」為0；若他以價格p買了這幅畫，他的「滿足度」為pi-p。而買家們的目標都是令滿足度盡量大。所以，買家Bi是絕不會以高於pi的價錢買畫的，因為他不買的話滿足度為0，但他以高於pi的價錢買畫，滿足度就變了負數。拍賣以「投暗標」方式進行，即每名買家只可向拍賣行提一次價，而這個價是保密的——其他買家是不知道的。
決定名畫誰屬的第一種方法就是大家所想的：價高者得。這個方法叫first price auction。假設買家們都不知道其他買家心中看名畫的價值，那麼他們應如何出價呢？他們就要估其他畫家看這幅畫的價值，對不對？若看這幅畫價值最高的幾個買家都錯誤地低估其他買家的叫價，名畫賣出的價錢恐怕就要大大降低。
有沒有其他方法令買家投標價就是他們各自的pi呢？有！這個方法叫second price auction。方法是：各買家投暗標後，投標價最高者以投標第二高價購得名畫。即是說，若四名買家投標價分別是14M、12M、8M和6M，第一名買家將以12M價格購得名畫。
這時，大家要仔細想一想。買家的確是會以各自的pi投標的；因為無論其他人投標價如何，若他們以低於pi的價格投標，都不可能會有better benefit。以上一段的例子來說，第一名買家不論以14M或13M投標，他最後的滿足度都是14M-12M = 2M；但若他以11M投標，他們滿足度就是0。以低於pi投標只會令滿足度有減少的風險。
現在回到first price auction。假設買家們還是不知道其他買家心中對名畫的價格，但現時卻有多一點的資料：買家心中價格滿足一個probability distribution。那麼，買家們應該怎樣投標呢？我們可以見到一個很漂亮與second price auction呼應的答案：假設自己心中價格是最高，然後以second highest bidding的預期值（expected value）投標。舉例說，若那個probability distribution是說買家心中價格在6M至18M之間平均分佈，那麼心中價格是14M的買家就應以(6+14)M/2 = 10M的價格投標。
2009年9月12日 星期六
等巴士之謎
假設某路線的巴士每 20 分鐘一班。如果乘客到達車站的時間是隨機的，而巴士又永遠準時到站的話，那麼乘客的平均候車時間是 10 分鐘（當然，最短的候車時間是 0 分鐘，最長則是 20 分鐘）。如果班次不準確但車子的數目不變的話（例如有些班次早到數分鐘，有些遲到數分鐘），那麼對乘客的平均候車時間將有何影響？
看下去之前，不妨停下來先想想。
由於車子的數目不變，那麼有些班次早到而有些遲到的話，表面上平均候車時間似乎不變（車子遲來的話，有些人久等了，但有些卻因而趕上該車子，而車子早來的情況也類似），其實不然。
考慮一下這個頗為極端的情況：單數的班次（第 1 班、第 3 班、……）總是遲到 10 分鐘，而雙數的班次則總是早到 10 分鐘。那麼，20 分鐘一班的巴士會變成每 40 分鐘一次過來兩班，但對乘客來說這跟每 40 分鐘一班沒有分別 -- 平均候車時間變成了 20 分鐘！
再考慮另一個情況：單數的班次總是遲到 3 分鐘，而雙數的班次則總是早到 3 分鐘。那麼從某班單數的班次開出到下一個單數班次到站的 40 分鐘可視為一個循環，如果我們假設這 40 分鐘期間每分鐘有一名乘客到達車站的話，那麼他們的候車時間分別為 14、13、…、1、0、25、24、…、1、0 分鐘，不難發現平均候車時間超過 10 分鐘（可以不經計算而看出此事嗎？）。
一般來說，如果巴士並非全部準時到達的話，那麼平均候車時間便會超過 10 分鐘。因為時間是連續的，要嚴謹證明這事有點麻煩，故這裡從略。不過懂得積分（integration）的讀者可以一試，事實上以上結果是排序不等式（rearrangement inequality）的一個「連續版（continuous version）」呢。
看下去之前，不妨停下來先想想。
由於車子的數目不變，那麼有些班次早到而有些遲到的話，表面上平均候車時間似乎不變（車子遲來的話，有些人久等了，但有些卻因而趕上該車子，而車子早來的情況也類似），其實不然。
考慮一下這個頗為極端的情況：單數的班次（第 1 班、第 3 班、……）總是遲到 10 分鐘，而雙數的班次則總是早到 10 分鐘。那麼，20 分鐘一班的巴士會變成每 40 分鐘一次過來兩班，但對乘客來說這跟每 40 分鐘一班沒有分別 -- 平均候車時間變成了 20 分鐘！
再考慮另一個情況：單數的班次總是遲到 3 分鐘，而雙數的班次則總是早到 3 分鐘。那麼從某班單數的班次開出到下一個單數班次到站的 40 分鐘可視為一個循環，如果我們假設這 40 分鐘期間每分鐘有一名乘客到達車站的話，那麼他們的候車時間分別為 14、13、…、1、0、25、24、…、1、0 分鐘，不難發現平均候車時間超過 10 分鐘（可以不經計算而看出此事嗎？）。
一般來說，如果巴士並非全部準時到達的話，那麼平均候車時間便會超過 10 分鐘。因為時間是連續的，要嚴謹證明這事有點麻煩，故這裡從略。不過懂得積分（integration）的讀者可以一試，事實上以上結果是排序不等式（rearrangement inequality）的一個「連續版（continuous version）」呢。
2009年9月6日 星期日
AM-GM 不等式的幾個證明（二）
上回給了 AM-GM 不等式的一個「無言證明」，但那只適用於 n=2 的情況。這次我們看一個完整的證明，方法是用「反向歸納法（backward induction）」。在 AM-GM 不等式的眾多證明中，這可說是最常見的一個。或者換個角度說會較為適合：在反向歸納法的眾多例子中，AM-GM 不等式是最常見的一個。
這裡先概述一下證明的方法。當 n=1 時，AM-GM 不等式顯然成立。當 n=2 時，我們也很容易證明 AM-GM 不等式成立，這是因為
這裡先概述一下證明的方法。當 n=1 時，AM-GM 不等式顯然成立。當 n=2 時，我們也很容易證明 AM-GM 不等式成立，這是因為
而後者顯然正確。利用以上已證明的 n=2 結果（即兩個正數的算術平均大於或等於它們的幾何平均），我們有
從而 AM-GM 不等式對於 n=4 也成立（注意這裡兩次用到 n=2 時的結果）。由於以上不等式對任意四個正數 x1、x2、x3、x4 成立，故特別地當 時也成立，從而有
這樣我們便從 n=4 的情況證明了 n=3 的情況！重覆以上的步驟，我們可以從 n=4 的情況推導出 n=8 的情況，再反向推導出 n=7、n=6 和 n=5 的情況，如此類推。這就是反向歸納法背後的理念。有興趣細讀詳情的話，可以參閱數學資料庫這份《數學歸納法》筆記中的 Theorem 3.5 和 Example 3.5。
證明 AM-GM 不等式還有很多其他方法，下回繼續。
訂閱：
文章 (Atom)