有些名言充滿數學哲理，本文選談兩個和概率論有關的名言。
上得山多終遇虎
這句話原指走到山上要面對老虎帶來的危險，即使一次沒有遇到，但如果不斷上山的話，總會有遇到老虎的一天，通常用作比喻做壞事的人終會受到制裁。這話背後有甚麼數學哲理呢？假設每次上山「遇虎」的概率為 p (>0)，且上山 n 次後遇虎最少一次的概率是 Pn，則 Pn = 1 - (1-p)n，故此不難發現當 n 趨向無限大時，Pn 的值趨向 1，應驗了「終遇虎」的結論！
一鳥在手勝過二鳥在林
這句話相信是出自英語的「One bird in hand is worth two in the bush」，不論中英文版本都有一些「變種」，主要是把「二」變成其他數字，不過意思也都相同，就是說「實在」勝過「浮雲」，有時則用以比喻要珍惜現在，別奢求無法得到的東西。
這話背後又有甚麼數學哲理？一鳥在手是否勝過二鳥在林，表面上視乎「在林」的鳥可以「到手」的概率 p，也就是視乎「二鳥在林」的期望值（expected value）。如果 p>0.5 的話，則「二鳥在林」的期望值是比「一鳥」高的。那麼為甚麼有一鳥在手「勝過」二鳥在林的說法呢？
很多時候，我們下決定時都不只看期望值。舉例說，假設你的身家有 n 元，現讓你從一副紙牌中抽兩張，如果抽到黑桃 A 和紅心 A 的話獎你 100000 n 元，否則輸掉 n 元，遊戲只可玩一次。這個遊戲的期望值是個很大的正數（當然是相對 n 而言），你願意參加嗎？ 除了期望值外，離差（dispersion）也會影響我們的決定，例如標準差（standard variation）是一個常見的離差指標。一般來說，我們希望離差越小越好，於是以上遊戲中正數的期望值便不足以彌補很大的離差。
這就解釋了一鳥在手為何可以勝過二鳥在林了 -- 因為「一鳥在手」時標準差是零，而「二鳥在林」時標準差是正數呢！
2009年6月22日 星期一
2009年6月20日 星期六
Convolution Technique in Generating Function (2)
It is quite unexpected that the second part of this passage is posted three months later. Anyway, let me post the link to the first part of this passage. Here, I am going to discuss another counting problem which we can use convolution technique to solve.
Let me recall the key idea again. Convolution of generating functions can be useful when we try to count a class of combinatorial objects, while these objects can be constructed by joining two smaller objects of size k and M-k.
Here comes the question, which looks really unfavourite when you first see it. An n by n square matrix M satisfies the following conditions: (1) every entry is a non-negative integer; (2) the sum of entries in each column is n-1; (3) for any two entries which are both positive, denote the coordinates by
and 
, then 
.
Below shows a few 4 by 4 matrices which satisfy the three conditions:
, 
, 
The first two conditions can be easily visualized. The third condition can be visualized as follows: for any non-zero entry, its north-west and south-east direction entries must be all zero.
I will generalize by counting the number of p (number of columns) by q (number of rows) matrices satisfying the three conditions (note: the sum of each column is fixed to be n-1). Let the number of such p by q matrices be
. Then our target is finding 
.
Suppose
denote the entry in the first column such that it is the toppest entry in the first column with non-zero entries (i.e. 
for all 
.) So the matrix looks like:
The black parts will be with all zero entries (by definition of and by condition 3). So the construction of this matrix can be divided into two parts:
a) constructing a 1 by k sub-matrix such that
with 
and 
.
b) constructing the (p-1) by (q-k+1) sub-matrix A such that the three conditions are satisfied.
By simple combinatorics, there are
ways to construct part a) (if you do not see why, read the notes "Combinations and Permutations" in Mathematical Database; in particular, it is page 10 to 14) and by definition, there are 
ways to construct part b). As k can be any value between 1 and q (inclusive), we have the recurrence relation:
Compare this recurrence to the one for Catalan numbers. Do you see the similarity? If so, try to continue. I will complete this passage a few days later (hopefully...).
Let me recall the key idea again. Convolution of generating functions can be useful when we try to count a class of combinatorial objects, while these objects can be constructed by joining two smaller objects of size k and M-k.
Here comes the question, which looks really unfavourite when you first see it. An n by n square matrix M satisfies the following conditions: (1) every entry is a non-negative integer; (2) the sum of entries in each column is n-1; (3) for any two entries which are both positive, denote the coordinates by
and , then .Below shows a few 4 by 4 matrices which satisfy the three conditions:
, , The first two conditions can be easily visualized. The third condition can be visualized as follows: for any non-zero entry, its north-west and south-east direction entries must be all zero.
I will generalize by counting the number of p (number of columns) by q (number of rows) matrices satisfying the three conditions (note: the sum of each column is fixed to be n-1). Let the number of such p by q matrices be
. Then our target is finding .Suppose
denote the entry in the first column such that it is the toppest entry in the first column with non-zero entries (i.e. for all .) So the matrix looks like:
The black parts will be with all zero entries (by definition of and by condition 3). So the construction of this matrix can be divided into two parts:a) constructing a 1 by k sub-matrix such that
with and .b) constructing the (p-1) by (q-k+1) sub-matrix A such that the three conditions are satisfied.
By simple combinatorics, there are
ways to construct part a) (if you do not see why, read the notes "Combinations and Permutations" in Mathematical Database; in particular, it is page 10 to 14) and by definition, there are ways to construct part b). As k can be any value between 1 and q (inclusive), we have the recurrence relation:Compare this recurrence to the one for Catalan numbers. Do you see the similarity? If so, try to continue. I will complete this passage a few days later (hopefully...).
2009年6月10日 星期三
概率證明
有些時候，我們可以利用概率的性質來證明一些組合題。即使題目本身看來和概率毫不相干，但加入了概率的考慮往往可以讓我們得出一個簡潔的證明。以下提供一個例子。
問題：
某學校響應微調政策，開辦的 n 個科目均設中文班和英文班。每位同學均可自由選讀不同的科目，數量不限，但同一科目不可同時報讀中文班和英文班。已知對任意兩個科目，均存在一名學生以不同語文同時修讀兩科。若每科最多有 10 名學生修讀，求 n 的最大可能值。
大家看下去前，不妨先停下來自己動動腦筋。
解答：
n 的最大可能值是 1024。
我們首先注意到 n=1024 是可能的：如果全校有 10 位學生，每人均報讀全部 1024 個科目，且學生 i 報讀第 j 個科目的中文班當且僅當 j 的二進制表示中右方數起的第 i 個位是 1（否則報讀第 j 個科目的英文班），則不難檢查得知這符合題中的條件。
以下證明 n 不可大於 1024。假設學生入學時會被隨機編成「中文人」或「英文人」。設 Ei 表示事件「第 i 個科目的學生全部選讀了對應自己身份的語文班」，則由於每科最多有 10 名學生修讀，故 P(Ei) ≧ 1/210 = 1/1024。再者，由「對任意兩個科目，均存在一名學生以不同語文同時修讀兩科」可知 E1、E2、…、En 是互斥事件，故此
從而必有 n≦1024。
這個帶點神秘感的概率題解，某程度上其實對應一些數算的技巧，再用概率加以包裝。概率證明還可以處理一些更複雜的情況，例如可以使用 Lovasz local lemma 來處理一些難以準確計算的概率，有興趣的讀者可點擊上方的連結細看。順帶一提，證明以上定理的 Lovasz 曾在國際數學奧林匹克（IMO）奪得三金一銀，而他的兒子至今亦已在 IMO 奪得一金一銀！
問題：
某學校響應微調政策，開辦的 n 個科目均設中文班和英文班。每位同學均可自由選讀不同的科目，數量不限，但同一科目不可同時報讀中文班和英文班。已知對任意兩個科目，均存在一名學生以不同語文同時修讀兩科。若每科最多有 10 名學生修讀，求 n 的最大可能值。
大家看下去前，不妨先停下來自己動動腦筋。
解答：
n 的最大可能值是 1024。
我們首先注意到 n=1024 是可能的：如果全校有 10 位學生，每人均報讀全部 1024 個科目，且學生 i 報讀第 j 個科目的中文班當且僅當 j 的二進制表示中右方數起的第 i 個位是 1（否則報讀第 j 個科目的英文班），則不難檢查得知這符合題中的條件。
以下證明 n 不可大於 1024。假設學生入學時會被隨機編成「中文人」或「英文人」。設 Ei 表示事件「第 i 個科目的學生全部選讀了對應自己身份的語文班」，則由於每科最多有 10 名學生修讀，故 P(Ei) ≧ 1/210 = 1/1024。再者，由「對任意兩個科目，均存在一名學生以不同語文同時修讀兩科」可知 E1、E2、…、En 是互斥事件，故此
1 ≧ P(E1∪E2∪…∪En) = P(E1) + P(E2) + ... + P(En) ≧ n/1024，
從而必有 n≦1024。
這個帶點神秘感的概率題解，某程度上其實對應一些數算的技巧，再用概率加以包裝。概率證明還可以處理一些更複雜的情況，例如可以使用 Lovasz local lemma 來處理一些難以準確計算的概率，有興趣的讀者可點擊上方的連結細看。順帶一提，證明以上定理的 Lovasz 曾在國際數學奧林匹克（IMO）奪得三金一銀，而他的兒子至今亦已在 IMO 奪得一金一銀！
2009年5月24日 星期日
Two Problems about Countability
Recently I heard two related problems about countability. They should be good exercises for mathematial analysis amateur.
Below N denotes the set of natural numbers.
The first question is, is there exists an uncountable collection of finite subsets of N, such that for any two subsets A and B in the collection, one is the subset of another?
The second question is, is there exists an uncountable collection of subsets of N, such that for any two subsets A and B in the collection, one is the subset of another?
------
The first question is very easy. The second question is a bit tricky.
Below N denotes the set of natural numbers.
The first question is, is there exists an uncountable collection of finite subsets of N, such that for any two subsets A and B in the collection, one is the subset of another?
The second question is, is there exists an uncountable collection of subsets of N, such that for any two subsets A and B in the collection, one is the subset of another?
------
The first question is very easy. The second question is a bit tricky.
2009年5月22日 星期五
四捨五入
日前有報章報導，東亞銀行的網上系統有漏洞，只要不斷透過四捨五入造成的誤差，便可安坐家中賺取利潤。本文談談「四捨五入」這個數學上常用的取近似值的方法。
四捨五入的原理很簡單，基本上就是「向較接近的一方取近似值，以減少誤差」。例如，要把123.456 取小數點後一位的近似值，則因為 123.456 界乎 123.4 和 123.5 之間，而且較接近後者，因此我們取 123.5 作為近似值。
這裡有一個小問題，就是「較接近的一方」並不一定存在，例如把 123.450 捨入至 123.4 和 123.5 都是「同樣接近」的，故此我們根據「五入」的規則，把 123.450 向上捨入至 123.5。但這樣做的話得出的近似值會偏大。如果只是把 123.450 變成 123.5 當然問題不大，不過如果是 1.5 變 2，或 10.5 變 11 的話，而且經常要「五入」的話（這樣的例子是存在的，例如以 0.5 分為評分單位但最終分數必定是整數的考試），那就很不同了。
為了解決這個「偏大」的問題，一個「修正版」的四捨五入法是「四捨六入五留雙（banker's rounding）」。名字本身有點誤導：雖然叫「六入」，但其實是「(5+ε)入」，例如 123.456 仍會「(5.6)入」至 123.5。只是當出現 123.450 這些「打和」的情況時，才採用「五留雙」的規則：如果 5 字前的位是雙數則保留，單數則進位，故基於「4」是雙數，123.450 會向下捨入至 123.4，而 123.550 則會上捨入至 123.6。至於「banker」是否真的採用此規則，大家不妨測試一下。
那麼為甚麼要「留雙」而不是「留單」呢？我有以下猜測。在以上 123.456 的例子中，如果採用四捨五入法取小數點後一位的近似值，則會變成 123.5，如果再把近似值取最接近整數，則變成 124。問題是最接近 123.456 的整數應是 123 才對。再細看一下，我們發現其實 123.44...445 已經可以「合法地」變成 124：只要逐位「五入」即可，而且即使採用「四捨六入五留單」，同樣的情況仍會發生。採用「五留雙」的話，這樣的情況會得到一點點的改善（雖然也好不到哪裡）：123.4500...001 才可以「合法地」變成 124！
四捨五入的原理很簡單，基本上就是「向較接近的一方取近似值，以減少誤差」。例如，要把123.456 取小數點後一位的近似值，則因為 123.456 界乎 123.4 和 123.5 之間，而且較接近後者，因此我們取 123.5 作為近似值。
這裡有一個小問題，就是「較接近的一方」並不一定存在，例如把 123.450 捨入至 123.4 和 123.5 都是「同樣接近」的，故此我們根據「五入」的規則，把 123.450 向上捨入至 123.5。但這樣做的話得出的近似值會偏大。如果只是把 123.450 變成 123.5 當然問題不大，不過如果是 1.5 變 2，或 10.5 變 11 的話，而且經常要「五入」的話（這樣的例子是存在的，例如以 0.5 分為評分單位但最終分數必定是整數的考試），那就很不同了。
為了解決這個「偏大」的問題，一個「修正版」的四捨五入法是「四捨六入五留雙（banker's rounding）」。名字本身有點誤導：雖然叫「六入」，但其實是「(5+ε)入」，例如 123.456 仍會「(5.6)入」至 123.5。只是當出現 123.450 這些「打和」的情況時，才採用「五留雙」的規則：如果 5 字前的位是雙數則保留，單數則進位，故基於「4」是雙數，123.450 會向下捨入至 123.4，而 123.550 則會上捨入至 123.6。至於「banker」是否真的採用此規則，大家不妨測試一下。
那麼為甚麼要「留雙」而不是「留單」呢？我有以下猜測。在以上 123.456 的例子中，如果採用四捨五入法取小數點後一位的近似值，則會變成 123.5，如果再把近似值取最接近整數，則變成 124。問題是最接近 123.456 的整數應是 123 才對。再細看一下，我們發現其實 123.44...445 已經可以「合法地」變成 124：只要逐位「五入」即可，而且即使採用「四捨六入五留單」，同樣的情況仍會發生。採用「五留雙」的話，這樣的情況會得到一點點的改善（雖然也好不到哪裡）：123.4500...001 才可以「合法地」變成 124！
2009年5月11日 星期一
Some linear algebra
These days some of my friends discussed some linear algebra problems with me. I found them quite interesting, so let me post some of them here.
1. If A and B are square matrices of the same size, then the spectrums of AB and BA are the same. More precisely, the generalized eigenvalues of AB and BA over the complex numbers occur with the same multiplicity. This is clear when A is invertible, because then AB and BA are similar. If A is not invertible, then we can approximate A by invertible matrices. The spectrum of AB is just the zeroes of det(xI-AB) (counted with multiplicities). The claim then follows easily. This generalizes the fact that the traces and determinants of AB and BA are the same.
2. If A and B are real square matrices of the same size and if there is a complex matrix U such that
, then there is a real matrix M such that 
. In other words, if two real matrices are similar over the complex numbers, then they are similar over the reals. Proof: Look at the equation MA = BM, where M is a square matrix of the same size as A and B. This is a linear system of equations in the entries of M with real coefficients. Hence if S_c is the complex vector space of complex matrices that satisfy this equation and S_r is the real vector space of real matrices that satisfy the same equation, then the complex dimension of S_c is the same as the real dimension of S_r. Now by assumption this dimension is at least 1. We want to find a real matrix in S_r that is invertible. Let 
be a basis of S_r over the reals. Then this is also a basis of S_c over the complex. By assumption there is a linear combination 
over the complex numbers whose determinant is non-zero. Hence the polynomial 
in 
does not vanish identically over 
. It follows that this polynomial cannot vanish identically over 
. Hence there is a real linear combination of that is invertible. This finishes the proof.
3. This is more or less for my own benefit, to recall the following proof of the well-known fact that any normal matrix is diagonalizable over C. Key: Assume A is normal, i.e. A commutes with A*. Then if x is an eigenvector of A, x is also an eigenvector of A*. In fact if Ax = tx, then
when A commutes with A*. This allows us to proceed by induction on the dimension of the vector space: first pick any eigenvector x of A. Then its orthogonal complement is preserved by A, because x is also an eigenvector of A*. Hence we can reduce to one dimension lower, and by induction this completes the proof.
1. If A and B are square matrices of the same size, then the spectrums of AB and BA are the same. More precisely, the generalized eigenvalues of AB and BA over the complex numbers occur with the same multiplicity. This is clear when A is invertible, because then AB and BA are similar. If A is not invertible, then we can approximate A by invertible matrices. The spectrum of AB is just the zeroes of det(xI-AB) (counted with multiplicities). The claim then follows easily. This generalizes the fact that the traces and determinants of AB and BA are the same.
2. If A and B are real square matrices of the same size and if there is a complex matrix U such that
, then there is a real matrix M such that . In other words, if two real matrices are similar over the complex numbers, then they are similar over the reals. Proof: Look at the equation MA = BM, where M is a square matrix of the same size as A and B. This is a linear system of equations in the entries of M with real coefficients. Hence if S_c is the complex vector space of complex matrices that satisfy this equation and S_r is the real vector space of real matrices that satisfy the same equation, then the complex dimension of S_c is the same as the real dimension of S_r. Now by assumption this dimension is at least 1. We want to find a real matrix in S_r that is invertible. Let be a basis of S_r over the reals. Then this is also a basis of S_c over the complex. By assumption there is a linear combination over the complex numbers whose determinant is non-zero. Hence the polynomial in does not vanish identically over . It follows that this polynomial cannot vanish identically over . Hence there is a real linear combination of that is invertible. This finishes the proof.3. This is more or less for my own benefit, to recall the following proof of the well-known fact that any normal matrix is diagonalizable over C. Key: Assume A is normal, i.e. A commutes with A*. Then if x is an eigenvector of A, x is also an eigenvector of A*. In fact if Ax = tx, then
when A commutes with A*. This allows us to proceed by induction on the dimension of the vector space: first pick any eigenvector x of A. Then its orthogonal complement is preserved by A, because x is also an eigenvector of A*. Hence we can reduce to one dimension lower, and by induction this completes the proof.
2009年5月1日 星期五
一道組合題－－題解
這是上文提到的組合數學題題解。
若小方塊是橫放的，我們設它蓋著 k 和 k + 1。這個小方格蓋著的數字的積是 k(k + 1)，不難驗算它和 0.5[k2 + (k + 1)2] - 0.5 等價。
若小方塊是縱放的，我們設它蓋著 k 和 k + 10。這個小方格蓋著的數字的積是 k(k + 10)，不難驗算它和 0.5[k2 + (k + 10)2] - 50 等價。
假設 n 個小方塊是橫放的，50 − n 個小方塊是直放的。當我們把這 50 個積加起來時，不難發現我們必定把 0.5 × 12、0.5 × 22、0.5 × 32、……、0.5 × 1002 都在藍色的部分加了一次，而綠色的部分則為 n 個 -0.5 及 (50 - n) 個 -50。我們注意 n 的值不影響前半部分，只影響後半部分的和。因此，為使這個和盡量大，我們應使後半部分盡量大。不難得知當 n 是 50 時，這個和便達到最大值 0.5(12 + 22 + ... + 1002) - 50 × 0.5 = 169150；同理，當 n 是 0 時，這個和便達到最小值 0.5(12 + 22 + ... + 1002) - 50 × 50 = 166675。因為我們可用 50 個橫放的小方格或 50 個直放的小方格蓋著方格表，所以這兩個值都是可取的。
由上述討論可知，我們只需知道橫放的小方塊的數量，便可求得該和。我們可由填色的方法證明，橫放的小方塊的數量必定是在 0 至 50 之間的共 26 個偶數。因此這個和共有 26 個可能值。
若小方塊是橫放的，我們設它蓋著 k 和 k + 1。這個小方格蓋著的數字的積是 k(k + 1)，不難驗算它和 0.5[k2 + (k + 1)2] - 0.5 等價。
若小方塊是縱放的，我們設它蓋著 k 和 k + 10。這個小方格蓋著的數字的積是 k(k + 10)，不難驗算它和 0.5[k2 + (k + 10)2] - 50 等價。
假設 n 個小方塊是橫放的，50 − n 個小方塊是直放的。當我們把這 50 個積加起來時，不難發現我們必定把 0.5 × 12、0.5 × 22、0.5 × 32、……、0.5 × 1002 都在藍色的部分加了一次，而綠色的部分則為 n 個 -0.5 及 (50 - n) 個 -50。我們注意 n 的值不影響前半部分，只影響後半部分的和。因此，為使這個和盡量大，我們應使後半部分盡量大。不難得知當 n 是 50 時，這個和便達到最大值 0.5(12 + 22 + ... + 1002) - 50 × 0.5 = 169150；同理，當 n 是 0 時，這個和便達到最小值 0.5(12 + 22 + ... + 1002) - 50 × 50 = 166675。因為我們可用 50 個橫放的小方格或 50 個直放的小方格蓋著方格表，所以這兩個值都是可取的。
由上述討論可知，我們只需知道橫放的小方塊的數量，便可求得該和。我們可由填色的方法證明，橫放的小方塊的數量必定是在 0 至 50 之間的共 26 個偶數。因此這個和共有 26 個可能值。
訂閱：
文章 (Atom)