\documentstyle[12pt]{article}
\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6.5in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}

\begin{document}

{\bf Tutorial 13. }

\date{}

\section{Conditional Expectation}

We can define {\em conditional expectation}, or the expectation
of a random variable, conditioned on a
particular event as follows:

\begin{definition}
The conditional expectation of a random variable $R$ given an event $A$ 
is defined as
$$E[R \mid A] = \sum_{r \in Range(R)} r \cdot Pr(R = r \mid A).$$
\end{definition}

{\em Example: } 
Let $R$ be the outcome of a die. What is the expected value of 
$R$ given that $R \leq 4$ ? 

$$E[R \mid R \leq 4] = \sum_{r=1}^4 r Pr(R = r \mid R \leq 4)$$
But $Pr(R=r \mid R \leq 4) = \frac{1}{4}$.
So,
$$E[R \mid R \leq 4] = \frac{1}{4} \sum_{r=1}^4 r = 2.5$$


One use of conditional expectation is 
to compute an expectation. \\
The following theorem breaks down the expectation into 
conditional expectations. 

\begin{theorem}
Let $A_1,A_2,\ldots,A_n$ 
be a set of disjoint events whose union is the 
the sample space.  Then for any random variable $R$,
\[
E[R] = \sum_{i=1}^n E[R \mid A_i] Pr(A_i)
\]
\end{theorem}

Notice that this is analogous to the theorem of total probability:

\begin{theorem}
Let $A_1,A_2,\ldots,A_n$ 
be a set of disjoint events whose union is the 
the sample space. Then for any event $B$,
$$Pr(B) = \sum_{i=1}^n Pr(B \cap A_i).$$
\end{theorem}

{\em Proof of Theorem 1. }
\begin{eqnarray*}
E[R] &=& \sum_r r \cdot Pr(R=r) \\
&=& \sum_r r \cdot \left( \sum_{i=1}^n Pr(R=r \cap A_i) \right)\\
&=& \sum_r r \cdot \left( \sum_{i=1}^n Pr(R=r \mid A_i) Pr(A_i) \right) \\
&=& \sum_{i=1}^n \left(\sum_r r \cdot Pr(R=r \mid A_i)\right) Pr(A_i) \\
&=& \sum_i E[R \mid A_i] Pr(A_i)
\end{eqnarray*}
The first step uses the theorem of total probability with $B$ being
the event $R=r$. The second step is by the definition of 
conditional probability.
\qed


{\em Example: }
(Assembly plants)

Suppose there are two computer assembly plants $F$ and $S$. 
Plant $F$ is fast but sloppy: 
It makes $70\%$ of the computers, but
a computer from $F$ has a $2\%$ probability of breaking down
on any given day of use.  

Plant $S$ is slow and careful: 
It makes $30\%$ of the computers, but the breakdown probability is
only $1\%$. 

These computers get randomly mixed, so I buy one at random from the
store. 
What is the expected number of days my computer works? 

Let $D$ be the random variable giving the number of days my computer
works. 
Let $I_S$ be the event that I bought the computer from $S$, and let
$I_F$ be that I bought it from $F$. 
We solve this problem using conditional expectations. 
We calculate separately the conditional expectation of the
number of working days conditioned on $I_S$ and on $I_F$,
then combine using the conditional expectation theorem. 

The expected number of working days for a computer from $S$ 
with probability of failure $p=0.01$ is just
$$E[D \mid I_S] = \frac{1}{p}-1 = 99$$
Note that mean time to failure is $\frac{1}{p}$, hence the number
of working days is $\frac{1}{p}-1$.
Similarly, the expected number of working days for a computer from $F$
is 
$$E[D \mid I_F] =\frac{1}{.02}-1 = 49$$.

Now to calculate the expected number of working days for the computer
when we don't know which factory it came from, we use the conditional
expectation theorem:

$$E[D] 
  = E[D|I_S] Pr(I_S) + E[D|I_F] Pr(I_F) = 99 (.30) + 49(.70) = 64$$


