數學資料庫手記: 10月 2009

2009年10月23日星期五

數學講座

日期：2009 年 11 月 20 日（星期五）
時間：下午 6 時 30 分至 8 時 30 分
地點：香港城市大學教學樓四樓 LT18 演講廳
講者：曾淵滄博士
講題：投資全攻略

簡介：
本講座旨在從科學角度與重點介紹甚麼是管理科學，亦討論管理科學如何在投資及財務應用方面所扮演之角色。本講座亦專為有志參加快張開辦的統計學課程而設。

有關其他詳情及報名方法，可瀏覽這裡。
（如果無法載入，可複製網址 http://hkage.org.hk/b5/new/Students/ma/0910003/poster.pdf）

2009年10月19日星期一

死後的paper？

前兩天聽了一個關於random graph的seminar，回到辦公室就拿起Janson, Luczak和Rucinski的Random Graphs查一些terms的意思。隨手一揭，見到Erdős, Suen和Winkler在1995年一起出了一份paper。當時我想如果這是Paul Erdős的話，他不是已經離世很久了嗎？但查一查wiki，才知道他是在1996年離世的。

但另外查一查DBLP，竟發現Paul Erdős直到2006年為止仍然有聯名的paper發。究竟是因為其他的作者在十多年前和他討論得出成果，所以將Paul Erdős的名字寫在作者欄上，還是這個世界上有另一個Paul Erdos呢？煩請有識之士指點迷津。

2009年10月14日星期三

AM-GM 不等式的幾個證明（六）

看見 Kahoo 給了 AM-GM 不等式這麼多個精彩的證明，不禁想再來一個用微分和凸函数 (convex functions) 的。

這裏我們只需留意對任意實數 x 和 a，

$e^x - e^a \geq e^a (x-a)$

這不等式可以用很多不同的方法來證明，其中要想清楚當中的概念的，比較好的方法，是留意 $e^x$ 是一凸函數，故其導數是遞增的，用中值定理即可推出上述不等式。（也可以不失一般性假設 $a = 0$ ，從而用一元微積分或 $e^x$ 的 Taylor 展開求得此不等式。）

有了這不等式以後，對正數 $x_1, \dots, x_n$ ，

$x_k = e^{\log x_k} \geq e^a + e^a (\log x_k - a), \qquad k = 1,\dots,n$

這裏 a 可以是任何實數。把上列的不等式平均起來，得到

$\frac{x_1+\dots+x_n}{n} \geq e^a + e^a \left(\frac{\log x_1 + \dots + \log x_n}{n} - a\right)$ ------(1)

取 $a = \frac{\log x_1 + \dots + \log x_n}{n}$ ，則

$\frac{x_1+\dots+x_n}{n} \geq e^{\frac{\log x_1 + \dots + \log x_n}{n}} = (x_1 \dots x_n)^{\frac{1}{n}}$

從而 AM-GM 不等式得證。事實上不等式 (1) 的右邊是一關於 a 的函數，左邊則跟 a 無關，所以我們會取的 a 使得 (1) 的右邊達至最大值，而這正是我們上面這樣取 a 的原因。

這證明的一個好處，是我們可以用同樣的辦法證明以下這個 AM-GM 不等式的推廣：對任意 $x_1,\dots,x_n \geq 0$ ，和任意正數 $\lambda_1,\dots,\lambda_n$ 使得 $\lambda_1+\dots+\lambda_n = 1$ ，有

$\lambda_1 x_1 + \dots + \lambda_n x_n \geq x_1^{\lambda_1} \dots x_n^{\lambda_n}$

從上面的討論可知，其實 AM-GM 不等式是函數 $e^x$ 的 convexity 的反映。對任何的凸函數 f，我們都有 Jensen 不等式，詳見 wikipedia。

2009年10月11日星期日

AM-GM 不等式的幾個證明（五）

作為本系列的完結篇，我們看看 AM-GM 不等式的一個不用數學歸納法的證明。本證明主要用到排序不等式，此不等式指出若 $a_1\le a_2\le\cdots\le a_n$ 而 $b_1\le b_2\le\cdots\le b_n$ ，那麼當我們把這些 a_i 和 b_i「配對相乘再相加」時，有以下不等式：

$\begin{align*} &\ a_1b_n+a_2b_{n-1}+\cdots+a_nb_1\\ \le&\ a_1b_{f(1)}+a_2b_{f(2)}+\cdots+a_nb_{f(n)}\\ \le&\ a_1b_1+a_2b_2+\cdots+a_nb_n \end{align*}$

