        \problemdata       % Takes 5 *mandatory* arguments
        {entries-greater}             % latex-friendly label for the prob.
        {expectation}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {S02 cp11f-2} % Usage (list ones you are aware of).
        {Ashish, S02}        % Last revision info (author, date).



\begin{problem} 
Suppose that I choose a listing of the numbers $1, 2, \ldots, n$
uniformly at random.  What is the expected number of entries that are
greater than all preceding entries?  For example, in the listing 4, 2,
1, 5, 3, the numbers 4 and 5 are greater than all preceding
entries\footnote{This problem can be equivalently phrased as follows:
There are n people whose heights are $1, 2, \ldots, n$. I choose a
random permutation, and line them up accordingly. What is the expected
number of people who can see what's going on in front of the line? We
are assuming that a person can see if and only if all the people in
front of him/her are shorter.} (Hint: What's the probability that the
first entry is greater than all the preceding entries? What about the
second one?)

\solution{Let $i_k$ be an indicator for the event that the $k$-th
entry is greater than the preceding $k-1$ entries.  By linearity of
expectation

\begin{eqnarray*}
\expect{\text{\# new maxima}}
    & = &   \sum_{k=1}^n \Ex(i_k) \\
    & = &   \sum_{k=1}^n 1 \cdot \Pr(i_k = 1) + 0 \cdot \Pr(i_k = 0) \\
    & = &   \sum_{k=1}^n \Pr(i_k = 1)
\end{eqnarray*}

All that remains is to compute $\Pr(i_k = 1)$, which is the
probability that the $k$-th entry is greater than all preceding
entries.  Note that each of the first $k$ entries is equally likely to
be the largest.  Therefore, $\Pr(i_k = 1) = \frac{1}{k}$.
Substituting into the equation above gives:

\begin{eqnarray*}
\expect{\text{\# new maxima}}
    & = &   \sum_{k=1}^n \Pr(i_k = 1) \\
    & = &   \sum_{k=1}^n \frac{1}{k} \\
    & = &   H_n
\end{eqnarray*}
}

\end{problem}
