The probability for a sequence to have small partial sums - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T09:37:30Z http://mathoverflow.net/feeds/question/16892 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/16892/the-probability-for-a-sequence-to-have-small-partial-sums The probability for a sequence to have small partial sums Gil Kalai 2010-03-02T18:36:22Z 2011-07-28T14:26:01Z <h1>The question</h1> <p>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 </p> <blockquote> <p>$|a_1+a_2+\dots a_k| \le t$, for every $k$, $1 \le k\le n$. </p> </blockquote> <p>(In other words, the probability that a random sequence will satisfy the above relation.) </p> <p>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).</p> <h2>variations</h2> <p>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. </p> <p>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. </p> <h1>Motivation</h1> <p>This question is relevant to the recent collective effort (<a href="http://gowers.wordpress.com/2010/03/02/edp10-a-new-and-very-promising-approach/" rel="nofollow">polymath5</a>) regarding the Erdos Discrepancy Problem (EDP). It particular it is relevant to a <a href="http://gowers.wordpress.com/2010/02/19/edp8-what-next/#comment-6278" rel="nofollow">probabilistic heuristic</a> regarding what the answer to EDP, and to several related questions, should be. </p> <p>It is also relevant to certain probabilistic approaches towards construction of sequences with low discrepancy.</p> <h1>Expectation</h1> <p>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&lt;2$ but I would like to know the dependence of c_t on t.</p> http://mathoverflow.net/questions/16892/the-probability-for-a-sequence-to-have-small-partial-sums/16940#16940 Answer by Douglas Zare for The probability for a sequence to have small partial sums Douglas Zare 2010-03-03T00:31:23Z 2010-03-03T13:03:37Z <p>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 </p> <p>$$\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).$$</p> <p>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</p> <p>$$\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).$$</p> <p>The exact count of paths staying in $[-t,t]$ is a sum of signed binomial coefficients.</p> <p>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$.</p> <p>The number of paths which never leave $[-t,t]$ from $0$ to $i \in [-t,t]$ with $n \equiv i ~\mod 2$ is </p> <p>$$\sum_{j\in \mathbb Z} (-1)^j {n\choose (n +i)/2 + j(t+1)}$$</p> <p>by the reflection principle applied to the group of isometries of $\mathbb R$ generated by reflecting about $t+1$ and $-t-1$.</p> <p>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. </p> <p>For example, for $n=100, t=2,$ the number of paths is </p> <p>$$... +{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} - ...$$</p> <p>For $n=101, t=2,$ the number of paths is </p> <p>$$... +{101\choose 44} + {101\choose 45} - {101\choose 47} - {101 \choose 48} + {101\choose 50} + {101\choose 51} - {101\choose 53} - {101\choose 54} + ...$$ </p> <p>These can be summed using the techniques in the answers to the <a href="http://mathoverflow.net/questions/16187/binomial-distribution-parity/" rel="nofollow">Binomial distribution parity question</a>.</p> <p>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 </p> <p>$$C \prod_{t \le t_{max}} (2 \cos \frac{\pi}{2t+2})^{n_t}$$</p> <p>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}$.</p> <p>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.</p> http://mathoverflow.net/questions/16892/the-probability-for-a-sequence-to-have-small-partial-sums/16945#16945 Answer by Peter for The probability for a sequence to have small partial sums Peter 2010-03-03T02:51:31Z 2010-03-03T02:57:57Z <p>As a lazy heuristic, one can consider the following construction.</p> <p>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?</p> <p>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}$.</p> <p>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..).</p> http://mathoverflow.net/questions/16892/the-probability-for-a-sequence-to-have-small-partial-sums/71492#71492 Answer by Gil Kalai for The probability for a sequence to have small partial sums Gil Kalai 2011-07-28T14:26:01Z 2011-07-28T14:26:01Z <p>Here is a useful supplement and references to the existing answers. I asked Yuval Peres a few days ago the question formulated as follows:</p> <blockquote> <p>What is the probability that the simple random walk of n steps will be confined to the interval $[-K,K]$?</p> </blockquote> <p>Yuval's answer a few hours later was: </p> <blockquote> <p>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})$.</p> </blockquote> <p>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$.</p>