ChapterZero

I’ve been working my butt off for the past several days trying to complete the latest stochastic processes homework, but that looks like a losing fight, so I’ve pretty much relaxed. Now I’m just doing it because every so often I learn a way to do something I thought was incredibly hard.

Example #1: Let be a continuous random variable, and be a random variable uniformly distributed on ; assume and are independent of each other. Calculate where is a fixed number. That is, find the cdf of the random variable . I’m surprised it’s even possible to get a nice closed form solution to this, and sad to say the particular trick used to get it isn’t from me. It’s from one of the guys in the class, either Nathaniel or Yuan, or both. The basic idea is to:

• Find the pdf of the random variable
• Use the independence of and to find the joint pdf of
• The clever idea is here: use a transformation of random variables argument to find the joint pdf of
• Integrate out to get the marginal distribution for

The answer, after working out all this stuff, is Amazing. What’s even more amazing is that this is only one incidental calculation on the way to solving a larger problem. Perhaps there was a way to avoid this unpleasantness altogether?

Example #2: If are independent uniformly distributed random variables on [0,1], then the pdf of the random variable is This one is easy to show, but nonetheless a neat result. In particular, it means the expected value of the random variable is – not terribly intuitive.

The registration period for winter term courses has begun. Here’s a list of the courses that I’m considering, in no particular order:

• ACM 216: Markov chains, discrete stochastic processes, and applications.
• ACM 118: Methods in Applied Statistics and Data Analysis
• ACM 104: Linear Algebra
• ACM 210: Numerical Methods for PDEs
• EE 163: Communication Theory
• CDS 202: Geometry of Nonlinear Systems
• APh/EE 131: Optical Wave Propagation

I’m aiming to take all the probability related ACM courses, because I started getting interested in serious probability and stochastic processes over the summer, and what I’ve seen in class and read on my own this term has made it seem like an interest worth pursuing. The PDE course I would take, just because I know nothing about PDEs and they seem useful and interesting– plus there’s the possibility of me eventually working with stochastic pdes, which I know absolutely nothing about except that the idea is awfully cool. However, I don’t know if the numerical methods course will be an effective intro to the subject; I’ll have to ask around.

The linear algebra course is required, unfortunately. It puzzles me that you take numerical linear algebra before the linear algebra course. Admitted, the linear algebra course is almost definitely more technical, but the ordering still seems weird. The communication theory course and the optics course I’m not too jazzed about either, but I need to take an applied course, and those were the closest to interesting. The geometry course I would love to take to fulfill my applied course requirement, but I’m not sure I can slip that one by: even though it’s being offered by the control and dynamical systems option, it’s essentially a differential geometry class… not incredibly applied.

I did note as I was looking for classes that an awful lot of excellent, interesting courses that I’d love to take aren’t being offered next term.

Integration is one of those mathematical operations that should conform to common-sense: no matter what method of integration you’re using, no matter how high-falutin’, the area of a square should be the square of the length of its sides. And that’s the way its been up to now: Riemann, Lebesgue-Stieltjes, and Lebesgue integration… they’re all cut from the same cloth, all succeedingly more careful generalizations of the intuitive notion of measure.

Yesterday we were briefly introduced to a form of stochastic integration, namely that of integration of functions with respect to Brownian noise:

where is an orthonormal basis of and is a sequence of i.i.d. r.v.s, so the integral is a Gaussian r.v. for each . This definition does not seem to have much to do with the concept of measurement. Is this even well-defined? By the Riemann-Lebesgue lemma the sum converges, but apparently any o.n.b. can be used, so does changing it affect the integral? Despite the obscurity of its origins, I like the simple form of this integral.

Today, I found an online book which does a great job of motivating stochastic integrals. To abbreviate the example he gives, consider the problem of sending a probe to the moon. We’ll describe the state of the system as , where are the location, velocity, and momentum of the probe. In the ideal case, we know where is the force applied to the probe, so we can solve for

In the real world, there will be random effects we can’t account for deterministically, such as minor fluctuations in the gravitational field, collision with debris, etc., all of which we will call noise (note that this model doesn’t account for noise which is partially caused by the state , noise is a function of – I don’t know if this is a limitation of the theory, or just this example). Then we’d like to say that how much the noise affects the state of the system varies depending on the state of the system, giving the new equation

