\documentstyle[12pt]{article}
\begin{document}

% adapted from 6044-macros
% header hackery

\newlength{\toppush}
\setlength{\toppush}{2\headheight}
\addtolength{\toppush}{\headsep}
\def\subjnum{18.314}
\def\subjname{Combinatorial Analysis}

\def\doheading#1#2#3{\vfill\eject\vspace*{-\toppush}%
  \vbox{\hbox to\textwidth{{\bf} \subjnum: \subjname \hfil Professor Propp}%
    \hbox to\textwidth{{\bf} Massachusetts Institute of Technology\hfil#3\strut}%
    \hrule}}

\newcommand{\htitle}[1]{\vspace*{3.25ex plus 1ex minus .2ex}%
  \begin{center}{\Large\bf #1}\end{center}}
\newcommand{\Var}{{\rm Var}}
\newcommand{\Cov}{{\rm Cov}}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}

\doheading{2}{title}{Last Revised: February, 1993}

\begin{center}
{Review of Probability}
\end{center}

{\bf 1 Introduction.}  Consider the following problems:

1. If you use a particular sorting scheme, what are your chances of completing
the sort with a given number of comparisons?

2. If 20 million bits of information are sent from a satellite, and each has
one chance in $10^{-5}$ of being received in error, all independently, what is
the chance of six bits out of a particular 100 bits being in error?

3. What are the pros and cons of doubling your bet every time you lose
in an even gambling game? Is there a winning strategy for the lottery?

4. Suppose you must choose among a sequence of alternatives, but must accept
or reject each in turn without examining the rest at all. What should you do
to try to get the best of them? 

These are questions about probability. We will briefly review
the basic definitions
and results in this subject. It is an important subject worth your
learning in detail if you have not already done so.
\vspace{.5in} \\

{\bf 2 Fundamental Concepts and Definitions} A {\em finite
probability space} consists of a finite set $S$ called a {\em sample
space\/}  (the elements of which are called {\em outcomes}) and a real
valued function $P$ defined on $S$, called a {\em probability measure}
or {\em probability}. The function $P(x)$ obeys $P(x) \geq 0$ for $x
\in S$ and $\sum_{x \in S} P(x) = 1$. Also $P(x)$ is called the {\em
probability} of the outcome $x$.

The probability $P(x)$  is intended to represent the proportion of the time
the outcome $x$ is expected to occur, if the situation modeled by the
probability space were to occur repeatedly in real life.  A {\em uniform}
probability space is one in which all outcomes have the same probability,
which then is the reciprocal of the cardinality of $S$.

An {\em event} is a subset of the sample space $S$. For any subset $E$
of $S$ , the probability of $E$, written $P(E)$, is the sum of $P(x)$
over all $x$ in $E$. The event ${\overline E}$ is the complement of
$E$ in $S$, namely the event $S-E$. In a uniform probability space, the
probability of an event is its cardinality divided by that of $S$.

Two events $E_{1}$ and $E_{2}$ are said to be {\em mutually exclusive}
if they do not overlap (i.e. are disjoint). It follows from the definitions
that the probability of either of two mutually exclusive events is the sum
of their individual probabilities; that is,

\[ P(E_{1} \cup E_{2} ) = P(E_{1}) + P(E_{2}) \]

\noindent
provided $E_{1}$ and $E_{2}$ are disjoint.

In general we have

\[ P(E_{1} \cup E_{2}) = P(E_{1})  + P(E_{2}) - P(E_{1} \cap E_{2}) \]

\noindent
since 
without the subtraction term 
the outcomes that are in both $E_{1}$ and $E_{2}$  would 
contribute twice to the right hand side.

The {\em conditional probability} of an event $E$ {\em given} an event $F$,
written $P(E \mid F)$, is intended to represent the probability of $E$
if the sample space $S$ were reduced to $F$. Since in $S$ the sum of 
$P(x)$ over all $x$ in $F$ is only $P(F)$, not 1,
we cannot use $P(x)$ as our probability distribution on $F$;
to get a probability distribution $P_F$ with sample-space $F$
we should set $P_F(x)$ to 0 for $x$ not in $F$
and set $P_F(x) = P(x)/P(F)$ for $x$ in $F$
(check that this sums to 1!).
We now easily calculate that

\[ P(E \mid F) = P_F (E \cap F) = P (E \cap F) / P(F). \]

Two events $E,F$ are said to be {\em independent} if the probability of $E$
given $F$ is the same as the (unconditional) probability of $E$
(and therefore as the
probability of $E$ given ${\overline F}$). By our last definition this
means that for $E$ and $F$ independent,

\[ P(E \cap F) = P(E) \cdot P(F) . \]

Three or more events are said to be independent if the conditional
probability of any one $E$, given any subset of the others, is just $P(E)$.
Equivalently: a family of events $E_1,E_2,...,E_n$ is independent
if

\[ P(E_1 \cap E_2 \cap ... \cap E_n) = 
P(E_1) \cdot P(E_2) \cdot ... \cdot P(E_n) \]

\noindent
{\em and} if this equality also holds
for every sub-family of $E_1,...,E_n$.

A {\em random variable} $f$ is a real-valued function defined on the 
sample space of outcomes. Given a random variable, one can define related
events, such as the event $\{ f = a \}$
(this is a shorthand for $\{x: f(x) = a\}$)
or the event $\{ f \geq g \}$
where $f$ and $g$ are random variables
(as in the preceding case, we use a condition as an abbreviation for
the set of outcomes in the sample set that obey the condition). 
One can also define an {\em indicator random variable}
of a given event $E$, which has value 1 on the elements of $E$, and
0 elsewhere in $S$. Random variables can be added or manipulated like
ordinary real valued functions to produce new random variables.

Two random variables $f$ and $g$ are called {\em independent} if the
event $f=a$ is independent of the event $g=b$
for all real numbers $a$ and $b$.

The {\em expected value} or {\em mean} of a random variable $f$, written
as $<f>$ or $E(f)$, is

\[ E(f) = \sum_{x \in S} f(x) P(x) . \]

The {\em variance} or {\em mean square deviation} of a variable $f$,
written as $\Var(f)$, is the mean of the square of the difference of $f$ 
from its mean: 

\begin{eqnarray*}
\Var(f) & = & E((f-E(f))^{2}) \\
& = & \sum_{x \in S} (f(x) - E(f))^{2} P(x) .
\end{eqnarray*}

The {\em standard deviation}, written $\sigma (f)$, of a random
variable $f$ is the square root of its variance. The following
equalities hold, if we multiply a random variable $f$ by a constant
$c$:
		
\begin{eqnarray*}
E(cf) & = & cE(f) \\
\Var(cf) & = & c^{2} \Var(f) \\
\sigma (cf) & = & c \ \sigma (f) .
\end{eqnarray*}
 
The expectation of a sum of two random variables $f$ and $g$ is the
sum of their expectations no matter how $f$ and $g$ are related:
\[ E(f + g) = E(f) + E(g) . \]
More generally,
\[ E (cf + dg)  = c E(f) + d E(g) \]
for all real $c$ and $d$. This is the famous {\em linearity of
expectation\/}. In general, we do {\em not\/} have the same property for
the product; that is, the expectation of the product will usually not
be the product of the expectations of two random variables.
Nevertheless, it is the case that if two random variables are
{\em independent} of one another, then the product of their expectations
will equal the expectation of their product:

\begin{eqnarray*} 
E(fg) &  =  & \sum_{\mbox{all real $a,b$}} ab \, P(f=a \mbox{ and } g=b) \\
      &  =  & \sum_{\mbox{all real $a,b$}} ab \, P(f=a) \: P(g=b) \\
      &  =  & \sum_{\mbox{all real $a$}} a \, P(f=a) 
           \  \sum_{\mbox{all real $b$}} b \, P(g=b) \\
      &  =  & E(f) E(g).  
\end{eqnarray*}

The variance of the sum of two variables, being quadratic in them, has
terms in it that involve one variable at a time, and cross-terms that
involve both.  It obeys

\begin{eqnarray*}
\Var(f+g) & = & \Var(f)+\Var(g) + 2(E(fg)-E(f)E(g)) \\
& = & \Var(f) + \Var(g) + 2 \Cov(f,g).  
\end{eqnarray*}

\noindent
The {\em covariance} $\Cov(f,g)$ defined here is in some sense a
measure of the dependence of the variables $f$ and $g$. If they are
independent we have

\[ \Cov(f,g) = (E(fg)- E(f) E(g)) = 0.  \]

\noindent
This tells us that {\em the variance of a sum of independent random
variables is the sum of their variances.}

The expectation of an indicator variable, or of any variable $f$ that takes
on values 0 and 1 only, is the probability $p$ that $f=1$. The variance of
such a variable $f$ is $p(1-p)$.

If one has a family of random events $E_1,...,E_k$,
and one defines a random variable $f(x)$
equal to the number of $k$'s such that the outcome $x$ belongs to $E_k$,
then the expected value of $f$ is just
$\sum_k P(E_k)$.

The expectation represents the average
value of the random variable over the sample space. 
Therefore the expectation of a variable $f$
(like the average of numbers) cannot be
an extreme value of $f$, unless $f$ takes on only one value.  For example,
if $E(f)=5$, then there must be elements of the sample space for which $f$
is at least 5 (and ditto for ``... at most 5'').

The variance is obviously a measure of how much deviation from its mean
the variable exhibits in the sample space. We shall see more explicit 
interpretations  shortly. 

There is an alternate formula for the variance of $f$, in terms of
expectations, which is often useful:
\begin{eqnarray*}
\Var(f) & = & E((f-E(f))^{2}) = E(f^{2}-2fE(f) + E(f)^{2}) \\
       & = &  E(f^{2}) - 2E(fE(f)) + E(f)^{2} \\
       & = &  E(f^{2}) - 2E(f)E(f)) + E(f)^{2} \\
       & = &  E(f^{2}) - E(f)^{2}.
