Timeline for Random sequence of integers in $\{1, 2, \dots, n \}$ which is "everywhere probably increasing" - how long can it be?
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 20, 2016 at 20:06 | history | edited | Will Sawin | CC BY-SA 3.0 |
deleted 128 characters in body
|
| May 12, 2015 at 2:58 | comment | added | Terry Tao | Nice! I had considered using a Fourier expansion to try to diagonalise the $a < b$ constraint, but dropped the idea after seeing the $1 \leq a$ and $b \leq n$ constraints also, though the neat "carrying the 1" decomposition deals with these constraints quite elegantly. | |
| May 12, 2015 at 0:02 | comment | added | Will Sawin | @TerryTao Sometimes the best constants in the continuous version are computable explicitly. : ) | |
| May 11, 2015 at 19:46 | history | edited | Will Sawin | CC BY-SA 3.0 |
added 1818 characters in body
|
| May 11, 2015 at 16:59 | comment | added | Terry Tao | In practice, dyadic arguments tend to be non-optimal by a factor of roughly 2 or so, but they have the advantage that the best constants for the dyadic version are often computable explicitly, even if they don't match the best constants for the continuous problem. Unfortunately most of the tools in my bag of tricks aren't geared towards extracting optimal constants for continuous problems... | |
| May 11, 2015 at 16:26 | comment | added | Will Sawin | The problem I'm referring to is $\max ( \sum_{1 \leq i < j \leq n } v_i \cdot w_j)$ subject to $|v_i|=|w_i|$, $v_i \cdot v_j = w_i \cdot w_j=0$ for $i \neq j$ and $\sum_{i=1}^n |v_i|^2=1$. | |
| May 11, 2015 at 16:22 | comment | added | Will Sawin | @TerryTao Do you think the dyadic approach is optimal? Using the usual Hilbert inequality, you can reduce the problem to a linear algebra optimization problem where, for instance, a 3-adic or 4-adic decomposition should be more efficient than 2-adic. I haven't done the exact calculations but in the case where $|\{j|d_j=d\}|$ is constant I can beat two, and that naively seems like the worst case. (By the way, it's easy to make mistakes with this kind of constant. I think it was $\pi/(2 \log 2)$ before, not $\pi \log 2$. That's still greater than )$2$, though.) | |
| May 11, 2015 at 16:03 | comment | added | Terry Tao | It may be that a Bellman function technique (yet another tool from the harmonic analysis toolbox!) may be useful in reducing the constant further, particularly if one is able to phrase the problem in a suitably "dyadic" formulation. | |
| May 11, 2015 at 16:00 | comment | added | Terry Tao | If one uses the dyadic Hilbert inequality $\sum_{I,J \hbox{ adjacent}} \sum_{i \in I} \sum_{j \in J} \frac{c_i d_j - c_j d_i}{|I|} \leq 2 (\sum_i c_i^2)^{1/2} (\sum_j d_j^2)^{1/2}$ (easiest to prove using the Haar wavelet basis) it appears that the constant $\pi \log 2$ can be reduced slightly to 2. | |
| May 11, 2015 at 14:33 | history | edited | Will Sawin | CC BY-SA 3.0 |
deleted 550 characters in body
|
| May 11, 2015 at 14:12 | comment | added | Will Sawin | @LinusHamilton By the way, I think I know how to get up to $3/4$. I don't want to write the details right now, but the idea is that in the first sequence you add a small independent random number to each $d_i$. This means the probability that $d_j>d_i$ starts at just under $1/2$ and increases linearly to $1$. By equally averaging the two strategies, we can get a probability just under $3/4$. This, plus Terry Tao's bound, suggests to me that the answer might be $n^{1/(2r-1)}$ exactly. | |
| May 11, 2015 at 14:04 | comment | added | Linus Hamilton | Ah, I see what's happening now. So $O(n^{1/r})$ is indeed wrong. Thanks, good example! | |
| May 11, 2015 at 13:39 | comment | added | Will Sawin | @LinusHamilton That's a typo. I meant to send $l$ to $|infty$, not $0$. | |
| May 11, 2015 at 7:03 | comment | added | Linus Hamilton | I don't understand how this can work if $l \rightarrow 0$. (I'm assuming your statement that $l$ is a natural number was a typo, since you need to let $l \rightarrow 0$ at the end.) In particular if $l$ is, say, $1/1000$, then the "gradient" of the sequence, $\alpha$, will be small, so two adjacent terms $d_i,d_{i+1}$ will be the same with large probability. In particular, when $l$ is small, the bound for the second strategy $max(1-\frac{l}{2}\frac{j-i}{n}, 1/2)-\frac{1}{l}$ has a whole $-\frac{1}{l}$ term that seems to disappear. | |
| May 11, 2015 at 4:13 | history | edited | Will Sawin | CC BY-SA 3.0 |
added 185 characters in body
|
| May 11, 2015 at 3:58 | history | answered | Will Sawin | CC BY-SA 3.0 |