### (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

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

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.

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.