Revisions - MathOverflow

Return to Answer

Added more information when t varies.

view source

edited Mar 3 2010 at 13:03

Douglas Zare
13k●3●36●58

For example, for $n=100, t=2, i=50,$ t=2,$ the number of paths is

For $n=101, t=2, i=51,$ t=2,$ the number of paths is

Now for some speculation: I believe a

A lot more can be said when $t$ varies, but the answers should be are more complicated. For $t$ slowly increasing, it may help to know how the eigenvectors change as you increment $t$. The geometry of this change should tell you how long you need to keep $t$ constant c\sqrt[3]n$, there is enough time for the distribution to stabilize (for a fixed each parity) at a given value of $n$), t$, since the ratio between the magnitudes of the largest two eigenvalues and what constant factors you the magnitudes of the next two is about $1+c/t^2$, and the principal eigenvectors have a small $L^1$ distance for adjacent values of $t$. You should pick up a constant factor for each transition.

You may want to use stochastic differential equations to determine In other words, the number of paths when you spend at least $n_t \gt c t^2$ steps at a given $t$ should be

$$C \prod_{t \le t_{max}} (2 \cos \frac{\pi}{2t+2})^{n_t}$$

where $C$ is between some functions $f_{lower}(t_{max}) \lt C \lt f_{upper}(t_{max})$ which does not depend on the values of $n_t$. I don't think the $n_t \gt c t^2$ condition is sharp for this behavior. Something like $n_t \gt c t^2/\log t$ should work, too. The geometry of Brownian motion with similar boundariesthe eigenvectors for adjacent values of $t$ lets you estimate $f_{lower}$ and $f_{upper}$.

For $t$ more rapidly increasing, different behaviors occur. By the law of the iterated logarithm, if $t$ increases as $t(n) = \sqrt {(2-\epsilon) n \log\log n},$ random paths will almost surely violate the constraint. I think there are precise versions of the law of the iterated logarithm which should be may tell you when a good guidepositive proportion of random paths do not violate the constraint. I would guess that if $t(n) = \sqrt{(2+\epsilon) n \log\log n}$ then a positive percentage of random paths won't violate the constraint.

Added eignevectors.

view source

edited Mar 3 2010 at 2:16

Douglas Zare
13k●3●36●58

For $t$ fixed, the count is proportional to $\lambda^n$, where $\lambda = 2 \cos \frac\pi{2t+2}$ is the principal eigenvalue of the adjacency matrix of the path with $2t+1$ vertices. The all-positive (Perron-Frobenius) eigenvector corresponding to $\lambda$ is

$$\bigg(\sin \frac{\pi}{2t+2}, \sin \frac{2\pi}{2t+2},\sin \frac{2\pi}{2t+2},\dots,sin \frac{(2t+1)\pi}{2t+2}\bigg).$$

Since $-\lambda$ is also an eigenvalue, the stable behavior of the distribution of endpoints of paths which stay in $[-t,t]$ is an oscillation between the odd entries

$$\bigg(\sin \frac{\pi}{2t+2}, 0,\sin \frac{3\pi}{2t+2},0,\dots,\sin \frac{(2t-1)\pi}{2t+2},0,\sin \frac{(2t+1)\pi}{2t+2}\bigg).$$ and even entries $$\bigg(0,\sin \frac{2\pi}{2t+2}, 0,\sin \frac{4\pi}{2t+2},0,\cdots ,0,\sin \frac{2t\pi}{2t+2},0\bigg).$$

The exact value count of paths staying in $[-t,t]$ is a sum of signed binomial coefficients.

The number of paths from $0$ to $i$ is 0 if the parity of $i$ disagrees with $n$, n \not \equiv i ~\mod 2$, and $n \choose (n\pm i)/2$ when $n \equiv i ~\mod 2$.

The number of paths which never leave $[-t,t]$ from $0$ to $i \in [-t,t]$ with $n \equiv i ~\mod 2$ which never leave $[-t,t]$ is

$$ \sum_{j\in \mathbb Z} (-1)^j {n\choose (n +i)/2 + j(t+1)}$$

by the reflection principle applied to the group of isometries of $\mathbb R$ generated by reflecting about $t+1$ and $-t-1$.

If you sum over all $i \in [-t,t]$, then when $n$ is even, you get a signed sum of binomial coefficients with $t+1$ positive signs in a row alternating with $t+1$ negative signs in a row. If $n$ is odd, then you get $t$ positive signs in a row, skip a term (give it a coefficient of $0$ instead of $\pm 1$), then $t$ negative signs in a row, skip a term, etc.

For example, for $n=100, t=2, i=50,$ the number of paths is

$$ ... +{100\choose 43} + {100\choose 44} + {100 \choose 45} - {100 \choose 46} - {100 \choose 47} - {100\choose 48} + {100\choose 49} + {100 \choose 50} + {100\choose 51} - ...$$

