Monthly Archives: May 2009

$\epsilon$ Induction

Induction over natural numbers is a standard tool in Mathematics. But what about doing induction over real numbers´? The structure is different and it's not immediately clear what is meant, so let me clarify it.

Let $P(v)$ be a proposition that we want to show for all $v \in \mathbb{R}^+_0$ .

Then we can use the following "induction principle" to prove it:

$\exists \epsilon \in \mathbb{R}^+$
$\text{a)} \forall u \in \left [0,\epsilon \right ]: P(u)$
$\text{b)} \left( \forall u \in \left [0, v - \epsilon \right ]: P(u) \right ) \Rightarrow P(v)$ ´

It's easy to show that this is a correct way to prove it. I'll use induction over natural numbers to prove it

Let $I_k := \left [k \cdot \frac \epsilon 2, (k+1) \cdot \frac \epsilon 2 \right ]$ .
Then let's show by induction over $k$ that $\text{(*)} \forall u \in I_k: P(u)$ :

Base:

From a) it follows that (*) already holds for $I_0$ and $I_1$ .

Induction Step ( $k \ge 2$ ):

If (*) holds for $I_0, ..., I_{k-1}$ , then it obviously holds for all $u \in \left [ 0, k \cdot \frac \epsilon 2 \right ]$ .

Fix $v \in I_k$ , then $v \le (k+1) \cdot \frac \epsilon 2 \Leftrightarrow v - \epsilon \le (k-2) \cdot \frac \epsilon 2 < k \cdot \frac \epsilon 2 \right$ . With b) it follows that $P(v)$ holds.

That is, $P(v)$ $\forall v \in I_k$ .

It should be possible to show that you can generalize this to:

$\exists \epsilon \in \mathbb{R}^+$
$\text{a)} \forall u \in \left [0,\epsilon \right ]: P(u)$
$\text{b)} \left( \forall u \in \left [\psi(v), \phi( v ) \right ]: P(u) \right ) \Rightarrow P(v)$
with $\phi( v ): \mathbb{R}^+ \to \mathbb{R}^+_0$ , $\psi( v ): \mathbb{R}^+ \to \mathbb{R}^+_0$ and $\psi(v) \le \phi(v) < v$ .

Analysis, Cauchy-Schwarz and Reciprocal Sums

Posted by BlackHC on May 7, 2009 No comments

Konkrete Analysis

First I want to share some solutions for the exercises of a Maths book. The book is called Konkrete Analysis by Folkmar Bornemann and is written in German as are my solutions for some of the exercises. (I think I cover about 70% of all exercises in the book and pretty much every easy one )

I don't claim that my solutions are correct and there are probably quite a few (uncorrected) mistakes, but right now I haven't been able to find any other openly available solutions. Although the book claims to be easily readable without attending the lectures of Professor Bornemann, I doubt that it is possible to do so successfully without being able to do the exercises and while doing so being able to get help or look at possible solutions to find new ideas.

I did all the exercises as way to prepare myself for the exam (it was very successful alas probably not in the most time efficient way), so it also contains solutions for old exams (but those are appended at the end and probably not interesting at all).

You can download the PDF konkrete-analysis-solutions here.

Cauchy-Schwarz and a Problem

The book is quite useful though as was the lecture "Analysis for Computer Scientists" which was based on the book (or vice-versa) and it is probably the single one lecture that has taught most since I started attending Computer Science at university.

One of the many topics (we covered a lot which was one of the nice things) was inequalities and the useful things you can do with them. Especially the Cauchy-Schwarz inequality turns out to be quite useful while pretty basic:

$<a,b> \leq ||a|| \cdot ||b||$ with $<a,b> = || a || \cdot || b ||$ when $\exists \lambda: a = \lambda b$

Interestingly enough this can already yield results that are quite difficult to obtain otherwise. For example we can easily prove lower or upper bounds that is the existence of a maximum or minimum by applying it.

First we obtain a lower or upper bound (for the right or the left side respectively) and then we can use the equality case to prove the existence of the a minium or maximum.

For example, let's take a look at this problem:

We have $x \in \mathbb{R}^n, 0 < x, \sum_{i=1}^n {x_i} = 1$ and want to minimize $\sum_{i=1}^n { \frac 1 x }$ .
We simply set $a_i := \sqrt{x_i}, b_i := \sqrt{ \frac 1 x_i }$ .

Then we get:

$\sum_{i=1}^n { a_i b_i } = \sum_{i=1}^n { \sqrt{ x_i } \frac 1 {\sqrt{ x_i }} } = \sum_{i=1}^n 1 = n$
$\leq \sqrt{ \sum_{i=1}^n \sqrt{x_i}^2 } \sqrt{ \sum_{i=1}^n \frac 1 {\sqrt{x_i}^2} } = \sqrt { \sum_{i=1}^n x_i } \sqrt{\sum_{i=1}^n \frac 1 x_i } = 1 \cdot \sqrt{\sum_{i=1}^n \frac 1 x_i }$

That is: $\sum_{i=1}^n \frac 1 x_i \geq n^2$ .

