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

So, obvious question - what is the constant in Terry Tao's bound? It seems to me to be $\pi \log 2 \approx 2.178$. Can this be improved, ideally all the way to $1$? 


This strongly suggests that $1/(j-i)$ is in fact the right weight function. Basically, this lower bounding method (and also the previous one) spend 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.


(This method is simpler and more general than my previous method.)