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



\begin{problem}
In this problem, we analyze probabilistically the 1st stage of bubble
sort performed on a list of $n$ integers $\{ i_1, \ldots i_n \}$.  We
assume that all the integers are distinct and that the order of the
integers is chosen uniformly from all possible orderings.

On the first step we compare integers $i_1$ and $i_2$. If $i_1 > i_2$
we swap them otherwise we leave them as they are. On step $k~(2\leq
k\leq n-1)$, we compare the new $i_k$ with $i_{k+1}$. If $i_k >
i_{k+1}$ we swap else we leave them as they are.

\begin{problemparts}
\problempart If a number $x$ is randomly (uniformly) chosen from a set of $n$
distinct numbers, what is the probability that $x$ is the largest
number in the set?

\solution{$1/n$}

\problempart What is the probability that on the $k$th step ($2\leq k\leq n-1)$,
$i_{k+1}$ is the biggest integer to appear in the list so far?

\solution{
%$\Pr({\mbox{choosing largest of $n$ numbers}}) = 1/n$.  
$\Pr({\mbox{$i_{k+1}$ in $k$ step is highest so far}})=1/(k+1)$.
}

\problempart Let $C_k$ be a random variable that is equal to $1$ if 
$i_{k+1} > i_{k}$. What is $\expect{C_k}$?

\solution{
\[\expect{C_k} = \Pr({C_k = 1}) 
        = \Pr({\mbox{ $i_k$ is highest so far}}) 
        = \frac{1}{k+1}\]
}

\problempart Let random variable $C=\sum_{k=1}^n C_k$. 
Give an asymptotic bound for $\expect{C}$ as well as an interpretation
of what $\expect{C}$ is.

\solution{
\[\expect{C} = \sum_k \expect{C_k} = \sum_{k=2}^{n}\frac{1}{k} \sim \ln n.\]

$C$ is the total number of swaps, 
so $\expect{C}$ is the expected number of swaps.
}

\end{problemparts}
\end{problem}