\end{eqnarray*}

{\bf 3 Bernoulli Trials. } {\em Bernoulli trials} refer to a
probability space describing $n$ independent ``trials'' of a 
two-valued (0-1) random variable which has probability $p$ of having value
1 in each trial. This situation arises with coin tosses, binary
message strings, and many other contexts. The outcomes are sequences
of length $n$ of the two values, say 0 and 1. If a sequence has $k$
1's in it, the probability it will occur in a series of $n$ trials is 

\[ p^{k} (1-p)^{n-k} . \]

\noindent
We can define the indicator variable $X_{k}$ for the event
``the $k$th bit $=1$''
as follows:

\[ X_{k} = \left\{ \begin{array}{ll}
                     1 & \mbox{if the $k$th bit of the sequence is 1,}
\\ 0 & \mbox{otherwise.} \end{array} \right. \] 
It is easy to see that
the value of the sum $X = \sum_{k=1}^{n} X_{k}$ on a particular
sequence $x$ is the number of 1's in $x$.  The mean of $X$ therefore
has value $np$; and $\Var(X) = np(1-p)$.

For Bernoulli trials, the probability that there are exactly $k$ 1's
is the probability of each outcome that has exactly $k$ 1's, summed over
all such outcomes. The number of outcomes having exactly $k$ 1's is
the number of different sequences of $n$ 0's and 1's of which there
are exactly $k$ 1's.  This number is called the {\em binomial
coefficient} $C(n,k)$. It satisfies