這裡 f(1)、f(2)、…、f(n) 是 1, 2, ..., n 的一個任意排列，而以上不等式中的三行分別叫「逆序和」、「亂序和」和「順序和」。不等式看起來有點複雜，但其實背後意念很簡單：假設一批學生分 n 組比賽（人數分別是 a₁、a₂、…、a_n），而每組均選擇 n 種隊服中的一種（價錢分別是 b₁、b₂、…、b_n），那麼最省錢的自然是越多人的組別使用越便宜的隊服（即逆序和），最花錢的自然是越多人的組別使用越貴的隊服（即順序和）。利用排序不等式，不難證明對任意正數 y₁、y₂、…、y_n 皆有

$\frac{y_1}{y_2}+\frac{y_2}{y_3}+\cdots+\frac{y_n}{y_1}\ge n$

（不失一般性設 $y_1\le y_2\le\cdots\le y_n$ ，並設 $a_i=y_i$ 和 $b_{n-i}=\frac1{y_i}$ ，再使用「亂序和 ≧ 逆序和」即可）。

現在我們用以上結果來證明 AM-GM 不等式。不妨設 x₁x₂…x_n = 1（這可通過代換 $x_i'=\frac{x_i}{\sqrt[n]{x_1x_2\cdots x_n}}$ 得到），並設

$y_1=\frac1{x_1},\quad y_2=\frac1{x_1x_2},\quad\ldots,\quad y_n=\frac1{x_1x_2\cdots x_n}=1$

即可得

$x_1+x_2+\cdots+x_n=\frac{y_n}{y_1}+\frac{y_1}{y_2}+\cdots+\frac{y_{n-1}}{y_n}\ge n$

從而證明了 AM-GM 不等式。

順帶一提，排序不等式的等號成立當且僅當 $a_1=a_2=\cdots=a_n$ 或 $b_1=b_2=\cdots=b_n$ ，大家不妨試試由此導出 AM-GM 不等式的等號成立當且僅當 $x_1=x_2=\cdots=x_n$ 。

2009年10月6日星期二

Gil Kalai's Seminar

上週四Hebrew University of Jerusalem和Yale University教授Gil Kalai來了Courant Institute講seminar。大家可能對這個名字有點印象，因為我曾在一篇手記 "Test Your Intuition"中提及他的網誌"Combinatorics and More"。

平時同一時段的"theory seminar"，有多於15人已屬罕見，但今次Prof. Kalai來講seminar卻吸引了38人來。平時有空位剩的房間一下子全院滿座，還有幾個人坐地下聽。

Prof. Kalai講了三個猜想，其中一個比較易懂和有趣，可以在這裏講講。

設 $f:\{-1,1\}^n\rightarrow\{-1,1\}$ 。我們可以進行一個"Fourier Transform"，即寫成 $f(x)=\sum_{S\subset\{1,2,\cdots,n\}} \hat{f}(S) W_S$ ，當中 $W_S=\Pi_{i\in S} x_i$ （這與一般Fourier Series中的 $e^{i n x}$ 的角色相同。）假設 $x=(x_1,x_2,\cdots,x_n)$ ，若每一個 $x_i$ 均獨立地有機會率 t 改變值（即由-1變成1或由1變成-1），若 $f(x)=f(y)$ 的機會很高，我們就可說 f 是noise stable。

甚麼情況下 f 是noise stable呢？Prof. Kalai舉了一個有趣的例子，就是說美國總統選舉，若Obama得票的數目是單數他就當選，否則McCain當選，這個選舉就很"noisy"，對吧？由此例子見到，noise stable的函數，它的Fourier expansion $f(x)=\sum_{S\subset\{1,2,\cdots,n\}} \hat{f}(S) W_S$ 中，當S是一個較大的集合時， $\hat{f}(S)$ 的值就應該很小。

2009年10月5日星期一

數學講座

日期：2009 年 11 月 6 日（星期五）
時間：下午 6 時 30 分至 8 時
地點：九龍塘教育服務中心西座四樓演講廳
講者：蕭文強教授
講題：難「分」難「解」的數學
簡介：

日常生活中不時碰到分配問題，例如工作時分配人手、得到獎賞後分配獎品、各選區分配議席、眾人分配美食等等。易乎？難乎？單單懂得除數是否就足夠呢？在這個講座讓我們一起探索一些有趣的例子。

有關其他詳情及報名方法，可瀏覽這裡。
（如果無法載入，可複製網址 http://hkage.org.hk/b5/new/Students/ma/091106mkma/poster_b5.pdf）

2009年10月1日星期四

AM-GM 不等式的幾個證明（四）

上回看過 AM-GM 不等式的一個「普通數學歸納法」證明。這裡我們再看三個類似的證明。一如之前，設 x_i 為正數，並已知 AM-GM 不等式對 n=1 和 n=2 成立。

