35
$\begingroup$

Let $D=(d_1,d_2,\dots,d_k)$ be a sequence of correlated random variables. $D$ is "everywhere $r$-probably increasing" if the event $d_j > d_i$ has probability $\geq r$ for all $j > i$.

Fix $r \geq 1/2$. How long can a random sequence of integers in $\{1, 2, \dots, n\}$ be, and still be $r$-probably increasing?

Perhaps surprisingly, the answer is not $O(n)$. For example, the random sequence which is $(1,1,1,2,2,2,3,3,3)$ with 50% chance and $(1,2,3,1,2,3,1,2,3)$ with 50% chance is everywhere $1/2$-probably increasing. It's easy to generalize this to get, when $r=1/2$, a sequence of length $n^2$. With a bit more work, when $r=a/b$, one can get a sequence of length $\sim n^{b/a}$.

I conjecture the answer is $O(n^{1/r})$. But I can't find any relevant papers, and frustratingly, I can't even prove any upper bound for any $r<1$.

$\endgroup$
  • 3
    $\begingroup$ If $r$ is greater than $1-1/n$, you can't have a sequence longer than $n$ by the union bound, since you would get a positive probability that $d_1 \lt d_2 \lt ... \lt d_n \lt d_{n+1}$, which is impossible. $\endgroup$ – Douglas Zare May 10 '15 at 16:44
  • 1
    $\begingroup$ My answer now has matching upper and lower bounds, estabilishing $n^{1/(2r-1)+o(1)}$ as the best possible. $\endgroup$ – Will Sawin May 11 '15 at 19:47
30
$\begingroup$