\[ C(n,k) = \frac{n!}{k!(n-k)!}.  \]

The entropy function $H$ is defined as
$H(q) = q \log_{2}(1/q) + (1 - q)\log_{2}(1/(1-q))$. Then one can show,
using {\it Stirling's formula}

\[ n! = \sqrt{2 \pi n} (n/e)^n \cdot (1 + o(1)) , \]

\noindent
that

\[ C(n, k) = 2^{nH(k/n) + O(\log n)} . \]

For large $n$, and for $k$ near $n/2$, this distribution looks much like a
{\em normal distribution} (see below) centered about $np$
with variance $np(1-p)$.
The probability distribution that the random variable ``the number of
1's'' (call it $f$) satisfies in Bernoulli trials is called a {\em
binomial distribution}, and satisfies:


\[  P(f=k) \: = \: C(n,k) \, p^{k} \, (1-p)^{n-k}. \]

\noindent {\bf Some Consequences.} We are already in a position to
draw conclusions about probability from these definitions. The fact
that the variance of a sum of independent random variables is the sum
of the variances, while multiplying a variable by a constant $c$
changes the variance by $c^{2}$, implies that upon averaging $n$
identically distributed independent random variables the variance of
the result is a factor $n$ smaller than that of the original
variables. For, one averages $n$ quantities by summing them and dividing by $n$.
Summing
them multiplies the variance by $n$, but dividing by $n$ divides the variance by
$n^{2}$, so that averaging reduces the variance by a factor of $n$. If
$n$ increases unboundedly, then the variance of the average must go to
0, if it was finite to begin with. Notice that the variable $K/n$ is
the average of the indicator variables for the event ``this bit is 1''
in Bernoulli trials.
\vspace{.5in} \\
{\bf 4 Tchebyschev's Inequality, The Weak Law of Large Numbers,
etc.} The variance of any variable, furthermore, provides an upper
bound on the spreading of that variable, as follows:
\vspace{.2in} \\

