\documentclass[12pt]{6042}
%\usepackage{eepic}
\usepackage{psfig}

\newcommand{\recn}[3]
{\setcounter{problemsetnum}{#1}
\handout{rec#1}{Notes for Recitation #1 (#2/98)}{#3}
}

%\let\pr=\Pr
%\def\av=\expect
%\let\var=\variance

\begin{document}
 
\recn{13}{5/8}{May 9, 1998 (revised May 31)}

\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{defin}
The covariance of random variables $R_1$ and $R_2$ is  
\[
\cov{R_1}{R_2} ::= \expect{R_1R_2} - \expect{R_1}\expect{R_2}.
\] 
\end{defin}

If the covariance of
 $R_1$ and $R_2$ is positive, we will say that they
are ``positively correlated'', and if their
covariance is negative we say that
they  are ``negatively correlated''.
Intuitively, positively correlated random variables tend to have
close values, while negatively correlated variables tend to have
values far apart. Independent random variables have zero correlation.



{\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} = \expect{R_1^2} - \expectsq{R_1} = \variance{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,
\begin{eqnarray*}
\cov{R_1}{R_2} & = & \expect{R_1(7-R_1)} - \expect{R_1}\expect{7-R_1}\\
& = & 7\expect{R_1} - \expect{R_1^2} - 7\expect{R_1}+\expectsq{R_1}\\
& = & - \expect{R_1^2} + \expectsq{R_1}\\
& = & - \variance{R_1} = -2\frac{11}{12}
\end{eqnarray*}
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} = \expect{R_1R_2} - \expect{R_1}\expect{R_2} =
\expect{R_1}\expect{R_2}-\expect{R_1}\expect{R_2} = 0.\]
The correlation of independent random variables is zero.

\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.  For example, let $R_1, R_2$ be
in the range $[1,3]$ such that $\pr{R_1 = i \& R_2 = j} = 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} &=& \expect{R_1R_2} - \expect{R_1}\expect{R_2} \\
&=& \sum_{i,j \in [1,3]} ij \pr{R_1 = i \& R_2 = j} - 
\Bigl(\sum_{i \in [1,3]}i \pr{R_1 = i} \Bigr)^2\\
&=& \frac{1}{8} (1+2+3+2+6+3+6+9) - \left(\frac{3}{8}(1+3) + \frac{2}{8}2
\right)^2\\
&=& 4-4 = 0
\end{eqnarray*}

\begin{theorem}
For random variables $R_1$ and $R_2$,
\[\variance{R_1+R_2} = \variance{R_1} + \variance{R_2}  + 2\cov{R_1}{R_2}.\]
\end{theorem}

