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

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

Generate a sequence randomly until the partial sum reaches the $\pm t$ limit. Then immediately return to 0 (in t steps). Repeat until n elements are generated.

We expect to reach the limit after about $t^2$ steps, so we perform about $n/t^2$ return operations. Very little is 'lost' outside these return operations, which take up about $n/t$ sequence elements. So we should hope that the probability that a random sequence has partial sums bounded by $\pm t$ is at least $2^{-n/t}$.

On the other hand, we have an alternative 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$. {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 at most about $2^{-4n/t^2}$.

It seems likely that the upper bound heuristic is much closer to the truth than the lower bound. In any case, it should not be so hard to turn this into a good argument that the probability is $2^{-c_t n}$ 2^{-c_tn}$ for some $t^{-2}\leq c_t\leq t^{-1}$c_t$ growing roughly like $t^{-2}$ (perhaps with some log factors..).
show/hide this revision's text 1

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

Generate a sequence randomly until the partial sum reaches the $\pm t$ limit. Then immediately return to 0 (in t steps). Repeat until n elements are generated.

We expect to reach the limit after about $t^2$ steps, so we perform about $n/t^2$ return operations. Very little is 'lost' outside these return operations, which take up about $n/t$ sequence elements. So we should hope that the probability that a random sequence has partial sums bounded by $\pm t$ is at least $2^{-n/t}$.

On the other hand, we have an alternative 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$ $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 at most $2^{-4n/t^2}$.

It seems likely that the upper bound heuristic is much closer to the truth than the lower bound. In any case, it should not be hard to turn this into a good argument that the probability is $2^{-c_t n}$ for some $t^{-2}\leq c_t\leq t^{-1}$.