Timeline for The probability for a sequence to have small partial sums
Current License: CC BY-SA 2.5
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 28, 2011 at 14:26 | answer | added | Gil Kalai | timeline score: 7 | |
| Apr 23, 2010 at 7:11 | vote | accept | Gil Kalai | ||
| Apr 23, 2010 at 7:11 | history | bounty ended | Gil Kalai | ||
| Apr 23, 2010 at 7:11 | history | bounty started | Gil Kalai | ||
| Mar 3, 2010 at 2:51 | answer | added | Peter | timeline score: 2 | |
| Mar 3, 2010 at 0:40 | comment | added | Douglas Zare | The principal eigenvalue for a path with 2t+1 vertices is 2 cos pi/(2t+2). | |
| Mar 3, 2010 at 0:31 | answer | added | Douglas Zare | timeline score: 12 | |
| Mar 2, 2010 at 21:05 | comment | added | Kevin P. Costello | 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... | |
| Mar 2, 2010 at 21:02 | comment | added | Gil Kalai | Hmm, this rings a bell, I believe you may be right and the reflection principle, as well as the asnwer for Brownian motion are relevant. On the other hand, I do not work to work it out myself but rather to learn what the answer is, and where can I find it, and in the polymath5 spirit would rather ask it on a "public" forum. | |
| Mar 2, 2010 at 20:46 | comment | added | Paul Yuryev | 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? | |
| Mar 2, 2010 at 20:24 | history | edited | Gil Kalai | CC BY-SA 2.5 |
deleted 2 characters in body
|
| Mar 2, 2010 at 19:30 | comment | added | Gil Kalai | 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. | |
| Mar 2, 2010 at 18:58 | comment | added | Bill Johnson | 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? | |
| Mar 2, 2010 at 18:36 | history | asked | Gil Kalai | CC BY-SA 2.5 |