## 2009年9月27日 星期日

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

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

$A_n=\frac{x_1+x_2+\cdots+x_n}n$$G_n=\sqrt[n]{x_1x_2\cdots x_n}$，其中所有 xi 皆是正數。正如上回所說，我們有 A1 = G1 和 A2 ≧ G2。假設 Ak ≧ Gk。以下證明 Ak+1 ≧ Gk+1：我們有

$A_{k+1}\ge G_{k+1} \Leftrightarrow A_{k+1}^{k+1}\ge G_{k+1}^{k+1} \Leftrightarrow A_{k+1}^{2k}\ge A_{k+1}^{k-1}G_{k+1}^{k+1} \Leftrightarrow A_{k+1}\ge\sqrt[2k]{A_{k+1}^{k-1}G_{k+1}^{k+1}}$

\begin{align*} \sqrt[2k]{A_{k+1}^{k-1}G_{k+1}^{k+1}}&=\sqrt[2k]{A_{k+1}^{k-1}x_1x_2\cdots x_{k+1}}\\ &=\sqrt{\sqrt[k]{x_1x_2\cdots x_k}\sqrt[k]{x_{k+1}A_{k+1}^{k-1}}}\\ &\le\frac12\left(\sqrt[k]{x_1x_2\cdots x_k}+\sqrt[k]{x_{k+1}A_{k+1}^{k-1}}\right)\\ &\le\frac12\left(\frac{x_1+x_2+\cdots+x_k}k+\frac{x_{k+1}+A_{k+1}+A_{k+1}+\cdots+A_{k+1}}k \right )\\ &\le\frac1{2k}[(k+1)A_{k+1}+(k-1)A_{k+1}]\\ &=A_{k+1} \end{align*}

## 2009年9月22日 星期二

### 洗幾次牌先「夠」？

-----

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月16日 星期三

### 拍賣方法的藝術

「潛水」了兩個月，事關七月、八月初都在科大寫paper，忙到不得了，而八月中下旬就要準備出國和參加一連串的farewell。對了，我現在身處New York，正在New York University的Courant Institute讀PhD in Computer Science。

## 2009年9月6日 星期日

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

$\frac{x_1+x_2}2\ge\sqrt{x_1x_2}\quad\Leftrightarrow\quad\left(\sqrt{x_1}-\sqrt{x_2}\right)^2\ge0$

\begin{align*} \frac{x_1+x_2+x_3+x_4}4&=\frac12\left(\frac{x_1+x_2}2+\frac{x_3+x_4}2 \right )\\ &\ge\frac12\left(\sqrt{x_1x_2}+\sqrt{x_3x_4}\right)\\ &\ge\sqrt\left(\sqrt{x_1x_2}\right)\left(\sqrt{x_3x_4}\right)\\ &=\sqrt[4]{x_1x_2x_3x_4} \end{align*}

\begin{align*} \frac{x_1+x_2+x_3+\frac{x_1+x_2+x_3}3}4&\ge\sqrt[4]{x_1x_2x_3\left(\frac{x_1+x_2+x_3}3\right )}\\ \frac{x_1+x_2+x_3}3&\ge\left(\frac{x_1+x_2+x_3}3 \right )^{\frac14}\sqrt[4]{x_1x_2x_3}\\ \left(\frac{x_1+x_2+x_3}3 \right )^{\frac34}&\ge\sqrt[4]{x_1x_2x_3}\\ \frac{x_1+x_2+x_3}3&\ge\sqrt[3]{x_1x_2x_3} \end{align*}