\documentstyle[12pt,epic,eepic,twoside,macpsfig,amssymb]{article}
\input{macros-course}
%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\psol{11}{December 7, 1995}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
\bparts
\ppart 
$E(X+Y) = E(X) + E(Y)$. $E(X) = 2\cdot(\frac{1}{4}) +
3\cdot(\frac{1}{4}) + 5\cdot(\frac{1}{2}) = \frac{15}{4}$. $E(Y) =
1\cdot(\frac{2}{3}) + 4\cdot(\frac{1}{3}) = 2$. Hence $E(X+Y) = 2 +
\frac{15}{4} = \frac{23}{4}$.
\ppart 
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
$X$ & $Y$ & $max(X,Y)$ & $Pr$ & $max(X,Y)\cdot Pr$ \\ \hline
$2$ & $1$ & $2$ & $(\frac{1}{4})(\frac{2}{3})$ & $\frac{1}{3}$ \\ \hline
$3$ & $1$ & $3$ &  $(\frac{1}{4})(\frac{2}{3})$ & $\frac{1}{2}$ \\ \hline
$5$ & $1$ & $5$ &  $(\frac{1}{2})(\frac{2}{3})$ & $\frac{5}{3}$ \\ \hline
$2$ & $4$ & $4$ &  $(\frac{1}{4})(\frac{1}{3})$ & $\frac{1}{3}$ \\ \hline
$3$ & $4$ & $4$ &  $(\frac{1}{4})(\frac{1}{3})$ & $\frac{1}{3}$ \\ \hline
$5$ & $4$ & $5$ &  $(\frac{1}{2})(\frac{1}{3})$ & $\frac{5}{6}$ \\ \hline \hline
\end{tabular}
\end{center}
Summing the last column we find that $E(max(X,Y)) = 4$.

\ppart 
Since $X + Y - max(X,Y) = min(X,Y)$ we get that $E(min(X,Y)) = E(X + Y) - E(max(X,Y)) = \frac{7}{4}$.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
Let B stand for boy and G for girl. Then the different possible
sequences of babies are BG, GB, BBG, GGB, BBBG, GGGB, .....  There are
two sequences of length $n$ for all $n \geq 2$. The probability of
occurence of a sequence of length $n$ is $2^{-n}$. Hence, E(number of
children) $= {\displaystyle \sum_{k=2}^\infty 2k\cdot 2^{-k}} = 3.$


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
\bparts
\ppart
It makes no difference how we arrange the numbers.  The expected value
is the same.  Why?  If we label the ends of the spinner we can define
$2$ random variables $X$ and $Y$.  $X$ is the number pointed to by one
end of the spinner and $Y$ is the other number.  We wish to maximize
$E(X+Y)$.  But since $E(X+Y) = E(X) + E(Y)$ and $E(X) = E(Y) =
(2n+1)/2$, all arangements give the same expected value of $2n+1$.

\ppart 
The best way to do this is to ensure that $1$ is opposite $2$, $3$ is
opposite $4$, $\ldots$, and $2n-1$ is opposite $2n$.  Let's call this
arrangement $A^*$. This will maximize the expected value of the product.

Consider any arrangement that isn't the one described above.  It therefore
must contain an odd $i$ that isn't paired up with $i+1$.  Pick the smallest
such $i$ and call it $k$.  Say $k$ is opposite $p$ and $k+1$ is opposite
$q$.  We know that $p$ and $q$ are bigger than $k$ (by choosing $k$ to be
the smallest such number we are assured that all numbers smaller than $k$ are
``properly'' paired up).  Now consider the new arrangement where $k$ is
paired with $k+1$ and $p$ is paired with $q$.  It has a better expected
product than the previous arrangement.  

To prove this note that since all pairs are equally likely when we turn the
spinner, it suffices to show that the sum of the products of the numbers
(denoted by $S$) is larger in the second arrangement.  
\begin{eqnarray*}
S_2 - S_1 & = & k(k+1) + pq - kp - (k+1)q \\
          & = & k^2 + k + pq - kp - kq - q \\
                  & = & k^2 + (1-p-q)k + (p-1)q \\
                  & = & (k-q)(k-(p-1))
\end{eqnarray*}

Thus $S_2 - S_1$ is greater than zero if $k$ is smaller than both $q$ and
$p-1$.  But this is true because of our choice of $k$.  Thus the second
arrangement is better.

Now we can transform any arrangement that isn't equal to $A^*$ by repeatedly
applying the following operation:

``Find the smallest odd $i$ that isn't paired up with $i+1$.  If $i$ is
paired with $p$ and $i+1$ with $q$ then pair $i$ with $i+1$ and $p$ with
$q$''

Each time we perform this operation, we increase the expected value of the product.  Thus $A^*$ must be the best arrangement since it is the only arrangement where we cannot perform this operation.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Let's fix the $n$ numbers we are given.  We can assume that we are given a
random permutation of the $n$ numbers.