\section{Covariance}

We saw in class that the variance of a random variable is a measure of
how it deviates from the mean. {\em Covariance} is another statistical
measure. It quantifies the similarity of the distributions of two
random variables.

\begin{definition}
The covariance of random variables $R_1$ and $R_2$ is  
\[
Cov(R_1,R_2) = E(R_1R_2) - E(R_1)E(R_2).
\] 
\end{definition}

If $R_1$ and $R_2$ are positively correlated then their
covariance is positive and if they are negatively correlated their covariance is
negative. Their covariance is zero if they are uncorrelated.

{\em Examples: }
Let $R_1$ and $R_2$ be uniform in the range $[1,6]$.
\begin{enumerate}
\item $R_1 = R_2$. In this case, 
$$Cov(R_1,R_2) = E(R_1^2) - E(R_1)^2 = Var(R_1) = 2\frac{11}{12}.$$
The variables are positively correlated. This is not a surprise ---
they are always equal.

\item $R_2 = 7 - R_1$. Now,
$$Cov(R_1,R_2) = E(R_1(7-R_1)) - E(R_1)E(7-R_1) =  
7E(R_1) - E(R_1^2) - 7E(R_1)+E(R_1)^2 $$
$$ = - E(R_1^2) + E(R_1)^2 $$
$$ = - Var(R_1) = -2\frac{11}{12}$$
The variables are negatively correlated, i.e., when one is high the other
is low. This is reflected by the negative covariance. 

\item $R_1$ are $R_2$ are independent (E.g. consecutive coin tosses).
Then $$Cov(R_1,R_2) = E(R_1R_2) - E(R_1)E(R_2) = E(R_1)E(R_2)-E(R_1)E(R_2) = 0.$$
The variables are uncorrelated.

\end{enumerate}


So if the variables are independent then, indeed their covariance
is zero. What about the converse? If the covariance is zero, are the
variables independent? 
The answer is no. E.g. let $R_1,R_2$ be in the range $[1,3]$ such that
$Pr(R_1 = i \cap R_2 = j) = \frac{1}{8}$ for all $(i,j)$ except
$(2,2)$ and $Pr(R_1 = R_2=2) = 0$. We can check that this gives
valid probability distributions for $R_1$ and $R_2$. 
$$Pr(R_1 =1) = \frac{3}{8}$$
$$Pr(R_1 =2) = \frac{2}{8}$$ 
$$Pr(R_1 =3) = \frac{3}{8}$$
Which add up to 1. 

The distribution of $R_1$ is the same as the distribution of $R_2$ but 
since $Pr(R_1=2 \mid R_2=2) = 0 \neq Pr(R_1=2)$, 
$R_1$ and $R_2$ are not independent. 
However,
\begin{eqnarray*}
Cov(R_1,R_2) &=& E(R_1R_2) - E(R_1)E(R_2) \\
&=& \sum_{i,j \in [1,3]} ijPr(R_1 = i \cap R_2 = j) - (\sum_{i \in [1,3]}i Pr(R_1 = i))^2\\
&=& \frac{1}{8} (1+2+3+2+6+3+6+9) - (\frac{3}{8}(1+3) + \frac{2}{8}2)^2\\
&=& 4-4 = 0
\end{eqnarray*}



\begin{theorem}
For random variables $R_1$ and $R_2$,
$$Var(R_1+R_2) = Var(R_1) + Var(R_2)  + 2Cov(R_1,R_2)$$
\end{theorem}

