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..). 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$F4n/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}\$.