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$.



Random sequence of integers in $\{1, 2, \dots, n \}$ which is "everywhere probably increasing" - how long can it be?
I adapt an argument from [this blog post of mine](https://terrytao.wordpress.com/2013/10/29/a-spectral-theory-proof-of-the-algebraic-regularity-lemma/), exploiting the $\ell^2$ boundedness of the discrete Hilbert transform (i.e. [Hilbert's inequality](http://en.wikipedia.org/wiki/Hilbert%27s_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](http://arxiv.org/abs/0909.2190) (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))}$.