For $n=101, t=2, i=51,$ the number of paths is

$$ ... +{101\choose 44} + {101\choose 45} - {101\choose 47} - {101 \choose 48} + {101\choose 50} + {101\choose 51} - {101\choose 53} - {101\choose 54} + ...$$

These can be summed using the techniques in the answers to the Binomial distribution parity question.

Now for some speculation. : I believe a lot more can be said when $t$ varies, but the answers should be more complicated. For $t$ slowly increasing, it may help to know how the eigenvectors change as you increment $t$. The geometry of this change should tell you how long you need to keep $t$ constant for the distribution to stabilize (for a fixed parity of $n$), and what constant factors you pick up.

You may want to use stochastic differential equations to determine the behavior of Brownian motion with similar boundaries, which should be a good guide.

Post Undeleted by Douglas Zare

occurred Mar 3 2010 at 0:43

Fixed fencepost error.; deleted 1 characters in body

view source

edited Mar 3 2010 at 0:42

Douglas Zare
13k●3●36●58

For $t$ fixed, the count is proportional to $\lambda^n$, where $\lambda = 2 \cos \frac\pi{2t+1}$ frac\pi{2t+2}$ is the principal eigenvalue of the adjacency matrix of the path with $2t$ edges2t+1$ vertices.

The exact value is a sum of signed binomial coefficients.

The number of paths from $0$ to $i$ is 0 if the parity of $i$ disagrees with $n$, and $n \choose (n\pm i)/2$ when $n \equiv i ~\mod 2$.

The number of paths from $0$ to $i \in [-t,t]$ with $n \equiv i ~\mod 2$ which never leave $[-t,t]$ is

$$ \sum_{j\in \mathbb Z} (-1)^j {n\choose (n +i)/2 + j(t+1)}$$

by the reflection principle applied to the group of reflections isometries of $\mathbb R$ generated by reflecting about $t+1$ and $-t-1$.

For example, for $n=100, t=2, i=50,$ the number of paths is

$$ ... +{100\choose 43} + {100\choose 44} + {100 \choose 45} - {100 \choose 46} - {100 \choose 47} - {100\choose 48} + {100\choose 49} + {100 \choose 50} + {100\choose 51} - ...$$

For $n=101, t=2, i=51,$ the number of paths is

$$ ... +{101\choose 44} + {101\choose 45} - {101\choose 47} - {101 \choose 48} + {101\choose 50} + {101\choose 51} - {101\choose 53} - {101\choose 54} + ...$$

These can be summed using the techniques in the answers to the Binomial distribution parity question.

Now for some speculation. I believe a lot more can be said when $t$ varies, but the answers should be more complicated. For $t$ slowly increasing, it may help to know how the eigenvectors change as you increment $t$. The geometry of this change should tell you how long you need to keep $t$ constant for the distribution to stabilize (for a fixed parity of $n$), and what constant factors you pick up.

You may want to use stochastic differential equations to determine the behavior of Brownian motion with similar boundaries, which should be a good guide.

Post Deleted by Douglas Zare

occurred Mar 3 2010 at 0:36

view source

answered Mar 3 2010 at 0:31

Douglas Zare
13k●3●36●58

For $t$ fixed, the count is proportional to $\lambda^n$, where $\lambda = 2 \cos \frac\pi{2t+1}$ is the principal eigenvalue of the adjacency matrix of the path with $2t$ edges.

The exact value is a sum of signed binomial coefficients.

The number of paths from $0$ to $i$ is 0 if the parity of $i$ disagrees with $n$, and $n \choose (n\pm i)/2$ when $n \equiv i ~\mod 2$.

The number of paths from $0$ to $i \in [-t,t]$ with $n \equiv i ~\mod 2$ which never leave $[-t,t]$ is

$$ \sum_{j\in \mathbb Z} (-1)^j {n\choose (n +i)/2 + j(t+1)}$$

by the reflection principle applied to the group of reflections of $\mathbb R$ generated by reflecting about $t+1$ and $-t-1$.

For example, for $n=100, t=2, i=50,$ the number of paths is

$$ ... +{100\choose 43} + {100\choose 44} + {100 \choose 45} - {100 \choose 46} - {100 \choose 47} - {100\choose 48} + {100\choose 49} + {100 \choose 50} + {100\choose 51} - ...$$

For $n=101, t=2, i=51,$ the number of paths is

$$ ... +{101\choose 44} + {101\choose 45} - {101\choose 47} - {101 \choose 48} + {101\choose 50} + {101\choose 51} - {101\choose 53} - {101\choose 54} + ...$$

These can be summed using the techniques in the answers to the Binomial distribution parity question.

You may want to use stochastic differential equations to determine the behavior of Brownian motion with similar boundaries, which should be a good guide.