{\em Proof. }
\begin{eqnarray*}
Var(R_1+R_2) &=& E((R_1+R_2 - E(R_1+R_2))^2)\\
&=& E(R_1^2+R_2^2 + 2R_1R_2 -2(R_1+R_2)E(R_1+R_2) + E(R_1+R_2)^2)\\
&=& E(R_1^2+R_2^2 + 2R_1R_2 -2(R_1+R_2)(E(R_1)+E(R_2))\\
&+&E(R_1)^2 + E(R_2)^2 + 2E(R_1)E(R_2))\\
&=& E(R_1^2) +E(R_2^2) + 2E(R_1R_2) - 2E(R_1)^2 - E(R_2)^2 -4E(R_1)E(R_2)\\
&+& E(R_1)^2 + E(R_2)^2 + 2E(R_1)E(R_2)\\
&=& E(R_1^2) - E(R_1)^2 + E(R_2^2) - E(R_2)^2 + 2E(R_1R_2)  -2E(R_1)E(R_2)\\
&=& Var(R_1) + Var(R_2) + 2Cov(R_1,R_2)
\end{eqnarray*}
\qed

\section{Variance of Sums}

As a corollary to the previous theorem we have:
\begin{corollary}
If $R_1$ and $R_2$ are independent, then 
$$Var(R_1+R_2) = Var(R_1)+Var(R_2)$$
\end{corollary}

{\em Proof. } 
If $R_1,R_2$ are independent, then $Cov(R_1,R_2)=0$.
\qed

A similar result holds for the sum of many independent random variables ---
but only needs that the variables are {\em pairwise} independent.

\begin{theorem}
If $R_1,\ldots,R_n$ are pairwise independent random variables, then
$$Var(R_1+\ldots+R_n)=\sum_{i=1}^n Var(R_i).$$
\end{theorem}

The proof is simple and follows from the definition of variance.
We won't do it here.

Using this result we can now derive the variance of a binomial distribution.
Let $R$ have an $n,p$ binomial distribution, i.e.,
$$Pr(R=k) = {n \choose k} p^k(1-p)^{n-k}$$

We can think of $R$ as the sum of $n$ Bernoulli independent random
variables. That is, the number of heads in $n$ tosses with the
probability of heads equal to $p$.
$$R = R_1+R_2+\ldots+R_n$$
And $Pr(R_i = 1) = p$, $Pr(R_i = 0) = 1-p$.
Now
$$ Var(R_i) = E(R_i^2) - E(R_i)^2 = p - p^2$$
Hence from the theorem,
$$Var(R) = \sum_{i=1}^n Var(R_i) = n Var(R_i) = p(1-p)n.$$


\section{Review of Markov, Chebyshev, Chernoff and Binomial bounds}

Let us review the methods we have for bounding deviation from the
mean via the following example.
Assume that IQ is made up of thinkatons; each thinkaton fires
independently with a $10\%$ chance. We have 1000 thinkatons in all,
and IQ is the number of thinkatons that fire. 
What is the probability of having Marilyn's IQ of 228?

So the IQ is a Binomial distribution with $n=1000, p= 0.1$.
Hence $E(IQ) = 100, \sigma_{IQ} =\sqrt{0.09 \times 1000} = 9.48$.

An IQ of 228 is $128/9.48 > 13.5$ standard deviations away.

Let us compare the methods we have for bounding the probability of this IQ.

\begin{enumerate}
\item Markov: 
$$Pr(IQ \geq 228) \leq {100 \over 228} < 0.44$$
\item Chebyshev:
$$Pr(IQ - 100 \geq 128 ) \leq {1 \over 13.5^2+1} < {1 \over 183}$$ 
\item Chernoff: 
$$Pr(IQ \geq 2.28 \times 100) \leq e^{-(\ln 2.28  + 1/2.28 -1)228} \leq e^{-59.9}$$
\item Binomial tails:
$$Pr(IQ \geq 228) = Pr(1000-IQ \leq 772) = F_{0.9,1000}(772) \leq e^{-72.5}$$
Here we used the formula for the binomial tail from Lecture 21 with 
$p = 0.9, n = 1000, \alpha = 0.772$.

\end{enumerate}

Note that the more we know about the distribution the better are the 
bounds we can obtain on the probability.

\section{Chernoff bounds and binomial tails}

