        \problemdata       % Takes 5 *mandatory* arguments
        {variance-6}             % latex-friendly label for the prob.
        {variance}               % The topic of the problem content.
        {Velleman}               % Source (if known)
        {S98 PS11-7; F97 PS11-8} % Usage (list ones you are aware of).
        {Theory Pig, S02}        % Last revision info (author, date).
\begin{problem} %source: spring00 ps10-5
Let $X$ and $Y$ be independent random variables taking on
integer values in the range $1$ to $n$ uniformly.  Compute the
following quantities: 

\begin{problemparts}

\problempart $\variance{aX+bY}$

\solution{First, we compute $\variance{X}$, 
which is also $\variance{Y}$ since $X$ and $Y$ are identically distributed.
\begin{align*}
\variance{X}
        & = \expect{X^2} - \expect{X}^2 
        = \sum_{i=1}^n i^2 \cdot \frac{1}{n}
                - \left( \sum_{i=1}^n i \cdot \frac{1}{n} \right)^2 \\
        & = \frac{(n+1)(2n+1)}{6} - \frac{(n+1)^2}{4} 
        = \frac{n^2 - 1}{12}
\end{align*}

We now use this to compute $\variance{aX + bY}$: 
\begin{align*}
\variance{aX+bY}
        & = \variance{aX} + \variance{bY} 
                & & \text{because $aX$ and $bY$ are independent} \\
        & = a^2 \variance{X} + b^2 \variance{Y}
                & & \text{Theorem~4.4 in Lecture Notes 24} \\
        & = (a^2 + b^2) \variance{X}
                & & \text{because $\variance{X} = \variance{Y}$} \\
        & = (a^2 + b^2) \frac{n^2 - 1}{12}
                & & \text{substitution from computation above}
\end{align*}
}

\problempart $\expect{\max(X,Y)}$

\solution{
First we compute the probability that the maximum of $X$ and $Y$ 
is equal to $i$: 
\begin{align*}
\Pr(\max(X,Y) = i) 
        & = \Pr(X \leq i \land Y \leq i) - \Pr(X < i \land Y < i) \\
        & = \Pr(X \leq i) \Pr(Y \leq i) - \Pr(X < i) \Pr(Y < i) \\
        & = \frac{i}{n} \cdot \frac{i}{n} 
                - \frac{i-1}{n} \cdot \frac{i-1}{n} \\
%       & = \frac{i^2 - (i-1)^2}{n^2} \\
        & = \frac{2i-1}{n^2}
\end{align*}

We now compute the expectation using these probabilities:
\begin{align*}
\expect{\max(X, Y)}
        & = \sum_{i=i}^{n} i \cdot \Pr(\max(X,Y) = i) 
          = \sum_{i=i}^{n} i \cdot \frac{2i-1}{n^2} \\
        & = \frac{1}{n^2} \cdot \sum_{i=1}^{n} (2i^2 - i) 
          = \frac{1}{n^2} \cdot \left(
                2 \cdot \frac{n(2n+1)(n+1)}{6} - \frac{n(n+1)}{2}
                \right) \\
        & = \frac{(n+1)(4n-1)}{6n}
\end{align*}

Alternatively, we could also compute it as follows:
\begin{align*}
\expect{\max(X,Y)}
        & = \sum_{i=0}^{\infty} \Pr(\max(X,Y) > i) 
          = \sum_{i=0}^{n-1} \left(1 - \Pr(\max(X,Y) \leq i)\right) \\
        & = n - \sum_{i=0}^{n-1} \Pr(X \leq i \land Y \leq i) 
          = n - \sum_{i=0}^{n-1} \Pr(X \leq i) \Pr(Y \leq i) \\
        & = n - \sum_{i=0}^{n-1} \left(\frac{i}{n}\right)^2 
          = n - \frac{1}{n^2} \cdot \frac{n(n-1)(2n-1)}{6} \\
        & = \frac{(n+1)(4n-1)}{6n}
\end{align*}
}


\problempart $\expect{\min(X,Y)}$

\solution{Note that $\max(X, Y) + \min(X, Y) = X + Y$.  
Thus,
\begin{align*}
\expect{\min(X, Y)}
        & = \expect{X} + \expect{Y} - \expect{\max(X, Y)} \\
        & = \frac{n+1}{2} + \frac{n+1}{2} - \frac{(n+1)(4n-1)}{6n} \\
        & = \frac{(n+1)(2n+1)}{6n}
\end{align*}
}

\problempart $\expect{|X-Y|}$

\solution{We could compute this directly. 
However, note that $|X - Y| = \max(X,Y) - \min(X, Y)$.  
Thus,
\begin{align*}
\expect{|X - Y|}
        & = \expect{\max(X, Y) - \min(X, Y)} \\
        & = \expect{\max(X, Y)} - \expect{\min(X, Y)} \\
        & = \frac{(n+1)(4n-1)}{6n} - \frac{(n+1)(2n+1)}{6n} \\
        & = \frac{n^2 - 1}{3n}
\end{align*}
}

\problempart $\variance{|X-Y|}$.

\solution{
We start with one of the standard formulas for variance:
\[
\variance{|X - Y|}
        = \expect{|X-Y|^2} - \expect{|X-Y|}^2 
        = \expect{(X-Y)^2} - \expect{|X-Y|}^2
\]

We could compute $\expect{(X-Y)^2}$ directly, 
but note that 
$\variance{X-Y} = \expect{(X-Y)^2} - \expect{X-Y}^2$, 
and $\expect{X-Y} = 0$. 
We can compute $\variance{X-Y}$ using the 
result in part (a). 
Thus, 
\begin{align*}
\variance{|X - Y|}
        & = \variance{X - Y} - \expect{|X-Y|}^2 \\
        & = (1^2 + (-1)^2) \cdot \frac{n^2 - 1}{12} -
                \left(\frac{n^2 - 1}{3n}\right)^2 \\
        & = \frac{(n^2 - 1)(n^2 + 2)}{18 n^2}
\end{align*}
}

\end{problemparts}
\end{problem}