假設 n=k 時 AM-GM 不等式成立，並考慮 n=k+1 時的情況。如果 $x_1=x_2=\cdots=x_{k+1}$ ，則 AM-GM 不等式顯然成立，否則不妨設各數中 x₁ 最小，x_k+1 最大，那麼這 k+1 個數的平均（不論是算術平均或是幾何平均）均大於 x₁ 而小於 x_k+1。以下用三個方法證明 n=k+1 的情況。

方法一

設 $G_{k+1}=\sqrt[k+1]{x_1x_2\cdots x_{k+1}}$ 。由歸納假設可知

$\frac{{x_1x_{k+1}}}{{(G_{k+1})^2}} + \frac{{x_2 }}{{G_{k+1}}}+\cdots+\frac{{x_{k+1}}}{{G_{k+1}}}\ge k\cdot\sqrt[k]{{\frac{{x_1x_2\cdots x_{k + 1} }}{{(G_{k+1})^{k+1}}}}} = k$ ，

從而 $\frac{{x_1 }}{{G_{k + 1} }} + \cdots + \frac{{x_{k + 1} }}{{G_{k + 1} }} \ge k - \frac{{x_1 x_{k + 1} }}{{(G_{k + 1} )^2 }} + \frac{{x_1 + x_{k + 1} }}{{G_{k + 1} }} \ge k + 1$ ，其中最後一個不等式成立是因為

$\frac{{x_1 + x_{k + 1} }}{{G_{k + 1} }} - \frac{y}{{(G_{k + 1} )^2 }} \ge 1 \Leftrightarrow (G_{k + 1} - x_1 )(G_{k + 1} - x_{k + 1} ) \ge 0$ 。

方法二

設 $R=\frac{\sqrt[k]{x_1x_2\cdots x_k}}{x_{k+1}}$ ，則 $0<R<1$ ，故此

$\100dpi \begin{align*} x_1+x_2+\cdots+x_{k+1}&\ge(kR+1)x_{k+1}\\ &=\left[\left(1-R^{\frac1{k+1}}\right)\left(1+R^{\frac1{k+1}}+\cdots+R^{\frac{k}{k+1}}\right)\right]x_{k+1}\\ &>\left[\left(1-R^{\frac1{k+1}}\right)(k+1)R^{\frac{k}{k+1}}\right]x_{k+1}\\ &=(k+1)\sqrt[k+1]{x_1x_2\cdots x_{k+1}} \end{align*}$

方法三

$\100dpi \begin{align*} \frac{x_1+x_2+\cdots+x_{k+1}}{k+1}&\ge\frac{k\sqrt[k]{x_1x_2\cdots x_{k}}+x_{k+1}}{k+1}\\ &=\sqrt[k]{x_1x_2\cdots x_{k}}+\frac{x_{k+1}-\sqrt[k]{x_1x_2\cdots x_{k}}}{k+1}\\ &=\sqrt[k+1]{\left(\sqrt[k]{x_1x_2\cdots x_{k}}+\frac{x_{k+1}-\sqrt[k]{x_1x_2\cdots x_{k}}}{k+1}\right)^{k+1}}\\ &>\sqrt[k+1]{\left(\sqrt[k]{x_1x_2\cdots x_{k}}\right)^{k+1}+(k+1)\left(\sqrt[k]{x_1x_2\cdots x_{k}}\right)^{k}\left(\frac{x_{k+1}-\sqrt[k]{x_1x_2\cdots x_{k}}}{k+1}\right)}\\ &=\sqrt[k+1]{x_1x_2\cdots x_{k+1}} \end{align*}$

除了用數學歸納法外，AM-GM 不等式還可以用其他方法來證明，我們下回再看。

數學資料庫手記

2009年10月23日星期五

數學講座

2009年10月19日星期一

死後的paper？

2009年10月14日星期三

AM-GM 不等式的幾個證明（六）

2009年10月11日星期日

AM-GM 不等式的幾個證明（五）

2009年10月6日星期二

Gil Kalai's Seminar

2009年10月5日星期一

數學講座

2009年10月1日星期四

AM-GM 不等式的幾個證明（四）

著作人

stat

網誌存檔

2009年10月23日 星期五

2009年10月19日 星期一

2009年10月14日 星期三

2009年10月11日 星期日

2009年10月6日 星期二

2009年10月5日 星期一

2009年10月1日 星期四

著作人

stat

網誌存檔

2009年10月23日星期五

2009年10月19日星期一

2009年10月14日星期三

2009年10月11日星期日

2009年10月6日星期二

2009年10月5日星期一

2009年10月1日星期四