The probability for a sequence to have small partial sums - MathOverflow

The probability for a sequence to have small partial sums

2010-03-02T18:36:22Z

The question

Let $a_1,a_2,\dots,a_n$ be a sequence whose entries are +1 or -1. Let t be a parameter. My question is to give an estimate for the number of such sequences so that

$|a_1+a_2+\dots a_k| \le t$, for every $k$, $1 \le k\le n$.

(In other words, the probability that a random sequence will satisfy the above relation.)

I am especially interested in this probability when t is small. Either a constant, or slowly growing (say, it behaves like (log n)^s for some real number s, or slower).

variations

1) I would also like to know what is the situation if you demand that the average value of |a_1+a_2+\dots a_k| is smaller than t, rather than the maximum value.

2) If there are more delicate estimates for the case that t itself is a function of k e.g. t itself grows as (log n)^s I would be very interested as well.

Motivation

This question is relevant to the recent collective effort (polymath5) regarding the Erdos Discrepancy Problem (EDP). It particular it is relevant to a probabilistic heuristic regarding what the answer to EDP, and to several related questions, should be.

It is also relevant to certain probabilistic approaches towards construction of sequences with low discrepancy.

Expectation

I would expect that the answers to the questions above are known. But they are not known to me. It is easy to be convinced, for example, that when t is bounded the number of such sequences is $c_t^{-n}$, for $c_t<2$ but I would like to know the dependence of c_t on t.

Answer by Douglas Zare for The probability for a sequence to have small partial sums

2010-03-03T00:31:23Z

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 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 $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$ 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,$ 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,$ 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.

A lot more can be said when $t$ varies, but the answers are more complicated. For $t$ slowly increasing, as $c\sqrt[3]n$, there is enough time for the distribution to stabilize (for each parity) at a given value of $t$, since the ratio between the magnitudes of the largest two eigenvalues and 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. 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 the 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 may tell you when a positive 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.

Answer by Peter for The probability for a sequence to have small partial sums

2010-03-03T02:51:31Z

As a lazy heuristic, one can consider the following construction.

Consider the following operation $F$ on sequences. Given a sequence $S$, we identify in $S$ the first place $q$ where the partial sum leaves $\pm t$. We identify the last place $r$ preceding $q$ in which it remains within $\pm t/2$. Then we let $F(S)$ be the sequence obtained from $S$ by swapping the signs of all elements from the $r$th place. Of course, if we apply $F$ sufficiently many times to any sequence we will obtain a sequence whose partial sums are bounded in $\pm t$. The question is how many times must we apply $F$ to a typical sequence?

We expect that for a random $S$ the value of $q-r$ is about ${t^2}/4$. Furthermore, by definition, if $q$ is the place at which the partial sums of $F$ first leave $\pm t$, and $q'$ is the first place at which the partial sums of $F(S)$ leave $\pm t$, then the last place $r'$ preceding $q'$ in which the partial sums of $F(S)$ remain within $\pm t/2$ satisfies $r'\geq q$. It follows that we expect to apply $F$ about $4n/t^2$ times to a randomly generated sequence $S$ in order to obtain a sequence whose partial sums are bounded within $\pm t$. It follows that we should expect that the probability that a random sequence has partial sums bounded by $\pm t$ is about $2^{-4n/t^2}$.

It should not be so hard to turn this into a good argument that the probability is $2^{-c_tn}$ for some $c_t$ growing roughly like $t^{-2}$ (perhaps with some log factors..).

Answer by Gil Kalai for The probability for a sequence to have small partial sums

2011-07-28T14:26:01Z

Here is a useful supplement and references to the existing answers. I asked Yuval Peres a few days ago the question formulated as follows:

What is the probability that the simple random walk of n steps will be confined to the interval $[-K,K]$?

Yuval's answer a few hours later was:

The confinement probability in [-K,K] decays up to a constant like $\exp(-cn/K^2)$ where $c$ is known: it is $\pi/2$. This is classical and you can find it e.g. in Feller volume 2 or in Spitzer’s book. This holds for all $K=o(\sqrt{n})$.

I was especially interested (for polymath5 purposes) in the value of $K=K(n)$ for which this probability is $2^{-n/\log n}$. The answer to this specific query is thus $K=C\sqrt{\log n}$ for a suitable $C$.