Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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
add comment

1 Answer

Jensen's inequality states that, if $\phi$ is a convex function \begin{equation} \phi( \mathbb{E}X) \leq \mathbb{E}\phi(X) \end{equation}

In your particular case, consider \begin{equation} \begin{aligned} \phi_n : x = (x_1,...,x_n) \mapsto \max_{i \in [1, n]} \{x_i\} \end{aligned} \end{equation}

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) \begin{equation} \max_i \mathbb E X_i \leq \mathbb{E} (\max_i X_i) \end{equation}

share|improve this answer
    
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
1  
(And, to be very bold, this does not even contradict the claim itself; it's only that equality is rather "unlikely".) –  Raphael Jun 12 '13 at 14:22
1  
@Raphael: see my answer to your other question math.stackexchange.com/questions/426998/… for more about upper bounds on the expectation of the maximum in terms of the expected value of the individual values. –  András Salamon Jun 22 '13 at 22:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.