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

-
Gil, let $S_k = \sum_{j=1}^k a_j$, where the $a_j$ are symmetric IID $-1, 1$ valued RV. Then $P[ \max_{1\le k \le n} |S_k| > t] \le 2 P[|S_n| >t]$ and $n^{-1/2} S_n$ is approximately $N(0,1)$. Is this insufficient for what you need? –  Bill Johnson Mar 2 '10 at 18:58
Dear Bill, I dont think so. the probability that S_n is bounded (say by 2) is c/sqrt n but the probability that all S_ks are bounded is exponentially small. –  Gil Kalai Mar 2 '10 at 19:30
For Brownian motion, the distribution of the maximum is found in closed form via reflection principle. For symmetric random walk, can't you do the same? –  Paul Yuryev Mar 2 '10 at 20:46
To avoid parity issues, let's assume n even (which we'll view as taking 2 steps at a time), and t is odd. We're then effectively taking a random walk on {-t+1, -t+3, \dots, -2, 0, 2, \dots, t-1\} where x->x is given weight 2 and x->x+/-2 are each given weight 1. I believe what then corresponds to your c_t^2 would be the spectral norm of the tridiagonal matrix A having all diagonal entries 2, all entries adjacent to the main diagonal 1, and all other entries 0. Alternatively, it's 2+||P_t||, where P_t is the adjacency matrix of the length t path. Surely this is a known quantity... –  Kevin P. Costello Mar 2 '10 at 21:05
The principal eigenvalue for a path with 2t+1 vertices is 2 cos pi/(2t+2). –  Douglas Zare Mar 3 '10 at 0:40

## 3 Answers

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.

-
Great ! thanks a lot. I thik the relevant cases for discrapancy heuristics are when t grows much smaller than n. For example, we would like to understand the orecise growth of t so that the probability will behave like exp (logn/n) –  Gil Kalai Mar 3 '10 at 13:33

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

-

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..).

-