I adapt an argument from this blog post of mine, exploiting the $\ell^2$ boundedness of the discrete Hilbert transform (i.e. Hilbert's inequality), to obtain an exponential upper bound. I don't see any obvious way to improve this to a polynomial bound (EDIT: A Whitney decomposition seems to do the trick, see below). The argument is inspired by a stability result of Hrushovski (based on de Finetti's theorem) which shows that some finite bound is possible, although it is not easy to extract a quantitative bound from Hrushovski's argument (and if one did, it would surely be worse than exponential); see Proposition 2.25 of that paper.

Suppose that ${\bf P}(d_j > d_i) \geq r$ for some $r>1/2$ and all $1 \le i < j \leq k$. Then of course $${\bf P}( d_j > d_i) - {\bf P}( d_j < d_i ) \geq 2r-1$$ for all $1 \le i < j \le k$. We expand this as $$ \sum_{1 \leq a < b \leq n} {\bf P}( d_j = b \wedge d_i = a ) - {\bf P}( d_j = a \wedge d_i = b ) \geq 2r-1.$$ Multiply by the positive quantity $\frac{1}{j-i}$ and sum to conclude that $$ \sum_{1 \leq a < b \leq n} \sum_{1 \leq i < j \leq k} \frac{1}{j-i} [{\bf P}( d_j = b \wedge d_i = a ) - {\bf P}( d_j = a \wedge d_i = b )] \gg (2r-1) k \log k \qquad (1).$$ The LHS can be rearranged as $$ \sum_{1 \leq a < b \leq n} \sum_{1 \leq i,j \leq k: i \neq j} \frac{1}{j-i} {\bf P}(d_j = b \wedge d_i = a ) $$ and rearranged further as $$ {\bf E} \sum_{1 \leq a < b \leq n} \sum_{1 \leq i,j \leq k: i \neq j} \frac{1}{j-i} 1_{d_j = b} 1_{d_i = a}.$$ By Hilbert's inequality, we have $$ \sum_{1 \leq i,j \leq k: i \neq j} \frac{1}{j-i} 1_{d_j = b} 1_{d_i = a} \ll (\sum_{1 \leq j \leq k} 1_{d_j=b})^{1/2} (\sum_{1 \leq i \leq k} 1_{d_i=a})^{1/2}$$ and $$ {\bf E} \sum_{1 \leq a < b \leq n} \sum_{1 \leq j \leq k} 1_{d_j=b}, {\bf E} \sum_{1 \leq a < b \leq n} \sum_{1 \leq i \leq k} 1_{d_i=a} \ll k n $$ so by Cauchy-Schwarz $$ {\bf E} \sum_{1 \leq a < b \leq n} \sum_{1 \leq i,j \leq k: i \neq j} \frac{1}{j-i} 1_{d_j = b} 1_{d_i = a} \ll kn $$ and hence $$ kn \gg (2r-1) k \log k$$ leading to the exponential upper bound $$ k \ll \exp( O( \frac{n}{2r-1} ) ).$$

EDIT: Looks like one can improve this to the polynomial bound $k \ll n^{O(1/(2r-1))}$ using the following standard Whitney decomposition trick (used for instance to prove the Rademacher-Menshov theorem or the Christ-Kiselev lemma). Firstly, without loss of generality we may take $n$ to be a power of 2. Then observe that if $1 \leq a < b \leq n$, then there is a unique pair of distinct dyadic intervals $I,J$ in $\{1,\dots,n\}$ with the same parent such that $a \in I$ and $b \in J$; let's call such pairs "adjacent". As such, the LHS of (1) can now be rearranged as

$$ {\bf E}\sum_{2^l < n} \sum_{I,J: |I|=|J|=2^l, \hbox{adjacent}} \sum_{1 \leq i,j \leq k: i \neq j} \frac{1}{j-i} 1_J(d_j) 1_I(d_i).$$

We apply Hilbert's inequality to bound this by $$ \pi {\bf E} \sum_{2^l < n} \sum_{I,J: |I|=|J|=2^l, \hbox{adjacent}} (\sum_j 1_J(d_j))^{1/2} (\sum_i 1_I(d_i))^{1/2}$$ which by Cauchy-Schwarz and the disjointness of the $I,J$ can be bounded by $$ \pi \sum_{2^l < n} k^{1/2} k^{1/2} \ll k \log n$$ leading to $$ k \log n \gg (2r-1) k \log k $$ and thus $k \ll n^{O(1/(2r-1))}$.

$\endgroup$
  • $\begingroup$ Slick argument! It's nice to have a bound. For all the examples I have, Hilbert's inequality introduces almost all of the exponential slack; especially when $a$ is not close to $b$. I'm trying to think of improvements. $\endgroup$ – Linus Hamilton May 10 '15 at 19:27
  • $\begingroup$ I think by using Hilbert's inequality more efficiently one can recover a polynomial bound; see edit. $\endgroup$ – Terry Tao May 10 '15 at 20:00
  • $\begingroup$ Wow! Both Hilbert's inequality and the Whitney decomposition are new tricks for my toolbox. I am interested in bringing down the exponent, as I have numerical evidence it should be $1/r$, so I'll try various tricks (perhaps summing three terms $a<b<c$, $i<j<l$ or more instead of two?) to chisel away at this proof. I'm a lot more optimistic now than I was when I posted this. $\endgroup$ – Linus Hamilton May 10 '15 at 20:35
  • 3
    $\begingroup$ If the $d_i$ are drawn iid from $\{1,\dots,n\}$, then $d_i \geq d_j$ with probability $1/2 - 1/2n$, regardless of how large $k$ is. So one gets no bound on $k$ in the regime $r < 1/2 - 1/2n$. It looks like my argument here can stretch to cover most of the regime $r \geq 1/2 - 1/2n$, by using Cauchy-Schwarz to get a nontrivial lower bound on the probability that $d_i=d_j$ on average (in the above argument this is just lower bounded by zero). $\endgroup$ – Terry Tao May 11 '15 at 0:22
22
$\begingroup$

Using Fourier analysis in the $d$ variable, we can get the optimal upper bound. As in Tao's argument, if there is a distribution of sequences for which each pair is $r$-probably increasing, there must be a single sequence $d_i$ : such that:

$$\sum_{1\leq a <b \leq n} \sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} 1_{d_i = a} 1_{d_j=b} >(1+ o(1)) (2r-1) k \log k$$

We may rewrite the left hand side as:

$$\sum_{1\leq a ,b \leq n} \sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} 1_{d_i = a} 1_{d_j=b} 1_{a<b}$$

Now use the "carrying the 1" decomposition:

$$ 1_{a<b} = \frac{b}{n} - \frac{a}{n} + \frac{ a-b \operatorname{mod} n}{n}$$

