Inequality for descents after applying Cauchy-Schwarz

Let $S_i$ be the symmetric group defined over i elements. Let $W_i$ be defined as $$W_i=D_i-\frac{i-1}{2}.$$ $D_i$ is the random variable counting the number of descents of a random permutation in $S_i$ (so we know that $E[D_i]=\frac{i-1}{2},$ $\operatorname{Var}(D_i)=\frac{i+1}{12}$ and $E[D_n^3]=\frac{(n^2-n+2)(n-1)}{8}$)

Then one has

\begin{align*} \frac{144}{n^4(n+1)^2}\left( \sum_{1\le i, j \le n-1} E[W_{i-1}^2 W_{j-1}^2] \right) &\stackrel{Cauchy}{\le} \frac{144}{n^4(n+1)^2} \left( \sum_{1 \le i, j \le n-1} \sqrt{E[W_{i-1}^4]E[W_{j-1}^4]} \right) \\ &\stackrel{?}{\le} \frac{C}{n^4(n+1)^2} \left( \sum_{1 \le i, j\le n-1}ij \right) \end{align*}

I'm having problems understanding how to get the inequality that I marked as $?$. While I understand that I can choose a big enough constant instead of $144$, but I don't get how the terms in the root are bounded by $ij$.


Descents in a uniform random permutation are one-dependent. They are also determinantal (as nonnegative integer valued random variables). In fact, all one-dependent processes are determinantal as proved in this article https://arxiv.org/pdf/0904.3740.pdf which is

    On adding a list of numbers (and other one-dependent determinantal processes)

by Borodin, Diaconis and Fulman, published in Bull. Amer. Math. Soc., 2010. If you look at that article, the main section pertaining to your questions is example 11 on page 12 which is descents in a uniform random permutation. They also give references to the original discoverer and main expositors: MacMahon; Stanley; and Gessel and Viennot.

The claim you are asking about is that $\mathbf{E}[W_n^4] \leq c n^2$ for some $c$. Then you can take $C = 144 c^2$ in your desired inequality. Let $\mathsf{X}_i$ be the indicator that the pair of spots $(i,i+1)$ give a descent in your permutation, for $i \in \{1,\dots,n-1\}$. Let $\mathsf{Y}_i = \mathsf{X}_i - \frac{1}{2}$, since $\mathbf{E}[\mathsf{X_i}]=1/2$. (If you write a permutation in 1-line notation, and then do a left-right reversal of the numbers you will interchange the set of descents with its complement, so all the $\mathsf{X}_i$'s are equally likely to be $0$ or $1$ if you just focus on their separate marginals.) Then $\mathsf{X}_i$ is independent of $\mathsf{X}_j$ for $|i-j|>1$. That is what it means to be 1-dependent. So $\mathsf{Y}_i$ is independent of $\mathsf{Y}_j$ for $|i-j|>1$. Therefore, in the quadruple sum $$ \mathbf{E}[W_n^4]\, =\, \sum_{i,j,k,\ell=1}^{n-1} \mathbf{E}[\mathsf{Y}_i \mathsf{Y}_j \mathsf{Y}_k \mathsf{Y}_\ell] $$ you only need to keep those indices such that $|i-j|\leq 1$ and $|k-\ell|\leq 1$ and then consider what happens when you permute the components of the ordered 4-tuple $(i,j,k,\ell)$. Note that combinatorial factor is at most $4!=24$ and so for the purpose of just checking that there is a $c$, we could skip it at first. The reason we only need those cases is if some $Y_k$, for example satisfies that $\min(\{|k-i|,|k-j|,|k-\ell|\})$ were at least 2, then that variable would be independent of the other so we could move it into its own expectation. But $\mathbf{E}[\mathsf{Y}_k]=0$ since we centered it.

But then you are done. It is easy to see that the number of indices $(i,j,k,\ell)$ such that $|i-j|\leq 1$ and $|k-\ell| \leq 1$ is bounded by $3(n-1)$ times $3(n-1)$. That product is bounded by $cn^2$.