Log in

No account? Create an account
Something that's bugged me for a long time is this: How many paths,… - Notes from a Medium-Sized Island [entries|archive|friends|userinfo]

[ website | My Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

[Dec. 13th, 2016|09:36 pm]

Something that's bugged me for a long time is this:

How many paths, starting at the origin, taking N steps either up, down, left or right, end up at a particular place (x, y)? Ignoring the fact that x+y has to have the same parity as N, something that goes like e- k(x2 + y2), right? Just central-limit-type reasoning ought to suffice to see that. It's a nice plain isotropic Gaussian sitting at the origin... so there are about as many paths to (x, y) as there are to (x, y) rotated by some smallish angle θ, yeah? Doesn't this mean there ought to be a combinatorial function --- or, like, "approximate" function or something that "rotates" paths by angles less than 90o, even though the paths themselves are made of chunky up/down/left/right steps?

And yet I can't for the life of me hack up anything that seems to work. Somewhat annoying.

I tried staring at the fact that surely you can pretend |N>, |E>, |W>, |S> are states in a Hilbert space, and take the discrete rotation |N> → |E> → |S> → |W> → |N> and make a continous version of it by saying

|N> → f(t)|N> + f(t-1)|E> + f(t-2)|S> + f(t-3)|W>
f(t) = (1+eπit/2+eπit+e-πit/2)/4

but this doesn't seem to do anything nice when I make a big tensor product and ask what happens when some typical state, like, |NENSENSNWNWNWWE> gets rotated; there doesn't seem to be any tendency of the norm of its displacement to get preserved, even in expectation.

From: eub
2016-12-17 10:00 am (UTC)
Is the basic intuition like: a (x, y) can be "rotated a little" to an (x, y)' -- subject to grid quantization, sure, but for larger values you don't notice much. So why can't the path be rotated-a-little equally as well as the point can?

Simplicius says: Given a path, if you're willing to compute its sum, you can then tweak one or two steps of the path to get your (x,y)' instead.

But that's not satisfactory, because it doesn't seem like you should have to do that?

Simplicius says: wolog say we start with an E (1, 0) that we're rotating alpha c.c.w. The rotated (cos, sin) should be our expectation, and we want to give probabilities on NESW that yield that expectation. Can't do that by blending just E and N, obviously, that just gives a straight line interpolant that falls inside the circle. But we can do it by blending E, N, and E+N.

Is that allowed, to rotate E to EN sometimes? Because it does seem like you're going to have to.
(Reply) (Thread)
[User Picture]From: jcreed
2016-12-17 12:36 pm (UTC)
Right, it is critical, I think, to see it as the path rotating, not merely the point; what I'm trying to get a sense of is why the combinatorics of number-of-long-paths-to-(x,y) seems to have a rotation symmetry? Why is it the 2-norm that falls out, of all things?

Changing the length of the path as it rotates a little bit seems acceptable, as long as the length changes average out to nothing over the long run, and/or is negligible for long paths.
(Reply) (Parent) (Thread)
From: eub
2016-12-18 08:09 am (UTC)
My intuition is that is really isn't the paths who have this property, it's their sums. That the sequencing of the paths needs to be erased to create the effect.

Backing up -- to me the rotational symmetry is not the basic thing here, the Gaussianness is. (You can twiddle the setup to get a Gaussian ellipsoid.) In one dimension, the Gaussianness is born out of the 2^n paths at the point where you sum them down to get the (n choose k) line, where you diagonally scan the n-cube. The multidimensional Gaussian comes together in the usual way.

Of course this assumes some properties of Gaussians which you may be preferring to roll your own intuition of?
(Reply) (Parent) (Thread)