July 23rd, 2011

beartato phd

(no subject)

I keep mulling over in an blunt sort of way the mystery of random walks and the geometric idea of rotation.

I can't help but want to recapitulate a really fast and cute suggestive "proof" of a special case of the central limit theorem.

Suppose I do a random walk on the integers. I start at 0 and I take 2n random hops left or right. What are the odds I end up at location 2x? Well, of those 2n random hops, n+x of them would have to be to the right. For that would leave n-x to the left, for a net of (n+x)-(n-x) = 2x as desired. So there's (2n choose x+n) paths of length 2n that move 2x to the right.

How can we estimate how many of these there are? Set f(x) = (2n choose x+n) = 2n!/(n+x)!(n-x)! and notice what happens if we increment x by one. The ratio f(x+1)/f(x) simplifies down to just (n-x)/(n+x+1). And if n is big compared to x, and both n,x are big compared to 1, this is something like (n-x)/(n+x) = 1 - 2x/(n+x) which is approximately 1-2x/n. Look at
f(x+1)/f(x) = 1-2x/n
and take the log of both sides. On the left we get ln f(x+1) - ln f(x). Thinking of 1 as the h in the definition of derivative, this is approximately (d/dx)(ln f) = f'(x)/f(x). On the right, use the fact that ln(x) has derivative 1 at x=1 to approximate it as -2x/n. So now we have
f'(x)/f(x) = -2x/n
This is easy to solve as a separable diffeq, like
df/f = -2x/n dx
and get
f = C e^(-x^2/n)

Blam! There's your Gaussian distribution. It comes straight out of the combinatorics of discrete random walks. That's far from a proof of the central limit theorem (or even that the binomial distribution converges to the Gaussian!) but it shows how you might guess it. And the really important mysterious thing to me --- I may have mentioned this before --- is the fact that two or more independent walks seem to magically create the idea of the 2-norm just by properties of the exponential:
e^(-x^2/n)e^(-y^2/n) = e^(-(x^2 + y^2)/n)
And the 2-norm is what makes Euclidean space feel so warm and fuzzy and... Euclidean. Rotations and reflections spring right out of it as precisely the things that preserve the 2-norm. And the reason I say "central limit theorem" is that it's interesting that no matter what your lattice is that you start with, you inevitably get some kind of Gaussian (subject to technical conditions, etc.) A huge family of statistical systems just want to be Gaussian!

And this same sort of magic is why I find the Feynman checkerboard model so fascinating, since it seems to conjure the Minkowski metric (t^2 - x^2) out of thin air --- or, rather, out of a simple model. I wonder if there's any kind of corresponding 'central limit theorem' for a nice class of local, unitary evolution functions that always tend asymptotically toward metrics like t^2 - (x^2 + y^2 + ...)?

Sadly all of the poking around I've done about higher-dimensional generalizations of the Checkerboard model specifically suggests that (a) they have been studied fairly intensely and (b) I get the impression they don't really work so well.

Separately, come to think of it, I guess I don't fault Wolfram for being so fascinated by discrete models in NKOS --- they really are very cute! --- only for making it sound like they haven't always been a thread running through mathematics, statistics, physics, etc.