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



Bounding expected maximum via adjacent differences
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)$.