Since the noise is random, is in fact a stochastic process. Each elementary event determines a different sample path. Therefore if is such that the Lebesgue-Stieltjes integral is defined on each sample path (cadlag?), we can actually solve the above equation, and use it to calculate useful quantities. For instance, if represents the time when the probe reaches the moon ( if it misses), then we can calculate the expected distance from the target point , given a particular noise model:

Pretty cool!

The problem is, apparently in general the sample paths of stochastic processes are not nice, so Lebesgue-Stieltjes integration cannot be done. Then you need to break out the power tools

The eikonal equation is a non-linear PDE related to the least action principle and the Hamilton-Jacobi equations of mechanics:

One application of the equation is describing the propagation of a wavefront through a medium where the local speed is a function of location . In this case, the level sets of correspond to the wavefronts at different times; that is, the set is the wavefront at time . The derivation of this equation is straightforward: let represent the differential path of the light ray emitted from point at time , which reaches the new wavefront at time . This path is perpendicular to the wavefront it starts from, and has length , so

yields the eikonal equation.

Note that if identically and on the boundary of a region , then for outside , the solution to the eikonal equation measures the distance from to . At least, I think it should

It’s known that every square matrix is unitarily similar to an upper triangular matrix: . Prove, using linear algebra, that this decomposition cannot in general be computed with a finite number of basic matrix operations (mult, add).

This result is known, but I believe only as a corollary of a theorem in another branch of mathematics.

Apparently it’s true: Ted Haggard is a polesmoking hypocrite. What kind of twisted mind does it take to make a profession out of self-hatred? Or perhaps he never really believed anything he said?

Republicans are really starting to make homosexuals look bad… just not quite in the way their fundie base would like. Who I’d really like to see fall flat on his face is James Dobson– the self-righteous, smarmy pseudo-psychologist who advocates the ex-gay movement and patriarchal marriage, among other wrong-headed notions.

I started reading Shannon’s A Mathematical Theory of Communication today. Who knew a seminal paper could be this well-written? It is much better for gaining an intuitive view of the subject than the information theory text I picked up earlier. Also, just about every page contains some titillating connection to a field outside of information theory proper; for example, he brings into play the characteristic equation from finite differences, a graph theoretic reformulation of the necessary conditions for a process to be ergodic, and statements about how the amount of redundancy in a language determines the possibility of forming large crossword puzzles. Apparently English has just enough redundancy at 50% to make large crossword puzzles feasible.

Usually when we think of non-square systems of linear equations, we think of skinny full rank matrices: i.e., of systems of the form

One way of solving these systems is to use the (reduced) QR factorization, which decomposes into a matrix which has orthonormal columns, and an upper-triangular invertible matrix . Intuitively, the Q matrix is the result of applying the Gram-Schmidt orthonormalization process to the columns of , and combines the columns of to get back . There is also a full factorization, A= where is unitary, and is upper triangular. A full factorization can be obtained from a reduced one by completing the basis in , and adding zeros to the bottom of .

Something really cool, that I learnt today while doing my linear algebra homework, is that the QR factorization is useful for solving full-rank underdetermined systems as well. That is, suppose your problem is now

Then this has at least one solution, but there may be multiple ones. What if you’d like to select the solution with minimum Euclidean norm? The idea is that is a full-ranked skinny matrix, so has a QR decomposition: .

Then minimizing given is the same as minimizing it given , which is the same as minimizing it given (since , remember has orthonormal columns). But then is a projection, so the with minimum length that satisfies this equation is just . So the minimum length vectors that satisfies is simply . Pretty neat.

Today we started the second part of the applied functional analysis class: real analysis in . We jumped right in at Lebesgue outer measure, but considering that it’s on the syllabus, hopefully we’ll come back later after we develop Lebesgue theory to develop a more general theory of measure and integration. I like this approach: start with Lebesgue integration in , then do the abstract stuff. This is more effective than say Foland’s approach: do abstract integration, use it to establish Lebesgue integration in , and have an optional section on the theory in .

Now the notes from both parts of the course (1: functional analysis, 2: real analysis) are available– cf. the Lecture Notes section. They are comprehensive enough that I didn’t refer to the book at all for the first part, but I actually like the book for this part (Wheeden and Zygmund), so I’ll probably read along.