%Using the formulas from Lecture 21, 
Here we derive
a bound on the deviation of a binomial
random variable from its mean in terms of standard deviations. 
%The analysis is messy but the bound is simple as we see in the
%following theorem:

\begin{theorem}\label{Binom}
If $R$ has an unbiased binomial distribution, then for $c\geq 1$,
$$Pr(R-E(R) \geq c\sigma_R) \leq e^{-c^2/2}$$
\end{theorem}

>From Chebyshev we know that this probability is at most ${1 \over 1+c^2}$.
%Using the bounds on the tails of the binomial distribution computed
%earlier in the course, 
We can actually show that this probability is at most
$e^{-c^2/2}$, which is much smaller as $c$ increases. The proof
can be derived from the tail probabilities of the binomial distribution
covered in Lecture 21. Alternatively, we can use the following Chernoff-bound-like result:

\begin{theorem}\label{Chernoff}
Let $X_1,X_2,\ldots,X_n$ be independent random variables with
$Pr(X_i = 1) = Pr(X_i = -1) = \frac{1}{2}$. 
Let $X = \sum_{i=1}^n X_i$. Then,
$$Pr(X \geq c \sqrt{n}) \leq e^{-c^2/2}$$
\end{theorem}

{\em Proof of Theorem \ref{Binom}. }
For $i=1,\ldots,n$, 
let $R_i = {X_i +1 \over 2}$. Then $Pr(R_i = 0) = Pr(R_i = 1) = \frac{1}{2}$.
That is the $R_i$'s are unbiased Bernoulli trials. 
Then $R = \sum_{i=1}^n R_i$, has the unbiased binomial distribution.

Now
\begin{eqnarray*} 
Pr(R-\frac{n}{2} \geq c \frac{\sqrt{n}}{2})  &=& Pr(2R-n \geq c \sqrt{n})\\
&=& Pr(X \geq c \sqrt{n}) \\
&=& \leq e^{-c^2/2}
\end{eqnarray*}

But $E(R) = \frac{n}{2}$ and 
$\sigma_R = \frac{\sqrt{n}}{2}$. Hence,
$$Pr(R-E(R) \geq c\sigma_R) \leq e^{-c^2/2}$$
\qed

{\em Proof of Theorem \ref{Chernoff}. }

$Pr(X \geq c\sqrt{n}) = Pr(e^{tX} \geq e^{tc\sqrt{n}})$ for any $t > 0$.
By Markov's inequality,
$$Pr(e^{tX} \geq e^{tc\sqrt{n}}) \leq {E(e^{tX}) \over e^{tc\sqrt{n}}}$$
Since the $X_i's$ are independent,
$$E(e^{tX}) = E(e^{t\sum_{i=1}^nX_i}) = [E(e^{tX_i})]^n$$
Now,
$$E(e^{tX_i}) = {e^t + e^{-t} \over 2} \leq e^{t^2/2}$$
from the Taylor expansions of $e^t$ and $e^{-t}$.
Hence,
$$Pr(X \geq c\sqrt{n}) \leq {e^{\frac{t^2n}{2}} \over e^{tc\sqrt{n}}} = 
e^{\frac{t^2n}{2} - tc\sqrt{n}}$$
Since we can choose any positive $t$, use $t = {c \over \sqrt{n}}$ to get
$$Pr(X \geq c\sqrt{n}) \leq e^{-c^2/2}$$
\qed


\section{Generalized Chernoff}  

The theorem from the previous section can be generalized as follows. We
don't give the proof here, but it is similar to the previous one. Note that
this result is not as good as those derived previously for binomial distributions but it is more general in what it covers.

\begin{theorem}
Let $R_1,\ldots,R_n$ be independent random variables with
$0\leq R_i \leq 1$. Let $R=\sum_{i=1}^n R_i$.
Then 
$$Pr(R - E(R) \geq c\sqrt{n}) \leq e^{-c^2/2}$$
\end{theorem}

{\em Example: } Load balancing. 