{\em Proof. }
\begin{eqnarray*}
\variance{R_1+R_2} &=& \expect{(R_1 + R_2)^2} - \expectsq{R_1+R_2}\\
& = & \expect{R_1^2 + 2R_1R_2 +R_2^2} - \left( \expect{R_1}+\expect{R_2} \right)^2\\
&=& \expect{R_1^2} + 2\expect{R_1 R_2} + \expect{R_2 ^2}
- \expectsq{R_1} - 2 \expect{R_1}\expect{R_2} - \expectsq{R_2}\\
&=& \left( \expect{R_1^2} - \expectsq{R_1} \right)
+ \left ( \expect{R_2 ^2} -  \expectsq{R_2} \right) +2 (
\expect{R_1 R_2} -\expect{R_1}\expect{R_2} )\\
& = & \variance {R_1} + \variance {R_2} +2 \cov{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 
\[\variance{R_1+R_2} = \variance{R_1}+\variance{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
\[\variance{R_1+\cdots+R_n}= \variance{R_1}+ \cdots + \variance{R_n}.\]
\end{theorem}

The proof is simple and is left to the reader. (Calculations will be
easier if one defines new random variables $D_i ::= R_i - \expect{R_i}$.
Then $\variance{\sum_i R_i} = \expect{\left( \sum_i D_i \right)^2}$,
$\expect{D_i} = 0$, and $\variance{R_i} = \expect{D_i^2}$, which will
simplify the expressions.)

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} = \binom{n}{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, \ \pr{R_i = 1} = p,\mbox{ and }\pr{R_i = 0} = 1-p.\]
Now
\[ \variance{R_i} = \expect{R_i^2} - \expectsq{R_i} = p - p^2.\]
Hence from the theorem,
\[\variance{R} = \sum_{i=1}^n \variance{R_i} = n \variance{R_i} = p(1-p)n.\]


\section{Wald's Theorem}

In this section we will prove Wald's Theorem, that was stated 
without proof in lecture.
The proof will make use of the following  observation.

\begin {lemma}\label{sumgek}
Let $R$ be a random variable with range in the non-negative
integers, then
\[ \expect{R} = \sum_{k \geq 0} \pr{R \geq k}. \]
\end {lemma}

\begin{proof}
We will begin with the right-hand expression and transform it into
$\expect{R}$.

\begin{eqnarray*}
\sum_{i=0}^{\infty} \pr{R > i}
	& = & \pr{R > 0} + \pr{R > 1} + \pr{R > 2} + \ldots \\
	& = & \underbrace{\pr{R = 1} + \pr{R = 2} + \pr{R = 3} + \ldots}_{= 
\pr{R > 0}} \\
	&   & + \underbrace{\pr{R = 2} + \pr{R = 3} + \ldots}_{= \pr{R > 1}} \\
	&   & + \underbrace{\pr{R = 3} + \ldots}_{= \pr{R > 2}} \\
	& = & \pr{R = 1} + 2 \cdot \pr{R = 2} + 3 \cdot \pr{R = 3} + \ldots \\
	& = & \sum_{i=0}^{\infty} i \cdot \pr{R = i} \\
	& = & \expect{R}
\end{eqnarray*}

In the first step, the summation is rewritten with the $\ldots$
notation.  In the second step, we rewrite each term $\pr{R > i}$ as a
series; if $R$ is greater than $i$, then it must be one of $i+1$,
$i+2$, etc.  (This is where we use the fact that the range of $R$ is the set of
non-negative integers.)  Next, we sum all the resulting series, and then revert
to $\sum$ notation.  The last summation is the definition of
$\expect{R}$.
\end{proof}

We recall the statement of Wald's Theorem\footnote{
Here's a better version of Wald's theorem than the one presented in
lecture and recitation this term:

\begin{theorem}[Better Version of Wald's Theorem]
Let $Q$ be a non-negative integer valued random variable such that
$\expect{Q}$ is finite, and let $R_1, R_2, \ldots$ be a countable sequence
of random variables.  Let $T$ be the sum $R_1 + R_2 + \cdots + R_Q$.
Suppose that, conditioned on being included in the sum, every variable
$R_k$ has the same distribution as $R_1$, and also suppose that
$\expect{\abs{R_1}}$ is finite.  Then,
$\expect{T} = \expect{Q} \cdot \expect{R_1}$.
\end{theorem}

More precisely, the condition ``conditioned on being included in the sum, every
variable $R_k$ has the same distribution,'' means
\[\pr{R_k = r \mid Q \ge k} = \pr{R_1 = r \mid Q \ge 1}\]
for all integers $k \ge 1$ and real numbers $r$.  Note that
$\pr{R_1 = r \mid Q \ge 1} = \pr{R_1 = r}$,
since $Q \ge 1$ by hypothesis.

\medskip
This version has the advantage that it does not put any constraints on the
behavior of $R_k$ when $R_k$ is \emph{not} included in the sum---which
makes better sense since the behavior of $R_k$ when it is not included in
the sum is not relevant to the conclusion of the theorem.  So $R_k$ can be
defined arbitrarily---say to be zero---if it is not in the sum.  This is
natural in many examples such as Team~\ref{Waldprob} where $R_k$
describes results of the $k$th in a series of trials, and $Q$ is defined
by a stopping condition on the values of the $R_k$'s; in this case $R_k$
isn't really defined when the experiment stops before the $k$th trial.

The proof is actually simpler with $R_k = 0$ when it is not included in
the sum, since then
\[\sum_{k=1}^{Q} R_k = \sum_{k=1}^{\infty} R_k.\]
A further technical advantage of this version is that with $R_k$
unconstrained when it is not in the sum, we can restrict to sample points
consisting solely of the stopped experiments, thereby modeling the
series of trials with a countable sample space as in Handout 54.}

\begin{theorem}[Wald's Theorem]
Let $Q$ be a random variable that takes on only non-negative, integer
values and such that $\expect{Q}$ is finite.  Let $R_1, R_2, \ldots$ be a
sequence of random variables, all with the same distribution and with
$\expect{\abs{R_1}}$ finite.  Let $T$ be the sum $R_1 + R_2 + \ldots +
R_Q$.  Suppose that every variable $R_k$ is independent of the event that
it is included in the sum.  Then,
\[\expect{T} = \expect{Q} \cdot \expect{R_1}.
\]
\end{theorem}

Technical conditions abound in the previous theorem.  For example, in
simple applications such as in the one presented in lecture, $R_k$ is
completely independent of $Q$.  The more weaker, technical condition
merely that $R_k$ is ``independent of the event that it is included in the
sum'' is important in other common applications, cf.,
Team~\ref{Waldprob} below.

We let $I_k$ be an indicator variable for the event that $R_k$ ``is included
in the sum $R_1 + \ldots + R_Q$'', that is, we define $I_k$ as follows:
\[
I_k ::= \left\{\begin{array}{cl}
1 & \text{if $Q \geq k$}, \\
0 & \text{if $Q < k$}.
\end{array}
\right.
\]
Then the precise condition on the $R_k$'s is that, for any $k$, $R_k$ is
independent of $I_k$.

\begin {proof}
The indicator variables $I_k$ play an important role in this proof.
First  of all, we can rewrite $T$ as
shown below:

\begin{eqnarray*}
T	& = & R_1 + R_2 + \ldots + R_Q \\
	& = & \sum_{k=1}^\infty R_k I_k
\end{eqnarray*}

The effect of the indicator variables is to cancel out all but the
first $Q$ terms in the infinite sum.  We can now compute the expected
value of $T$ as follows:

\begin{eqnarray*}
\expect{T}	& = & \expect{ \sum_{k=1}^\infty R_k I_k}
\end{eqnarray*}


On the right, we have the expectation of an infinite sum, and we would
like to apply linearity of expectation.  Recall that linearity of
expectation holds also for infinite sums, provided that the sum is
absolutely convergent with probability one.  But for any point of our
sample space, $Q$ takes some finite value $q$, and only the indicator
variables $I_1,\ldots,I_q$ are non-zero; therefore, for every point of the
sample space all but finitely many terms of the infinite sum are zero.  So
it's OK to use the infinite version of the linearity of expectation:
\begin{eqnarray*}
\quad \quad
%	& = & \expect{\sum_{k=1}^{\infty} R_k I_k} \\
	& = & \sum_{k=1}^{\infty} \expect{R_k I_k}
\end{eqnarray*}

The third condition of Wald's Theorem is precisely that $R_k$ and
$I_k$ are independent.  Therefore, the expectation of the product is
the product of the expectations:
\begin{eqnarray*}
\quad \quad
	& = & \sum_{k=1}^{\infty} \expect{R_k} \expect{I_k} 
\end{eqnarray*}

The expected value of $R_k$ is equal to the expected value of $R_1$ by
the second condition of Wald's Theorem.  
Since it is independent of $k$, 
we can pull the term $\expect{R_1}$ outside the summation:
\begin{eqnarray*}
\quad \quad
& = & \expect{R_1} \sum_{k=1}^{\infty}\expect{I_k}.
\end{eqnarray*}

The expected value of an indicator variable like $I_k$ is the probability
that it is 1, and, by the definition of $I_k$, we have that $I_k=1$ if and
only if $Q\geq k$, so that
\begin{eqnarray*}
\quad \quad
	& = &  \expect{R_1} \sum_{k=1}^{\infty} \pr{Q \geq k}.
\end{eqnarray*}
Since $Q$ is a non-negative, integer-valued random variable, the remaining
sum is equal to $\expect{Q}$ by Lemma~\ref{sumgek}.
\begin{eqnarray*}
\quad \quad
	& = & \expect{R_1} \cdot \expect{Q}.
\end{eqnarray*}
\end{proof}

As an application of Wald's Theorem, here's a simple proof that
\begin{corollary}
The mean time to failure is the reciprocal of the probability of failure.

Namely, consider flipping a weighted coin until a head shows up.  Assume
the flips are independent.  Then
\[\expect{\mbox{number of flips to first head}} = \frac{1}{\pr{\mbox{heads on
one flip}}}.\]
\end{corollary}
\begin{proof}
Assume the probability of a head is $h$.  Regard flipping until a head
shows up as a game in which each tail flipped pays nothing and each head
pays \$1.00.  We know from Handout 54 that the probability of eventually
flipping a head is one, so with probability one, a game pays off \$1.00.
It follows that the \emph{expected} win obviously must also be \$1.00.
But by Wald's Theorem, the expected win is the expected number of flips
until a head turns up, times the expected number, $h$, of heads per flip.
That is,
\[1 = \expect{\mbox{number of flips to first head}} \cdot h.\]
\end{proof}

\iffalse
\section{Sum of Pairwise Independent Random Variables}

Let $V_1,\ldots,V_n$ be pairwise independent random variables
such that $\pr{V_i=0} =1/2$ and $\pr{V_i=1}=1/2$ (i.e. each
$V_i$ is an uniformly distributed Bernoulli variable.)
Then $\variance{\sum_i V_i} = \sum_i \variance{x_i} = n/4$, and Chebyshev
inequality implies that
\[ \pr{\abs{\sum_i V_i - n/2} \geq \epsilon n} \leq \frac 1 {4\epsilon^2
n}.\]
In particular, for $\epsilon = 1/2$,
\[\pr{\sum_i V_i = 0  \mbox{ or } \sum_i V_i = n} \leq \frac 1n . \] 
If the random variables $V_i$ are mutually independent, then the previous
bound can be strengthened to $2 \cdot 2^{-n}$.  We will see that this is
not possible in general, i.e., under the sole condition of pairwise
independence, the bound implied by Chebyshev's inequality is essentially
the best possible.

Consider independent uniformly distributed Bernoulli variables
$X_1,\ldots,X_k$.  Let $n ::= 2^k -1$; we shall define $n$ new random
variables $Y_S$, one for any non-empty subset $S \subseteq
\set{1,\dots,k}$, as follows:

\[ Y_S = \Bigl{  \begin {array}{cl}
1 & \mbox{ if } \sum_{i \in S} X_i \mbox{ is odd,}\\ 0 & \mbox{
otherwise.}  \right. \] It is easy to verify that for every non-empty $S$,
the random variable $Y_S$ is a uniformly distributed Bernoulli random
variable ($Y_S$ can be thought of as the indicator variable of the event
``make $k$ consecutively numbered coin tosses and get an odd number of
heads among the coin tosses whose numbers are in $S$.''  Such an event
happens with probability $1/2$ as long as $S$ is not empty.)

We now proceed to show that for every two different non-empty set $S \neq
T \subseteq \set{ 1,\ldots,k}$, the random variables $Y_S$ and $Y_T$ are
independent.  Fix two boolean values $b_1,b_2 \in \set{0,1}$, we want to
show that
\[ Pr (Y_S = b_1 | Y_T = b_2) =  Pr (Y_S = b_1) \]
\fi

\section{Team Problems}

\begin {problems}

\problem %1

The Petersburg Casino offers the following game: the gambler
bets a fixed wager, and then the dealer flips a fair coin
(dealers do not flip coins in US casinos, but they do in
Petersburg) until it comes up heads. The gambler receives
\$1 if the coin shows heads the first time, \$2
if it shows the first head at second toss, and in general
$\$2^{k-1}$ if the dealer tosses the coin $k$ times to get
the first head. The fixed wager is \$100,000.

\bparts

\ppart
What is the expected amount of money that the Petersburg Casino
is going to pay to a gambler that plays this game?
What about the variance?
Is it reasonable for the gambler to risk \$100,000
dollars in a game where there is a $50 \%$ chance of getting
only {\em one dollar} back (this is not really a mathematical
question: just think about that.)

\ppart
What is the probability that the gambler does not lose
money in this game, i.e. what is the probability that
he gets back from the Casino more than \$100,000?


\eparts

\problem %2
\label{Waldprob}
A Harvard student, lost in the underground corridors of MIT, finds himself
in a room containing three doors.  Door 1 leads him to freedom (out of
MIT) after an hour of travel; door 2 returns him to the same room after four
hours travel, and door 3 returns him to the room after seven hours travel.
Each time he finds himself in the room, the Harvard student picks a door
with equal probability.  Let $T$ denote the time until he finds the exit.

\bparts

\ppart Define a sequence of independent identically distributed random
variables $R_i$ and a stopping rule $Q$ such that

\begin{displaymath}
T = \sum_{i=1}^{Q}{R_i}
\end{displaymath}

\ppart Argue that $R_k$ is independent of the event that $Q\geq k$.  Is
$R_k$ independent of $Q$?

\ppart Use  Wald's Theorem to find $\expect{T}$.

\ppart Now suppose that an MIT student is also lost and finds herself in a 
similar situation to the Harvard student.  The MIT student never chooses the 
same door twice.  What is $\expect{T}$ for the MIT student?

\eparts

\problem

If a random variable has infinite expectation, then the variance
is undefined, however a random variable may have finite
expectation and infinite variance.

\bparts

\ppart 
Show an example of a random variable whose expectation is finite
but whose variance is infinite.

[It might be easier to use a random variable whose expectation is zero.]

\ppart
If you used a random variable which can assume negative values
in answering the previous question, try to find an example
of a {\em non-negative} random variable whose expectation is finite
and whose variance is infinite.

[Hint: notice that $\sum_{n=1}^\infty 1/2^{2n} =1/3$
and $\sum_{n=1}^{\infty} 1/2^n = 1$.]

\eparts


\problem

Let $X$ be a non-negative random variable with expectation
$n/2$. Markov's inequality implies that
\begin{equation}\label{eq:mark}
\pr{ X \geq \frac 23 n} \leq \frac 34 .
\end {equation}

\bparts

\ppart
Define a random variable $X$ with expectation $n/2$ such
that the above bound holds with equality.

\ppart If $X_1,\ldots,X_n$ are a collection of {\em independent} unbiased
Bernoulli variables over the same sample space, then $X = \sum_i X_i$ has
expectation $n/2$ and is non-negative, therefore the bound~\eqnref{eq:mark}
above applies.  Unfortunately it is a much larger bound than necessary in
this case.  However, under the general hypotheses for Markov's
inequality---where independence is not assumed---the
bound~\eqnref{eq:mark} is still the best one can hope for.

Define unbiased Bernoulli variables $X_1,\ldots,X_n$ on a sample space
such that for $X = \sum_{i=1}^n X_i$, the bound~\eqnref{eq:mark} holds
with equality (assume $n$ is a multiple of 3).  \hint The variables will
have to be dependent.  Define things so that $\pr{X_1= \cdots =X_n = 0}=
1/4$.

\eparts

\end {problems}

\section {Solutions}
\subsection*{Problem 1 Solution}

Let $V$ be the random variable corresponding to the amount of money
that the gambler is paid by the dealer. The distribution of
$V$ is as follows: for any $n\geq 1$,
\[ \pr { V= 2^{n-1}} = 2^{-n}, \]
where the probability refers to the event that the dealer
tosses $n-1$ tails followed by a head.
The average of $V$ is
\[ \expect{V} = \sum_{n=1}^{\infty} [2^{-n} 2^{n-1}]
= \sum_{n=1}^{\infty} 1/2 = \infty. \]
The variance is not defined for a random variable having infinite
expectation. It does not sound too bad to risk \$100,000 on
a game where we expect to win an infinite amount of money. However
the probability of recovering the money of the wager is only
\begin {eqnarray*}
 \pr { X \geq 100,000} & =& \pr { X \geq 2^{17}}\\
&=& \pr { \mbox{ there are 17 consecutive tails }}\\
& =& \frac 1 {131,072} 
\end {eqnarray*}

\subsection*{Problem 2 Solution}

We view this an experiment where at each step the student makes a choice
between three equally likely outcomes.  We define $R_i$ as the number of
hours to return to the same room, or to escape, starting at the $i$th
step.  The experiment does not end.  That is, as soon as the student
escapes, he is doomed, like Sisyphus, to be stuck back in the room and
start trying to escape again.  This ensures that there is an $i$th step
for all $i \ge 0$, and that the $R_i$ are identically distributed (they
are also independent, though this fact is not needed in applying Wald's
Theorem).  In particular, $\pr{R_i=1}=\pr{R_i=4}=\pr{R_i =7}=1/3$, and
$\expect{R_i} = (1+4+7)/3=4$.

Define $Q$ to be the number of steps from the first step until the escape
door is selected \emph{for the first time}.  Now $Q$ is geometrically
distributed with probability $1/3$ and $\expect{Q}=3$.

Assuming Wald's Theorem is applicable, we conclude
\[\expect{T} = \expect{\sum_{i=1}^Q R_i}  = 3 \times 4 = 12.\]

To justify the use of Wald's Theorem, we establish that $R_i$ is
independent of the event that $Q \geq i$.

It's worth noting that $R_i$ is \emph{not} independent of $Q$.  For
example, if $Q=i$, then it must be that the student found the escape door
at the $i$th step, and so $\pr{R_i = 1 | Q=i} =1 \neq 1/3 = \pr{R_i = 1}$.

However, suppose we are given that the student has never managed to escape
before the $i$th step, that is, that $Q \ge i$.  Then we can observe that
the experiment starting at the $i$th step has exactly the same structure
as the experiment at the first step---where we were given, implicitly,
that the student had not escaped before the first step.  So we can
conclude that the distribution of $R_i$ given $Q \ge i$ is the same as
that of $R_1$ given that $Q\ge 1$, that is, the same as $R_1$, which we
already observed is the same as $R_i$.  In other words, $R_i$ is
independent of the event that $Q \geq i$, as required.  (This informal
argument can be justified rigorously as in Handout 54 on ``Probabilities
in a Dice Game,'' by explicitly describing the sample space for the
problem along with a suitable bijection between the whole sample space and
the event $Q \geq i$.)

\medskip
Regarding the MIT student, the problem can be solved by complete
enumeration; call $A$ the door that leads out, $B$ the door that leads
back in four hours, and $C$ the door that leads back in seven hours. The
possible events are

\begin {itemize}

\item
$A$ with probability $1/3$, in which case $T=1$

\item
$BA$ with probability $\frac 12 \cdot \frac 13 = \frac 16$, in which case $T=5$;

\item
$BCA$ with probability $\frac 12 \cdot \frac 13 \cdot 1 = \frac 16$, in which case $T=12$;

\item
$CA$ with probability $\frac 12 \cdot \frac 13  = \frac 16$, in which case $T=8$;

\item
$CBA$ with probability $\frac 12 \cdot \frac 13 \cdot 1 = \frac 16$, in which
case $T=12$.

\end {itemize}

The average of $T$ this time is $\expect{T} = 39/6 = 6.5$.

\subsection*{Problem 3 Solution}

There are several possible solutions. One possibility (that solves
directly also the second question)
is to consider a random variable $V$ such that for any $n\geq 1$
we have $\pr{V = 2^n } ::= 3 \cdot 2^{-2n}$; this is a valid 
distribution since $\sum_{n=1}^\infty 3 \cdot 2^{-2n} =1$.
Then
\[ \expect{V} = \sum_{n=1}^\infty 2^n \cdot 3 \cdot 2^{-2n}
=  \sum_{n=1}^\infty 3 \cdot 2^{-n} = 3. \]
Therefore,
\[\variance{V} = \expect{V^2} - \expectsq{V} = \expect{V^2} - 9, \]
and we just have to compute the expectation of $V^2$.  For every $n \geq
1$ we have that $\pr{V^2 = 2^{2n}} = 3 \cdot 2^{-2n}$, so
\[ \expect{V^2} = \sum_{n=1}^\infty 2^{2n} \cdot 3 \cdot 2^{-2n}
= \sum_{n=1}^\infty 3 = \infty.\]

\subsection*{Problem 4 Solution}

Consider the sample space where $X_1 = \cdots = X_n = 0$ occurs with
probability $1/4$, and where for any $i=1,\ldots,n$, the event
$(X_1,\ldots,X_n) = \mbox{shift}_k (0^{n/3}1^{2n/3})$ happens with
probability $3/4n$.  The notation $\mbox{shift}_k (a_1,\ldots,a_n)$, where
$a_1,\ldots,a_n$ is a binary string, stands for the string $(a_{k+1}\cdots
a_{n}a_1\cdots a_{k})$ obtained by doing a $k$ times a cyclic shift to the
left of the string $a_1,\ldots,a_n$.  Notice that with probability exactly
$3/4$ exactly a fraction $2/3$ of the $X_i$ get value $1$, therefore
expression~\eqnref{eq:mark} is satisfied with equality.  We have to check
that for any $i$ we have $\pr {X_1 = 1} = 1/2$. This follows from the fact
that there are exactly $2n/3$ shifts such that $X_i=1$, each one happening
with probability $3/4n$; since they are disjoint events we can sum their
probability, and their sum is $1/2$.


\end{document}