Let's define random variables $X_i (1 \leq i \leq n)$ by
\[
X_i = \left\{ \begin{array}{ll} 1 & \mbox{ if element $i$ is the maximum} \\
                                                                  & \mbox{ of $V[1],\ldots,V[i]$} \\
                                                                0 & \mbox{ otherwise} \end{array} \right.
\]

Note that the number of times we update the current maximum is precisely
$X_1 + \ldots + X_n$.  Since expectation is a linear operator, we can
compute $E(X_1 + \ldots + X_n)$ by finding $E(X_i)$ for all $i$ and summing
them up.  Note also that since $X_i$ is an ``indicator'' variable, we only
have to find $P(X_i=1)$.  $X_i = 1$ if element $i$ is the largest of
$V[1],\ldots,V[i]$.  In a random permutation, this happens with probability
$\frac{1}{i}$.  Why?  If you take $i$ distinct numbers and randomly permute
them, the probability that the largest one occupies the last (or any)
position is $1/i$.  If we note that 
\[P(X_i = 1) = \sum_{n_1,\ldots,n_i} P(X_i = 1 \mid
\mbox{first $i$ elements are $n_1, \ldots, n_i$})\cdot P(\mbox{first $i$
elements are $n_1$,\ldots,$n_i$)}
\] 
and further observe that the first term is $1/i$
we can conclude that $P(X_i = 1) = 1/i$.  
Thus
\begin{eqnarray*}
E(X) & = & \sum_i P(X_i=1) \\
     & = & \sum_{i=1}^n 1/i \\
         & = & H_n \approx \ln n
\end{eqnarray*}
Recall that $H_n$ is the $n$th Harmonic number. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
\bparts
\ppart
$E(X-m) = E(X) - E(m) = m - m = 0$. Thus $X-m$ is a random variable
with mean $0$.
\ppart Assume $n$ is even.
\begin{eqnarray*}
E(|X - n/2|) & = 2^{-n}\left[ {\displaystyle \sum_{k=0}^n {n\choose k} |k - \frac{n}{2}|} \right] & \\
 & = 2^{-n}\left[2  {\displaystyle \sum_{k=0}^{\frac{n}{2}-1} {n\choose k} (\frac{n}{2} - k) } \right] & \\
 & = 2^{-n}\left[n{\displaystyle \sum_{k=0}^{\frac{n}{2}-1} {n\choose k} }\right] + 2^{-n}\left[2{\displaystyle \sum_{k=0}^{\frac{n}{2}-1} {n\choose k}k} \right] & \\
 & = 2^{-n}\left[n(2^{n-1} - (\frac{1}{2}){n\choose \frac{n}{2}}) \right] + 2^{-n}\left[2{\displaystyle \sum_{k=1}^{\frac{n}{2}-1} {n-1\choose k-1}(\frac{n}{k})k} \right] & \\
 & = 2^{-n}\left[n(2^{n-1} - (\frac{1}{2}){n\choose \frac{n}{2}}) \right] + 2^{-n}\left[2n{\displaystyle \sum_{k=0}^{\frac{n}{2}-2} {n-1\choose k}} \right] & \\
 & = 2^{-n}\left[n(2^{n-1} - (\frac{1}{2}){n\choose \frac{n}{2}}) \right] + 2^{-n}\left[2n(2^{n-2} - {n-1\choose \frac{n}{2} - 1}) \right] & \\
 & = 2^{-n}\left[n(2^{n-1} - (\frac{1}{2}){n\choose \frac{n}{2}})  + 2n(2^{n-2} - {n-1\choose \frac{n}{2} - 1}) \right] & \\
 & = 2^{-n}{n\choose \frac{n}{2}}(\frac{n}{2}).
\end{eqnarray*}
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
\bparts
\ppart
There are $n/k$ groups of size $k$ each. Let $X_i$ be a random
variable that denotes the number of tests performed in group
$i$. $X_i$ takes value $1$ with probability $(1-p)^k$ and value $k+1$
with probability $1-(1-p)^k$. Hence the expected number of tests is
$E(\sum_{i=1}^{\frac{n}{k}} X_i) = \sum_{i=1}^{\frac{n}{k}} E(X_i) =
(\frac{n}{k})((1-p)^k + (k+1)(1 - (1-p)^k)) = n(1 - (1-p)^k +
\frac{1}{k})$.
\ppart
The $k$ must be chosen so that the derivative of the answer from part
a) w.r.t. $k$ is $0$, i.e. $(1-p)^k\ln(1-p) + \frac{1}{k^2} =
0$. Assuming that $p$ is very small, so that we can approximate
$(1-p)^k$ by $1$ and $\ln(1-p)$ by $-p$ we get that $k \sim
\sqrt{\frac{1}{p}}$. And the resulting expectation is $n\sqrt{p}$.

\ppart
If $p = 0.01$ then the fraction of work saved is $1 - \sqrt{0.01} =
0.9$, i.e. $90\%$ of the work is saved in such a situation.

\ppart
There are many possible improvements. Here is one. Consider a scheme
where we blend all the soldiers' blood and perform the test. If it
comes up negative we stop, else we split the soldiers into two groups
and repeat on each group. If $E_n$ is the expected number of test with
$n$ soldiers we see that it satisfies the recurrence
\[ E_n = (1-p)^n + (1- (1-p)^n)2E_{\frac{n}{2}}. \]
It is easily proven by induction that $E_n = \Theta(pn)$. Since, in an
expected sense, there will $pn$ soldiers with the disease, and the
number of soldiers with the disease is a lower bound on the number of
tests, hence this scheme is optimal upto constant factors.


\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
Consider a tournament (actually a distribution over tournaments) where
each game outcome is random (50-50). For any ordering (permutation)
$\sigma$ of the teams let the indicator random variable $X_\sigma$ be
$1$ if $\sigma$ is a valid chain and $0$ otherwise. The probability of
a given ordering $\sigma$ being a valid chain is $2^{-n}$. So, the
expected number of valid chains is $E({\displaystyle \sum_\sigma
X_\sigma}) = {\displaystyle \sum_\sigma E(X_\sigma)} = 10!\cdot2^{-9} =
7087.5$. Since this is greater than $3000$ there exists some
tournament which has at least $3000$ valid chains.

\end{problems}

\end{document}