A set of jobs $J_1,\ldots,J_n$ have to be scheduled on a 
set of processors $P_1,\ldots,P_m$. 
The length (processing time) of each job is some number $L_i$ in the
range $[0,1]$, unknown to us. We would like to schedule the
jobs on the machines so that the load on the machines is 
balanced. The average load is $L = {\sum_{i=1}^n L_i  \over m}$.
We would like the load on every machine to be not much more than this.
Achieving such a schedule can be hard though, since we don't know 
ahead of time which jobs are long and which are short. By using a random
strategy we can be almost certain to do very well, however. For example,
suppose we pick a random machine for each job. 

Consider this process
from a machine's point of view. The probability that job $j$
is assigned to it is $\frac{1}{m}$. 
Let $R_{ij}$ be the random variable indicating the time spent
by the machine $i$ on job $j$. 
Then 
$$Pr(R_{ij} = L_j) = \frac{1}{m}, \quad Pr(R_{ij} = 0) = 1-\frac{1}{m}.$$
Hence $E(R_{ij}) = {L_j \over m}$.
The load on machine $i$ is then $\sum_{j=1}^n R_{ij}$.
$$E(\sum_{j=1}^n R_{ij}) = \sum_{j=1}^n E(R_{ij}) = \sum_{j=1}^n{L_j \over m} = L$$

>From the generalized Chernoff bound, 
$$Pr(\mbox{load on machine i } - L \geq c\sqrt{n}) \leq e^{-c^2/2}$$
By Boole's inequality,
\begin{eqnarray*}
Pr(\mbox{load on any machine } \geq L+  c\sqrt{n}) &\leq& 
\sum_{i=1}^m Pr(\mbox{load on machine i } \geq L + c\sqrt{n}) \\
&\leq& m e^{-c^2/2}
\end{eqnarray*}

If we choose $c = \sqrt{2\ln m}+6$, say, then
$$Pr(\mbox{load on each machine } \leq L + c \sqrt{n}) \geq 1 - m e^{-\ln m -18}  = 1 - e^{-18} = 0.99999998..$$  

Hence we can be fairly sure (i.e., with probability at least $1-e^{-18}$) that
every machine will have load at most $L+\sqrt{2n\ln m }+6\sqrt{n}$. For many
values of $n$ and $m$ this is very close to optimal. For example, if 
$m=10$, $n=5000$, and $L=300$, the maximum load on any machine will 
almost surely not exceed 332. (In fact it is likely to be even less --- 
we have been fairly crude in our bounds.)

\section{Team Problem}
Consider a square grid of 100x100 nodes.
This is a communication network.  Each node sends 1
message per second to a randomly selected destination node.  Messages
are routed through the row to the correct column and then through the
column to the correct destination.  It can be assumed that messages
are routed instantaneously, provided there is sufficient bandwidth (capacity) 
on the edges of the network.  The problem is to get upper bounds on
the edge capacities so that with probability $0.99$  
all traffic for the next 10 years can be handled
without ever exceeding any edge capacity. In other words, we want to 
be virtually certain that there will never be a second in the next 10 years
during which we don't have enough capacity on a link in the network.

\begin{enumerate}
\item What is the expected traffic per second through any given edge?
[Hint: This is not the same for every edge.]
\item We need a success probability of $99\%$ over 10 years. 
What success probability do we need per second? Let $P_f$ be the
probability of failure in 1 second. That is $1-P_f$ is the probability
that the network succesfully handles the load in one second 
(i.e. the traffic through every edge is at most capacity of the edge). 
How small must $P_f$ be to 
ensure that probability of any failure ever in 10 years is less than
$1\%$.
\item Show that if each edge has capacity $136 > 50e$, then the guarantee can be made.
Use the bound obtained on $P_f$. [Hint: Apply Boole's inequality
and Chernoff's bound.]
\item Find better bounds for the edge capacities. You can 
specify a different bound for each edge (depending on its
expected traffic). 
\end{enumerate}

\end{document}


