2 problems I’m working on right now:

1. Evaluate $latex\sum_{k=1}^{k=n}(n-k)2^{k-1}$ by somehow interpreting the term as a sum of disjoint sets.

2. Longest possible monotonic subsequence. Fun thinking about this in terms of directed graphs.

Thinking about today: say we add a new set S to a $\sigma$ -algebra , then the new $\sigma$ -algebra with this set appended, has additional sets of the form $(A \cup S) \cap (B\cup (X/S))$

Longest Subsequence

The problem of finding the longest monotonically decreasing subsequence has an O(n log n) solution. My soln is $O(n^2)$ .

Absolutely fascinating that a sequence can be represented as a permutation graph, which means that the problem of finding the longest subsequence morphs into the problem of finding the largest clique!

Thus, essentially, the question which I was trying to solve – prove that a sequence from 1…101, will contain a increasing or decreasing sub-seq of length 10, morphs into a problem of proving that the ramsey number is 10.

Longest Subsequence Algorithm

An algorithm that has O(n^2) time complexity & O(n) space complexity to find the longest monotonically decreasing subsequence:

Define new arrays. Length & pointer – length contains the length of the longest subsequence starting with a[i], and pointer points to the next element of that particular subsequence.
(for i = lastElementIndex -1 ; i >= 0 ; i–)

If (i is last element index)

i. Length[i] = 1, pointer[i] = null

Else

i. Go through all elements from j = i to j = lastElement, appropriately setting pointer & length – i.e. if a[i] > a[j], then clearly no sequence possible. Else, just choose the one with the longest length.

Constructing the sequence from the length/pointer arrays is a straightforward task then.

2 good resources

[tag Resources]

An intuitive feeler to Algebraic Geometry: http://rigtriv.wordpress.com/ag-from-the-beginning/

A nice introduction to what Algebraic Topology actually does: http://blog.mikael.johanssons.org/archive/2006/01/introduction-to-algebraic-topology-and-related-topics-i/

This is something that I never really understood well until actually working out copious amounts of basic topology.

Longest Subsequence

Problem is to find the longest monotonically increasing/decreasing subsequence.

1st approach was to try out a recursive algorithm, starting with {a_n-1,a_n} in {a_1…a_n}, and build up the sequence from there.

However, this doesn’t always work. Take for example if a_n-1 = a high number forwhen we want a monotonically decreasing subsequence.

Then that number ends up blocking out other numbers that come later but could be part of the subsequence.

Take for example the sequens {8,6,12,4,2}. Here, the algorithm yields {12,4,2}, which is clearly suboptimal.

Limits & Indicator Functions

Proved a simple theorem today. Let ${A_n}$ be a sequence of subsets. Then, we have

$\limsup_{n->\infty } A_n = {w : \sum 1_{A}(w)=\infty }$
$\liminf_{n->\infty } A_n = {w : \sum 1_{A^{c}}(w)< \infty }$

Proofs use a tedious amount of notation manipulation, but thinking of it in terms of indicator functions is interesting.

Path ahead

Looking back at my blog posts over the last year, it’s clear that there is no real pattern within the posts. In terms of my math education, I feel that 2008/2009 has been all over the place with little progress being made anywhere. The ‘shallow/broad’ approach isn’t working. In fact, the last two times I actually remember learning any concrete amount of math was a bit of Galois theory in the summer of 2009 (Rotman’s book for company on a Europe trip) and Information theory in the summer of 2007.

What’s required is focus.

So what I plan to do for 2010 is focus exclusively on one topic – probability. I shall work on 3 aspects of probability theory.

1. Random walks/stochastic processes (non-measure theoretic).

2. Measure & Probability

3. Applications of Probability – Statistical learning & Information theory

Update & Quadratic Reciprocity

Things have been a little busy with work so I haven’t had as much time as I would like for math. I’ve been pottering about here and there – mostly around finite fields and trying to prove $\sum_{d|n} \varphi(d) = n$ , but didn’t get anywhere I’m afraid.

I came pretty close though – at least by the proof in Apostol’s book. However, failed to make one simple but crucial connection.

Anyways, I started reading this book – Fearless Symmetry – and thought this could be good point to start learning a little bit about quadratic reciprocity and it’s connections to Galois theory. So the first problem that comes out is ‘What are the solutions for $x^2 = a \mod p$ .

One small conclusion that immediately comes about is that for any solution $r$ , $(r+p)^n$ is also a solution.

Proving the Cauchy-Schwarz Inequality

The inequality states:

$a_1b_1+a_2b_2 +.. a_nb_n <= \sqrt (a_1^2+ ..+a_n^2)\sqrt(b_1^2+..+b_n^2)$ .

This is very easily proved by squaring both sides, and cancelling the common terms.

One gets the following on doing this:

$2\sum_{i\neq j}a_ib_ia_jb_j <= \sum_{i\neq j}a_i^2b_j^2$ .

For every pair of indices i & j, we can take the two same terms from the RHS and put them onto the LHS, creating a sequence of sum of squares whose generic term is:

$a_i^2b_j^2+a_j^2b_i^2-2a_ia_jb_ib_j = (a_ib_j-a_jb_i)^2$ .

The sum of squares of the above form for every i,j is clearly positive.

Hence the inequality is true.