Bounding expected maximum via adjacent differences

Question

For $X_i$, $i\in[n]$ be a sequence of integrable random variables. Is there a universal constant $c>0$ such that $$\mathbb{E}\max_{i\in[n]}X_i \le c\left( \max_{i\in[n]}\mathbb{E}|X_i| + \mathbb{E}\max_{i\in[n]}|X_i-X_{i+1}| \right), $$ where $X_{n+1}:=X_1$?

This would certainly be true, with $c=1$, if $ \mathbb{E}\max_{i\in[n]}|X_i-X_{i+1}| $ were replaced by $ \mathbb{E}\max_{i,j\in[n]}|X_i-X_j| $.

What I am looking for is a sparsified version, with only $n$ cyclical comparisons (rather than $\approx n^2$).

Answer 1

I don't think so. Define the $X_i$'s as follows. Choose $j \in [n]$ uniformly at random, set $X_j = n$, set $X_{j+k} = n-|k|\sqrt{n}$ for $1 \le |k| \le \sqrt{n}$ (with indices taken mod $n$), and set $X_i = 0$ for the remaining $i$. Then $\max_{i \in [n]} X_i = n$ almost surely, so $\mathbb{E}\max_{i \in [n]} X_i = n$. For any fixed $i \in [n]$, we have $\mathbb{E}|X_i| \asymp \sqrt{n}$. And finally, $\max_{i \in [n]} |X_i-X_{i+1}| = \sqrt{n}$ almost surely. In summary, the LHS is $n$ while the RHS is $c\left(c'\sqrt{n}+\sqrt{n}\right)$.