Since I’ve been using amazon so much lately, I decided I might as well take the plunge and use all its features. Just finished the first revision of my first listmania. Comments or suggestions for additions (keeping in mind the orthogonality condition)? I can’t think of any good ODE books.
Looks like my plan for the weekend is to spend some time in bed with Folland’s Real Analysis. I didn’t realize at the time I took the course what a godsend this book is– I thought it was too dense at the time– but now I see how it functions almost perfectly as a reference book for the analysis I need to know to handle advanced probability treatises.
The fact that he immediately takes the abstract approach to measures means that– besides the fact that, unlike in many books which serve the same function, pages aren’t wasted on the development of exclusively the Lebesgue measure/integral, which is then generalized and repeated for abstract measures/integrals– he completely covers probability spaces as a (albeit unmentioned) subset of his discussion. His functional analysis chapter is also pretty comprehensive in relation to the functional analysis I’ve seen used in probability treatises, even though he doesn’t cover the important topics of self-adjoint or compact operators. And, I’m particularly grateful for the chapter on point-set topology, because to my shame I forgot most of the general topology I knew, and that turns out to be very important (duh, I guess).
At this stage though, the most attractive feature of his book is the short chapter which provides short, rigorous proofs of the Central Limit Theorem, 0-1 Law, Laws of Large Numbers, and other basic probabilistic results.
We’re two lectures into the large deviations course, and I think I have some grasp of what large deviation theory is about. It deals with the probability of large deviations from expected values– “the analysis of the tail of probability distributions”. Here’s one example of a LDT result (a Large Deviation Principle):
Cramer’s Theorem
Letbe a sequence of bounded i.i.d. random variables with mean
, and let
be the empirical means; then the tail of the probability distribution of
decay exponentially with increasing
at a rate given by a convex rate-function
:
Cramer apparently first proved this theorem using complex variables method and found – the rate function– as a power series expansion. I’m glad to have discovered this, because the way we were shown of finding 
in class is very technical, and was supplied without motivation.
Specifically, we developed Cramer’s theorem by defining as the Fenchel transform of the logarithm of the moment generating function of 
, and proving (well, so far accepting the validity of) a technical lemma which has Cramer’s theorem as a corollary. Mathematically impressive, but it provides no motivation for why we knew that defining in that way would give us useful results. Apparently this formulation of is an application of another result in Large Deviation Theory, Varadhan’s Theorem on the asymptotics of expectations of random sequences.
An Introduction to Large Deviations for Teletraffic Engineers seems to be a good basic reference for LDT.
Ha! Things are looking up. I just read through the first 15 pages of one of our recommended readings for large deviations, on concentration of measure inequalities– 15 pages in under 45 minutes is nontrivial, folks :). At first I was scared because I couldn’t for the life of me figure out why
and that was literally the first equation on the first page! But then I decided to go with it for the nonce, and the rest went so smooth, I had learned about Bernstein’s inequality before I knew it. If the rest of the reading goes like this, I might remember stuff! I certainly understand it.
Oh, and I did figure out how to prove that heart stopper: use Fubini. I have seen this before, in a different context, when I was taking Papadakis’ fourier analysis course. See what I mean about forgetting stuff? At least this time forgetting helped me to figure out for myself how to prove it.
Studying probability is such a downer! I’ve seen all this stuff before, some of it several times, yet it all seems to fly right out of my head. Things like the monotone class theorem, which types of convergence of r.v.s imply other types of convergence and in what circumstances, 
, important basic stuff like that is taking me forever to review. Given this, my large deviations course is going to be hell! Not so much the stochastics course, because he’s starting from scratch with an accelerated review of probability, but in large deviations, I didn’t even understand the first lecture which was supposed to be heuristic and intuitive. Ha! I guess I should go review that lecture now…
I decided to go ahead and attempt one of my problem sets early, and I found that in the process, I needed to come up with an order two FD approximation to 
. Generally when I come across a question like this, it usually just asks for a 2nd order approximation to say the 1st derivative, and then I just mess around with various combinations of Taylor series expansions of the type 
, until I hit upon what I need.
Even for that relatively simple case, this procedure is a pain in the ass. I didn’t think I was up to it for the 3rd derivative, so I came up with a more systematic procedure, which can be used to get 
with accuracy 
. It gives a forward finite differences scheme, but the idea should be adaptable to backward and central difference schemes also.
Here’s the idea: let 
be a weight by which we will multiply 
. Then
so
Letting 
, what we want is 
, because if this holds true,
which would imply
as desired.
So the question is how do we choose and 
such that we have the appropriate conditions on 
? Well, note that if we write 
and 
as vectors, we have 
where 
. Conveniently, when such an 
is square, it is full rank (prove it!), so we can invert to find the weights. Since 
varies between 
and 
, letting contain 
to 
makes square.
Voila! (I’d like to say Q.E.D., but this was an algorithm, not a proof 
)
To recap, if you want to approximate with accuracy using forward differences, use the point approximation
where the weight vector 
is chosen to satisfy
where 
and the 1 is in the 
-th entry of the rhs vector.
Of course, you better check all my algebra if you intend to use this for anything important. I’m sure I messed up somewhere– I tried coding this up in Mathematica to test it and got weird results– but I’ve spent enough time on it for now.
Stephen Hawkings is giving a talk entitled “Running History Backwards” here on April 2nd, at 4pm. I have a required department colloqium from 4:15-5 on the same day. I actually wanted to go to this one, because it’s about optimization with PDEs as constraints: “Fast Algorithms for Variational Problems Constrained by Elliptic and Evolution Equations”. Sounds nice, yes? But from past experience I would be lucky to understand more than the introduction, and even that vaguely.
All other considerations aside, the opportunity is there for me to see the vaunted Dr. Hawkings– I’ve never read any of his books, being neither a theoretical physicist nor a frequent consumer of popular science works– so this would be my first exposure to him. How cool is that? Guess where I’m going to be at 4pm on April 2nd…
A really hot girl works in Guggenheim, the building next door to us. I pass her on the stairs several times a week, and sometimes see her working in her office at ungodly hours; this morning I ran into her leaving the Cats. Everytime I see her, even if she’s sitting at her computer, she looks like she just got back from doing something healthy to the n-th degree (like a 27K marathon), followed by a quick shower. I can’t put my finger on what makes her so attractive– yes, she’s definitely got the physical aspect: she’s somewhere between Lexa Doig (brunette and similar size and mannerisms and that fresh-out-of-the-shower-and-all-put-together look) and Ali Larter (body type)– but I suspect it has to do with the specific combination of brains, beauty, and especially strength-in-action that she represents. She seems to have it all, in the right proportions.
I have often wondered why Einstein’s paper on brownian motion was considered such a watershed. But then I realized that atoms were still controversial in 1905! Odd to think that during Einstein’s lifetime, we went from being unsure about atoms to the beginnings of quantum theory, and along the way managed to develop GR. Wow. I wonder what we’ll see in my lifetime?
At some point I have to read his original paper. I’ve seen his insights on Brownian motion explained in modern probabilistic terms several times (it’s as popular an illustratory example in probability texts as the wave equation or laplace’s equation are in PDE texts), but I suspect that they’ve been modernized, mathematized, and dephysicized. I’d like to see them in their natural habitat.
Incidentally, one of the courses I’m taking this term– and I’m freaking stoked about it!–, ACM 217: Stochastic calculus and stochastic control, will apparently have course notes online. If the quality of the notes yet to be posted is comparable to that of those already up, this will be a great resource to learn about stochastic processes and stochastic calculus.