Now we know an lower bound for the reciprocal sum.
To determine the minimal x vector, we remember to start with:

$a = \lamda b \Leftrightarrow \sqrt x_i = \lambda \frac 1 \x_i \Leftrightarrow x_i = \lambda$

We use that with the constraint: $1 = \sum_{i=1}^n x_i = \sum_{i=1}^n \lambda = n \cdot \lambda$ ,
resulting in: $x_i = \lambda = \frac 1 n$ .

Generalization

The nice thing is you can go and generalize this finding to more interesting minimization problems as there also exist more advanced versions of the Cauchy-Schwarz inequality´ adding degrees of freedom to play around with´.

Thus it is possible to solve the following class of problems using a slightly more advanced Cauchy-Schwarz inequality:

$x,q \in \mathbb{R}^n; 0 < x, q$
$0 < \alpha, \gamma < \infty; \beta > 0$
$\large\sum_{i=1}^n {x_i}^\gamma = \beta$
$\large min \sum_{i=1}^n \frac {q_i} {x_i^\alpha}$

by utilizing

$\large \sum_{i=1}^n { a_i b_i } \le \sqrt[p]{ \sum_{i=1}^n a_i^p} \sqrt[p']{ \sum_{i=1}^n b_i^p'}$ with $\frac 1 p + \frac 1 {p'} = 1$

Equality requires the same linear dependence condition as the normal Cauchy-Schwarz inequation.

I've only deduced the solution for $\gamma = 1$ but it shouldn't be difficult to adapt it once you get the idea how it works (it's fairly straight forward).

You can find the whole deduction in the PDF "Minimum of a Generalized Reciprocal Sum".

For completeness' sake here are the results for an optimal solution $x^{*}$ :

$\large x_i^{*} = \beta \cdot \frac { \sqrt[1 + \alpha]{q_i} }{\sum_{k=1}^n \sqrt[1 + \alpha]{q_k}}$

$\large \frac { \left (\sum_{i=1}^n \sqrt[1 + \alpha]{q_i} \right )^{1 + \alpha}} {\beta^\alpha} = \sum_{i=1}^n \frac {q_i} {x_i^{*}^\alpha}$

Epilog

Coming up with the solution was actually a lot of fun and quite interesting because I didn't know it was possible to deduce it this way nor did I know how to do it before. If you read the PDF, I think it's quite nice how you can play around with the formulas and come up with new things from the Cauchy-Schwarz inequality.
If you are only interested in $x ^ {*}$ , you can shortcut everything by immediately skipping to the equality case once $p$ and $p'$ have been determined and solve for that.
I mainly wrote it all out because I wanted to make sure, that it actually was correct.

If it wasn't for my Analysis lecture last term, I probably wouldn't have found this.

Cheers,
Andreas

The Reverse Pigeonhole Principle

Posted by BlackHC on May 5, 2009 1 comment

Everybody (I hope) knows about the pigeonhole principle.

In short it states that:

If $f: N \to M$ and $n:= \left | N \right | \leq \left | M \right | =: m$ , then there exists at least one $m_0$ with $\left | f^{-1}\left ( m_0 \right ) \right | \geq \left \lceil \frac {n} {m} \right \rceil$ .

For example, if we have n + 1 pigeons in only n pigeonholes, there is (at least) one pigeonhole that has at least two pigeons inside (thus the name).

One thing I haven't seen mentioned anywhere yet (at least not with this name) is the reverse pigeonhole principle:

If $f: N \to M$ and $n := \left | N \right | \leq \left | M \right | =: m$ , then there exists at least one $m_0 \in M$ with $\left | f^{-1}\left ( m_0 \right ) \right | \leq \left \lfloor \frac {n} {m} \right \rfloor$ .

Again an example: if we have n + 1 pigeons (it's valid up to 2n - 1) and n pigeonholes, then there exists (at least one) pigeonhole with at most one pigeon in it.

The proof for the reverse principle is simple:

Assume that for all $m_0 \in M$ : $\left | f^{-1}\left ( m_0 \right ) \right | > \left \lfloor \frac {n} {m} \right \rfloor$ , that is each such set contains at least $\left \lfloor \frac {n} {m} \right \rfloor + 1$ elements, then from $\frac n m - 1 < \left \lfloor \frac {n} {m} \right \rfloor$ it follows that:

$n = \sum_{m_0 \in M} { \left | f^{-1} \left ( m_0 \right ) \right | \geq m \left ( \left \lfloor \frac {n} {m} \right \rfloor + 1 \right ) > m \cdot \frac n m = n }$ .

This clearly is a contradiction, so the original assumption must have been wrong, which proves the reverse pigeonhole principle.

I haven't seen this written down anywhere before and it's useful to keep it in my mind on its own because it shortens some arguments, so I hope this might help someone

On other news my LaTeX script is severly broken and I don't know why
For some reason it sometimes merges two LaTeX pieces into one because it forgets to echo the last " after the title (which is impossible, of course..).
Cheers,
Andreas

BlackHC’s Adventures in the Dev World

Just another weblog

Monthly Archives: May 2009