## Announce

Puki contents have been moved into SONOTS Plugin (20070703)

## Inequalities

$$\frac{n!}{m!} \leq n^{n-m}$$

### Fano's inequality

$$H(X|\hat{X}(Y)) \leq H(X|Y) \leq \Pr(X\neq\hat{X})log(|{}\mathcal{X}|-1) + h(\Pr(X\neq\hat{X})) \leq \Pr(X\neq\hat{X})log|{}\mathcal{X}| + 1$$

### Triangle inequality

In a normed vector space? V, the triangle inequality is

$$\displaystyle \|x + y\| \leq \|x\| + \|y\| \quad \forall \, x, y \in V$$

### Cauchy-schwartz inequality

The Cauchy–Schwarz inequality states that for all vectors x and y of a real number|real? or complex number|complex? inner product space?,

$$|\langle x,y\rangle| \leq \|x\| \cdot \|y\|.$$

(Think of $\langle x,y \rangle = \|x\|\|y\|cos\theta$)

In euclidean space, :$\left(\sum_{i=1}^n x_i y_i\right)^2\leq \left(\sum_{i=1}^n x_i^2\right) \left(\sum_{i=1}^n y_i^2\right).$

For the inner product space of square-integrable complex-valued functions

\left|\int f(x) \overline{g}(x)\,dx\right|^2\leq\int \left|f(x)\right|^2\,dx \cdot \int\left|g(x)\right|^2\,dx.

A generalization of this is the Hölder inequality?.

Expectation (probability) is inner product of this form.

### Jensen's inequality

If f is a convex function $$f\left(\mathbb{E}\{X\}\right) \leq \mathbb{E}\{f(X)\}.$$

### Chebyshev inequality

mean から離れた値の確率は低い。どの確率分布でも。 No more than $1/k^2$ of the values are more than k standard deviations away from the mean.

Let X be a r.v. with expected value $\mu$ and finite variance $\sigma^2$. Then for any real number? $k > 0$,

\Pr(\left|X-\mu\right|\geq k\sigma)\leq\frac{1}{k^2}.

Only the cases $k > 1$ provide useful information. This can be equivalently stated as

\Pr(\left|X-\mu\right|\geq \alpha)\leq\frac{\sigma^2}{\alpha^2}.