{\bf Tchebyschev's Inequality:} Let $f$ be a variable with mean $\mu$. We
then have

\begin{eqnarray*} 
\Var(f) &  =  & E( (f - \mu)^{2} ) \\
       &  =  & \sum_{a} \; (a- \mu)^{2} \, P(f=a) \\
       &  =  & \sum_{|a-\mu| > x} (a- \mu)^{2} \, P(f=a) + \sum_{|{a-\mu}| \leq x} (a-\mu)^{2} P(f=a) \\
       &  \geq &  \sum_{|{a-\mu}| > x} (a-\mu)^{2} \, P(f=a) \\
       & \geq  &  x^{2} \sum_{|{a-\mu}| >x} P(f=a) \\
       & \geq  &  x^{2} \; P(|f-\mu| >x), 
\end{eqnarray*}

\noindent
which can be written as {\em Tschebyschev's Inequality}

\[ P(|f-\mu| > x) \: \leq \:  \Var(f) /x^{2} \]

\noindent
or, substituting $x = c \cdot \Var(f)^{1/2}$,

\[ P(\, |f-\mu| > c(\Var(f))^{1/2} \, ) \: \leq \: c^{-2}. \]

\noindent {\bf Weak Law of Large Numbers.} We have seen that
the average of any $n$ independent 
random variables of finite variance $V$ has variance $V/n$.
By Tschebychev's Inequality, the
probability of a deviation of such an average from its mean by a fixed
amount $\delta$ or more will have $V/n\delta^2$ as an upper bound,
which goes to zero as $n$ gets large. More precisely,

\medskip

{\em Let $X_{1}, \ldots , X_{n}$ be independent random variables
having a common distribution with mean $\mu$, and set $S_{n} = X_{1} +
\ldots + X_{n}$. Then, for any $\delta > 0$, 
\[ \lim_{n \rightarrow \infty} 
P \left ( \left| \frac{S_{n}}{n} - \mu \right| \, \geq \, \delta \right) \; 
= \; 0. \]}

This statement is called the {\em Weak Law of Large Numbers.}
The Weak Law justifies the interpretation of the
probability $p$ of an event as the proportion of times the event will
occur, if the conditions of the problem are repeated sufficiently
often.
\vspace{.5in} \\

\noindent {\bf The Probability of an Event not Happening in Repeated
Independent Trials.} If an event $E$ has probability $p$ of happening
in each of $N$ independent trials, then it has probability $(1-p)^{N}$
of never happening. This is because on each successive trial, by
independence, the probability of $E$ not happening is $(1-p)$ no
matter what has happened before.


Suppose I shuffle a deck of 52 cards and then pick one, simultaneously
calling out ``Ace of Spades.'' If I repeat this procedure 52 times
(including the shuffle), what is the chance I never correctly identify
the card I choose?  Answer: $(1-1/52)^{52}$, which is close to $1/e$
(by a limit from elementary calculus).
\vspace{.5in} \\

\noindent {\bf Probability of Two Values of a Function Agreeing.}
Suppose I have a function defined on $N$ elements that can take on $M$
different values. What is the probability, $P$, that no two elements
have the same value, assuming all functions are equi-probable?

The number of functions on which all values are distinct is
$M(M-1) \cdots (M-N+1)$.  The total number of functions is $M^{N}$. The
ratio of these gives the desired probability. It is an easy excercise
to compute what this ratio is, and as an approximation one can find

\[ P \sim e^{-N(N-1)/(2M)}\ .  \]

This can be used to show, for instance, that the probability that among 50
people, no two have the same birthday, is very very small.
\vspace{.5in} \\

 \noindent {\bf Waiting Time.} An interesting question for
Bernoulli trials is, what is the mean of the random variable that
represents the {\em waiting time} until the first occurrence of the
event $E$. This variable has probability $p(1-p)^{k-1}$ of having
value $k$, and it is a nice excercise to deduce from this that the
mean waiting time to first occurrence of $E$ is $1/p$.
\vspace{.5in} \\

 \noindent {\bf Normal Distribution.} A {\em normal distribution} with
mean $\mu$ and variance $\sigma^{2}$ for a random variable $f$ is a
continuous distribution for which the probability that $a < f < b$ is

\[ \frac{1}{\sqrt{2 \pi \sigma}} \int_{a}^{b} e^{-((x-\mu) /  \sigma )^{2}/2}
\ dx . \]

The following facts about normal distributions are useful to know: The
plot of the {\em probability density} or integrand in this distribution
is bell-shaped. Approximately 68\% of the area of this curve lies in
the interval $\mu - \sigma$ and $\mu + \sigma$; 95\% between $\mu - 2
\sigma$ and $\mu + 2 \sigma$; and 99.9\% between $\mu-3 \sigma$ and $\mu
+ 3 \sigma$.
\vspace{.5in}\\

\noindent {\bf Central Limit Theorem. } It is an easy exercise to
show that the distribution of $K/N$, the average number of occurences
of $E$ in Bernoulli trials, approaches a normal distribution with
appropriate mean and variance ($p$ and $p(1-p)/N$) as $N$ increases.
This same limit occurs for averages of variables in much greater
generality. Statements of this kind are called {\em central limit
theorems} and there are a variety of them, giving other conditions
for which the average of a number of variables approaches a normal (or
other) distribution.
\vspace{.5in} \\

\begin{center}{\bf Exercises.} \end{center}

\begin{enumerate}

\item Two ordinary, six-sided dice are rolled. What is the expectation
of the sum of the two values showing? What is the expectation of the maximum?

\item Show that $P(ABC) = P(A) P(B | A) P(C | AB)$.
Find a general formula for events $A_{1} \ldots A_{n}$.

\item Cards are dealt to four players, thirteen to each player at
random. Compute the probability the first person holds all the aces,
given that this same person holds the ace of hearts.  

\item What is the probability, that in a group of twenty people, no
two have the same birthday? How many people would have to be present 
so that with more than a 95\% chance two people have the same birthday? 
How many people would have to be present so that with a 100\% chance 
two people have the same birthday?  

\item What is the expected waiting time until the first occurrence
of an event $E$ in an infinite sequence of Bernoulli Trials?

\item We are given three six-sided dice (call them A,B,C).
Each die is fair, but the sides are not marked in the usual way:
the sides of die A are marked 3,3,3,3,3,6,
the sides of die B are marked 2,2,2,5,5,5,
and the sides of die C are marked 1,4,4,4,4,4.
I pick a die, then you pick a die.
Then we roll, and whoever's die comes up with a higher number
wins ten dollars from the other person.
Which die should you pick, and why?
How quickly should expect to make money
if we play this game all day?

\item
A Keno ticket comes with eighty spots, numbered 1 through 80.
You mark one to fifteen spots on the ticket,
and write the amount of your wager in the corner of the ticket
(any multiple of \$1).
After you have paid this amount to the house,
the house randomly chooses twenty numbers between 1 and 80.
Your payoff is determined by the number of spots you marked
and the number of spots you managed to ``catch'' (where
you catch a spot if both you and the house choose it),
and is proportional to the size of your wager
(up to a ceiling of \$25,000).

Suppose you mark 15 spots and wager \$5.
If you catch 0 spots, you get back exactly the amount you wagered.  
If you catch 1 through 5 spots, you get nothing back at all.
If you catch 6 through 15 spots, then the payoff is
\$10, \$30, \$80, \$300 \$960, \$9600, \$25000, \$25000, \$25000, \$25000,
respectively.

Calculate, or estimate:
(a) the probability that you will catch 0 spots;
(b) the probability that you will catch 6 or more spots;
(c) the rate at which you would expect to lose money (per game) in the
long run, if you kept at it.

\bigskip
{\sf These notes were adapted from notes developed
by Prof.\ Daniel Kleitman.}

\end{enumerate} 
\end{document}
