show/hide this revision's text 2 deleted 2 characters in body

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 is 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.
show/hide this revision's text 1

The probability for a sequence to have small partial sums

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