The first two terms are pretty simple. The first term is:

$$\sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} \frac{d_j}{n} = \sum_{1 \leq j \leq k} \frac{d_j}{n} \log \left( \frac{j}{k-j} \right) \approx k $$

and the second term is similar.

Now we've replaced $1_{a<b}$ with a convolution operator. So let's take the discrete Fourier transform:

$$\frac{1}{n}\sum_{0 \leq \xi \leq n-1} \sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} e\left( \frac{d_j \xi}{n}\right) e\left( \frac{- d_i \xi}{n}\right) \left( \sum_{x=0}^{n-1} \frac{x}{n} e \left( \frac{x \xi}{n} \right)\right)$$

By the Hilbert transform inequality:

$$\left|\sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} e\left( \frac{d_j \xi}{n}\right) e\left( \frac{- d_i \xi}{n}\right)\right| \leq \pi k$$

So the bound is

$$\frac{\pi k}{n}\sum_{0 \leq \xi \leq n-1}\left| \sum_{x=0}^{n-1} \frac{x}{n} e \left( \frac{x \xi}{n} \right)\right| \approx \frac{\pi k}{n} \sum_{0 \leq \xi \leq n-1} \frac{n}{2 \pi \min(\xi,n-\xi)} \approx k \log n$$

This gives:

$$k \log n > (1+o(1)) (2r-1) k \log k$$

Hence:

$$n > k^{ 2r-1 +o(1) }$$

Note that the base notation trick in the original post allows us to remove the $o(1)$ in the exponent bound by amplification.


Here is the matching lower bound:

Suppose that I have two sequences of $k$ numbers, one of which is a sequence of numbers from $1$ to $n_1$ that is increasing with probability $r_1$, and one which is a sequence from $1$ to $n_2$ that is increasing with proobability $r_2$. For any fraction $a/b$, I can construct a sequence of $k^b$ numbers from $1$ to $n_1^a n_2^{b-a}$ that is increasing with probability $\frac{a}{b} r_1 + \frac{b-a}{b}r_2$ as follows:

Write a number from $1$ to $k^b$ in base $k$ notation as $b$ numbers from $1$ to $k$. Choose randomly $a$ of the numbers and apply the first sequence, getting a number from $1$ to $n_1$. For the rest, apply the second sequence, getting a number from $1$ to $n_2$. Encode this sequence of numbers lexicographically as a single number from $1$ to $n_1^a n_2^{b-a}$ (generalizing base notation).

For any two numbers $i$ and $j$, consider the first place where they are not equal. In that place, $j$ must be larger than $i$. $d_j$ is equal to $d_i$ in all previous places. Hence as long as $d_j> d_i$ in this place, $d_j>d_i$. The probability that it is greater in this place is at least $r_1$ if this number was chosen and $r_2$ if it wasn't, so the total probability is at least $\frac{a}{b} r_1 + \frac{b-a}{b}r_2$.

This shows that we can take $k=n^{1/f(r)}$ for a convex function $f$. In particular, because we can take $f(1)=1$ (totally deterministic sequence) and $f(1/2-\epsilon)=0$ (totally random), we know $f(r) \leq 2r-1+\epsilon$, so we can get $k$ at least $n^{1/(2r-1)-\epsilon}$


An explanation of why $1/(j-i)$ is in fact the right weight function. Basically, this lower bounding method spends an equal amount of work improving the probability that $d_j>d_i$ for $j-i$ at any given scale. So the weight function should make every scale equally valuable, which $1/(j-i)$ does.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Linus Hamilton May 11 '15 at 7:03
  • $\begingroup$ @LinusHamilton That's a typo. I meant to send $l$ to $|infty$, not $0$. $\endgroup$ – Will Sawin May 11 '15 at 13:39
  • $\begingroup$ Ah, I see what's happening now. So $O(n^{1/r})$ is indeed wrong. Thanks, good example! $\endgroup$ – Linus Hamilton May 11 '15 at 14:04
  • 1
    $\begingroup$ 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... $\endgroup$ – Terry Tao May 11 '15 at 16:59
  • 2
    $\begingroup$ 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. $\endgroup$ – Terry Tao May 12 '15 at 2:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.