# Expectation of maximum of a function whose expectation is concave

An analysis of a data structure yields a property of the form

$\qquad \mathbb{E}[ f(k) ] = H_k + H_{n-k+1} - 1$

for some natural $n$ and all $1 \leq k \leq n$. Note that the $f(k)$ are not independent.

Now I am interested in the quantity

$\qquad \mathbb{E}[\max_{k=1,\dots,n} f(k)]$.

Since $\mathbb{E}[f(k)]$ is concave on $[1,k]$ if continued on the reals and the maximum is "nice", I think it should be possible to apply (the symmetric version of) Jensen's inequality to conclude

$\qquad \mathbb{E}[\max_{k=1,\dots,n} f(k)] \leq \max_{k=1,\dots,n} \mathbb{E}[f(k)] = \mathbb{E}[f(n/2)] = 2H_{n/2} + \frac{1}{n/2 + 1} - 1$,

glossing over odd $n$.

Does this really hold? If so, how can I make the argument formal? If not, is there any handle on the desired quantity? Right now, I don't know more about the distribution for $f(k)$.

Note that I can expect a logarithmic bound, so we should be able to make a connection.

-
Sorry but $E[\max\cdots]\geqslant\max E[\cdots]$, always, not the other way round (and Jensen is not needed to prove it). – Did Jun 12 '13 at 11:24

Jensen's inequality states that, if $\phi$ is a convex function $$\phi( \mathbb{E}X) \leq \mathbb{E}\phi(X)$$
In your particular case, consider \begin{aligned} \phi_n : x = (x_1,...,x_n) \mapsto \max_{i \in [1, n]} \{x_i\} \end{aligned}
For all $n$, $\phi_n$ is convex since $\forall t \in [0,1]$, $\max \{ tx^1_i + (1-t)x^2_i\} \leq t \max\{x^1_i\} + (1-t) \max\{x^2_i\}$, therefore (unfortunately) $$\max_i \mathbb E X_i \leq \mathbb{E} (\max_i X_i)$$
Too bad, thanks. I take it you know of no way to use the expected value for $f(k)$ towards obtaining an upper bound on the expectation of the maximum? – Raphael Jun 12 '13 at 13:44