\documentclass[11pt,twoside]{article}   
\usepackage{latex-macros/course}

%\hidesolutions         
%\showsolutions
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{11}                    % !! start the paper

\begin{problem}
The Weak Law of Large Numbers in \href{
http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln13-14.pdf}
{Notes 13-14} was given for a sequence $G_1, G_2, \dots$ of pairwise
independent random variables with the same mean and variance.  We can
generalize the Law to sequences of pairwise independent random variables,
possibly with \emph{different} means and variances, as long as their
variances are bounded by some constant.

\begin{theorem*}[Generalized Pairwise Independent Sampling]
Let $X_1, X_2, \dots$ be a sequence of pairwise independent random
variables such that $\variance{X_i} \leq b$ for some $b\geq 0$ and all
$i\geq 1$.  Let
\begin{align*}
A_n & \eqdef \frac{X_1 + X_2 + \cdots + X_n}{n},\\
\mu_n & \eqdef \expect{A_n}.
\end{align*}
Then for every $\epsilon > 0$,
\begin{equation}\label{gpis}
\pr{\abs{A_n - \mu_n} > \epsilon} \leq \frac{b}{\epsilon^2} \cdot \frac{1}{n}.
\end{equation}
\end{theorem*}

\begin{problemparts}
\problempart  Prove the Generalized Pairwise Independent Sampling Theorem. 
\hint The proof of the Pairwise Independent Sampling Theorem from
the Notes is repeated in the Appendix.

\solution{Essentially identical to the proof attached, except that
$\variance{G_i}$ gets replaced by $b$, and the equality becomes $\leq$
where the $b$ is first used.}

\problempart Conclude
\begin{corollary*}[Generalized Weak Law of Large Numbers]

For every $\epsilon > 0$,
\[
\lim_{n \rightarrow \infty}
        \pr{\abs{A_n - \mu_n}  > \epsilon} = 0.
\]
\end{corollary*}

\solution{For any fixed $\epsilon$, the righthand side of~(\ref{gpis})
approaches 0 as $n$ approaches infinity.}

\end{problemparts}
\end{problem}


%F01 pset10

\begin{problem}
A gambler has been studying the roulette wheel in a Las Vegas casino over
a long period of time, and his data confirms that the wheel is biased to
come up on a red number about 51\% of the time.  Since a bet on red pays
even money (bet \$1 and either lose it, or win and get back \$2), he
realizes the odds are in his favor.

So with high hopes and an initial stake of \$10,000, the gambler aims to
turn his stake into \$1,000,000.  He plans simply to continue making \$100
bets on red until either he is ahead the \$1,000,000, or he goes bankrupt.
He considers bankruptcy very unlikely because the odds are in his favor,
and the bets are small enough relative to his initial stake that he can
withstand a long run of losses.

\bparts

\ppart 
Based on this description, describe a reasonable probability space to
model this situation.

\solution{
An easy way to describe an appropriate sample space is to keep track of
the gambler's stake.  So sample points will be all the finite sequences of
nonnegative multiples of 100, that
\begin{itemize}
\item start at 10,000,
\item end at the first occurrence of either 0 or 1,000,000,
\item have successive integers in the sequence differ by exactly 100.
\end{itemize}
For example, the sample point describing two initial wins, followed by 102
losses and bankruptcy would be the length 105 sequence
\[
(10000, 10100,10200, 10100,10000,9900,9800,\dots,200,100,0).
\]
The sample point corresponding to his winning every bet until he reaches
his goal would the length 9,900 sequence
\[
(10000, 10100,10200, 10300,10400,\dots, 999800, 999900, 1000000).
\]
The probability of an outcome is defined to be $(0.51)^k(0.49)^j$ where
$k$ is the number of increases by 100, and $j$ is the number of decreases
by 100.  Note that either $j-k = 100$ for sample points that lead to
bankruptcy or $k-j = 9,900$ for those leading to \$1,000,000.}

\ppart\label{ep} Describe a positive constant, $\epsilon$, such that, at
any point during his play when the gambler has not gone bankrupt, there is
a probability of at least $\epsilon$ that he will reach his goal of
\$1,000,000 within the next 9,999 bets.

\solution{ $\epsilon \eqdef (0.51)^{9999}$ will do, since even if the
gambler's stake was down to \$100, there is still this much probability
that he will win the next 9,999 bets in a row and reach his goal of
\$1,000,000.}

\ppart\label{rn} Conclude that the probability that the gambler bets $n\geq 9,999$
or more times before the game ends is $O(r^n)$ for some constant $r < 1$.

\solution{Let $r \eqdef (1-\epsilon)^{1/9999}$.

The derivation of this $r$ goes as follows:

By part~(\ref{ep}) the probability that the gambler reaches his \$1,000,000 goal
during his first 9,999 bets is \emph{at least} $\epsilon$.  So the
probability that the game does not end before the 9,999th bet is \emph{at
most} $1-\epsilon$.

Similarly, the conditional probability that the game does not end before
completion of the another 9,999 bets, given that it hasn't already ended
during the first 9,999 bets, is also $1-\epsilon$.  So the probability
that the game does not end before the $2\cdot 9,999$th bet is at most
$(1-\epsilon)^2$.  In general, probability that the game does not end
before the $k \cdot 9,999$th bet is at most $(1-\epsilon)^k$.

Let $m \eqdef \floor{n/9999}$.  Now $m \cdot 9999 \leq n$, so
\begin{align*}
\pr{n\ \text{or more bets}} & \leq \pr{m \cdot 9999\ \text{or more bets}}\\
          & \leq (1-\epsilon)^m\\
          & = (1-\epsilon)^{\floor{n/9999}}\\
          & \leq (1-\epsilon)^{(n/9999)-1}\\
          & = (1-e)^{-1} \cdot (1-\epsilon)^{(n/9999)}\\
          & = (1-e)^{-1} \cdot r^{n} =O(r^n).
\end{align*}
}

\ppart Conclude that the probability that he bets forever---without either
going bankrupt or reaching his \$1,000,000 goal---is zero.

\solution{The probability that the Gambler bets forever is less than the
probability that he makes at least $n$ bets, for any $n \in \naturals$.
So by part~(\ref{rn}), the probability the Gambler bets forever is $\leq c
\cdot r^n$ for some constant $c>0$ and every $n$.  But $r<1$, so $r^n \to
0$ as $n \to \infty$, which implies that the probability that the gambler
bets forever cannot be greater than 0.}

\ppart The ``high hopes'' of the Gambler overlook some difficulties with
his strategy.  Is he really very likely to win?  How long will it take?
\hint $\paren{0.49/0.51}^{100} \approx 0.018$.

\solution{He has a 98\% chance of winning: more than $1-
\paren{0.49/0.51}^{100}$ using the formula~(\ref{biaswinsimp}) bounding
the probability of getting an intended profit in an unfair game.  To apply
the formula, we reverse the roles of $T$ and $n$ to turn the favorable
game into an unfair one.  This turns into a game with probability 0.49 of
winning a bet.  Since the bets are \$100, we consider \$100 to be a unit
bet, so the Gambler's starting stake in the role-reversed game is 9900
units with an aim to win 100 units.  Now the probability of a win in this
reversed game is a most $\paren{0.49/0.51}^{100} \approx 0.018$; winning
the reversed game corresponds to going bankrupt in the original game, so
his probability of winning the real game is $\geq 1 - 0.018 \geq 0.98$.

It follows from the formula~(\ref{bias-time}) for expected number of bets
(with $T=10000, n=100, p = 0.51$, and $\pr{\text{win} \geq 0.98}$ that he
can expect to make nearly half a million bets before winning, however.}

\eparts
\end{problem}


\begin{problem}
A new political journal announces as part of its editorial policy that
only poll results identifying a candidate preferred by more than half of
the voter at the 95\% confidence level will be acceptable for publication.
They will, however, publish any such poll that identifies the leading
candidate at this confidence level.  The editors reason that under this
policy, their readership can be confident that at most 5\% of their
listings of leading candidates will be incorrect.

The Republication National Committee plans to finesse the journal's policy
and make several Republican candidates who are trailing in tight races
appear to be in the lead.  Namely, the Committee identifies 200 districts
in which the Republican candidate is actually preferred by slightly fewer
than half of the voters in their districts.  It instructs each of the
managers in these district campaigns to conduct an \emph{honest},
\emph{random} poll of voter preference in their district.  The poll should
involve the minimum number of voters ensuring, at the 95\% confidence
level, that the fraction of voters in the poll who prefer the Republican
candidate will be less than 1\% larger than the actual fraction of voters
in the district who prefer the Republican candidate.

The Committee plans to submit to the journal the results of just those
polls where 51\% or more of the voters polled prefer the Republican
candidate.  The Committee expects that this will happen in around 5\% of
the polls.  That is, around 10 polls will show, at the 95\% confidence
level, that the Republican candidate has more than half the votes in his
district, when in fact he does not.

So the journal will publish its 95th\%-confidence-level list of leading
candidates, and its list will be \emph{wrong about every one} of the 10 or
so candidates whose polls are submitted by the Committee.

Will this strategy by the National Committee work?  If not explain why.
If so, discuss the fallacy in the editors' reasoning. 

\solution{Yes, the strategy will work.

Even though all the several hundred Republican candidates are slightly
behind in their campaigns, around 5\% of the poll results can be expected
to be more than 1\% larger than the actual fraction who prefer the
Republican.  So nearly 5\% of the polls will estimate that the Republican
is preferred by at least 51\% of the voters, when in fact the Republican
is preferred by slightly less than 50\%.

The editors have confused the nature of statistical confidence levels with
probability: confidence at the 95\% level does \textbf{not} mean that
there is only 1 chance in 20 that a poll is right.  It doesn't even make
sense to talk about the probability of a real-world fact such as which
candidate is leading.  We can only say that our prediction based on a
random sample has probability 0.95 of being right.  This means that if we
took many samples and made predictions based on each sample, there is a
high probability that 95\% of our predictions would be right.  But when
the National Committee selects just those sample results it likes, the
confidence level we assign to those results is no longer relevant.

There really is no clear alternative policy the journal editors could
adopt that would overcome this kind of problem, even if there wasn't a
National Committee trying to mislead readers.  For example, in medical
trials, there are many more than 200 ``alternative'' therapies being
evaluated by proponents who may be gullible, but are genuinely honest.
Nevertheless, at the 95\% confidence level, we can expect 10 of the 200
evaluations of useless or even damaging alternative therapies to yield
positive results.  The remaining 190 medical trials would not be submitted
for publication by honest proponents because the trials did not show
positive results at the 95\% level.  But the 10 that did would be
submitted by honest medical testers with no intention to mislead.

This is why, unless there is a explanation of \emph{why} a therapy works,
scientists and doctors usually doubt results claiming to confirm the
efficacy of some mysterious therapy at a high confidence level.}

\end{problem}


% fall02 final exam
%{\bf EXPECTATION, INFINITE VARIANCE, SERIES}

\begin{problem}
Let $R$ be a positive integer valued random variable such that
\[
f_R(n)  = \frac{1}{cn^3},
\]
where
\[
c \eqdef \sum_{n=1}^{\infty} \frac{1}{n^3}.
\]

\begin{problemparts}

\problempart \label{exf} Prove that $\expect{R}$ is finite.

\solution{
\begin{align*}
\expect{R} \eqdef & \sum_{n \in \naturals^{+}} n \cdot \frac{1}{cn^3}\\
 = & \sum_{n \in \naturals^{+}} \frac{1}{cn^2}\\
 < &\ 1+\int_{1}^{\infty} \frac{1}{cn^2}\\
 = &\ 1 + \frac{1}{2c}\\
< &\ \infty.
\end{align*}
}

\problempart Prove that $\variance{R}$ is infinite.

\solution{
Since
\[
\variance{R} = \expect{R^2} - \expectsq{R},
\]
and $\expectsq{R} < \infty$ by part~(\ref{exf}), we need only show
that $\expect{R^2} = \infty$.  But
\begin{align*}
\expect{R^2} \eqdef & \sum_{n \in \naturals^{+}} n^2\frac{1}{cn^3}\\
 = & \sum_{n \in \naturals^{+}} \frac{1}{cn}\\
 = & \lim_{n \to \infty} \frac{1}{c} \cdot H_n\\
 = &\ \infty.
\end{align*}
}

\end{problemparts}
\end{problem}


\appendix

\section{Appendix}
\setcounter{secnumdepth}{0}

The \emph{probability density function (pdf)} for a random variable, $R$, is
the function $f_R : \range{R} \to [0,1]$ defined by:
\[
f_R(x) \eqdef \pr{R = x}.
\]

%% expectation formulas
The \emph{expectation} of random variable, $R$, is:
\begin{equation*}%\label{expsum2}
\expect{R} \eqdef \sum_{r \in \range{R}} r \cdot f_R(x)
\end{equation*}

\iffalse

If $R$ has codomain $\naturals$, then
\begin{equation*}
\expect{R}= \sum_{r \in \naturals} \pr{R > r}
\end{equation*}

The \emph{conditional expectation}, $\expcond{R}{A}$, of a
random variable, $R$, given event, $A$, is
\begin{equation}\label{defcondexp}
\expcond{R}{A} \eqdef \sum_r r \cdot\prcond{R=r}{A}.
\end{equation}

\begin{theorem*}
[Law of Total Expectation]
If the sample space is the disjoint union of events $A_1,A_2,\cdots$,
then
\[
\expect{R} = \sum_i \expcond{R}{A_i} \pr{A_i}.
\]
\end{theorem*}
\fi

Random variables $R_1, R_2, \dots$ are \emph{mutually independent} iff
\[
\pr{\lgintersect_{i} [R_i = x_i]} = \prod_{i} \pr{R_i = x_i},
\]
for all $x_1, x_2, \dots \in \reals$.  They are \emph{$k$-wise
independent} iff $\set{R_i \suchthat i\in J}$ are mutually independent for
all subsets $J \subset \naturals$ with $\card{J} = k$.

\iffalse

The Binomial Distribution with parameters $n,p$ is the distribution of the
sum $B_{n,p} \eqdef \sum_{i=1}^n X_i$ where $X_1,\dots,X_n$ are mutually
independent Bernoulli (indicator) variables with $\pr{X_i = 1} = p$.  It
has pdf
\[
f_{n,p}(k) \eqdef \binom{n}{k} p^k q^{n-k}
\]
where $q \eqdef 1-p$.
\begin{align*}
\expect{B_{n,p}} = & np,\\
\variance{B_{n,p}}  = & npq.
\end{align*}
\fi

\begin{theorem*} [Expectation of a Product]
If  $R_1, R_2, \dots, R_n$ are mutually independent, then
\[
\expect{R_1 \cdot R_2 \cdots R_n} = 
\expect{R_1} \cdot \expect{R_2} \cdots \expect{R_n}.
\]
\end{theorem*}


\begin{theorem*}
In the Gambler's Ruin game with probability $p$ of winning
each individual bet, with initial capital, $n$, and goal, $T$,
\begin{align}
\pr{\text{the gambler is a winner in a fair game}} = & \frac{n}{T},
        & \text{(\ie $p = 1/2$)}\label{fairwin}\\
\pr{\text{the gambler is a winner a biased game}} = &
        \frac{(q/p)^n-1}{(q/p)^T -1}. & \text{(\ie $p \neq 1/2$)}\label{biaswin}
\end{align}

\begin{corollary*}
If the game is unfair, \ie $p< 1/2$,
\begin{equation}\label{biaswinsimp}
\pr{\text{the gambler is a winner in an unfair game}} < \left(\frac{p}{q}
\right)^m,
\end{equation}
where $m \eqdef T-n$.
\end{corollary*}

Let $Q$ be the number of bets till the game ends.
\begin{equation}\label{bias-time}
\expect{\text{$Q$ in a biased game}} =
\frac{\pr{\text{gambler is a winner}}T-n}{2p-1}.
\end{equation}

\begin{equation}
\label{Tn}
\expect{\text{$Q$ in a fair game}} = n(T-n).
\end{equation}

\end{theorem*}



%%%%%%%%%%%%%%%%%%%%%%%%% VARIANCE %%%%%%%%%%%%%%%%%%%%%%%%%%%%
The \emph{variance}, $\variance{R}$, of a random variable, $R$, is:
\[
\variance{R} \eqdef \expect{(R - \expect{R})^2}.
\]
Variance can also be equivalently defined as:
\[
\variance{R}\eqdef \expect{R^2} - \expectsq{R},
\]

\begin{lemma*}
For $a,b \in \reals$,
\begin{equation}\label{a2v}
\variance{aR+b} = a^2\variance{R}
\end{equation}
\end{lemma*}

\begin{theorem}\label{th:varsum}
If $R_1, R_2, \ldots, R_n$ are \emph{pairwise} independent random
variables, then
\[
\variance{R_1 + R_2 + \cdots + R_n} = \variance{R_1} + \variance{R_2} +
  \cdots + \variance{R_n}.
\]
\end{theorem}


%%%%%%%%%%%%%%%%%%%%%%%%%% MARKOV %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{theorem*}[Markov's Theorem]
  If R is a nonnegative random variable, then for all $x > 0$
  \begin{displaymath}
    \pr{R \geq x} \leq \frac{\expect{R}}{x}.
  \end{displaymath}
\end{theorem*}
An alternative formulation is
\[
\pr{R \geq x\expect{R}} \leq \frac{1}{x}.
\]


%%%%%%%%%%%%%%%%%%%%%%%% Chebyshev %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{theorem*}[Chebyshev]
Let $R$ be a random variable, and let $x$ be a positive real number.
Then
\begin{equation}\label{Chb}
\pr{\abs{R - \expect{R}} \geq x} \leq \frac{\variance{R}}{x^2}.
\end{equation}
\end{theorem*}
An alternative formulation is
\[
\pr{\abs{R - \expect{R}} \geq x\sigma_R} \leq \frac{1}{x^2},
\]
where $\sigma_R \eqdef \sqrt{\variance{R}}$ is the standard deviation of
$R$.


\begin{theorem*}[Pairwise Independent Sampling]
Let
\[
A_n \eqdef \frac{\sum_{i=1}^n G_i}{n}
\]
where $G_1, \dots, G_n$ are pairwise independent random variables with the
same mean, $\mu$, and deviation, $\sigma$.  Then
\begin{equation}\label{Sndev}
\pr{\abs{A_n - \mu} > x} \leq 
\paren{\frac{\sigma}{x}}^2 \cdot \frac{1}{n}.
\end{equation}
\end{theorem*}

\begin{proof}
By linearity of expectation,
\[
\expect{A_n} = \frac{\expect{\sum_{i=1}^n G_i}}{n}
   = \frac{\sum_{i=1}^n \expect{G_i}}{n}
   = \frac{n\mu}{n} = \mu.
\]

Since the $G_i$'s are pairwise independent, their variances will also add,
so
\begin{align*}
\variance{A_n}  = & \paren{\frac{1}{n}}^2 \variance{\sum_{i=1}^n G_i}
                        & \text{(by~(\ref{a2v}))}\\
 = & \paren{\frac{1}{n}}^2 \sum_{i=1}^n \variance{G_i}
                        & \text{(by Theorem~\ref{th:varsum})}\\
 = & \paren{\frac{1}{n}}^2 n\sigma^2\\
 = & \frac{\sigma^2}{n}.
\end{align*}

Now letting $R$ be $A_n$ in Chebyshev's Bound~(\ref{Chb})
yields~(\ref{Sndev}), as required.

\end{proof}

\end{document}


\iffalse

\begin{problem}
Prove that in an \emph{unbounded} fair game, where the Gambler plays until
he is broke no matter how much his stake increases in the meantime, the
Gambler is \emph{sure} to go broke, but the expected number of bets before
he goes broke is infinite.

\solution{
Directly from Notes 13-14:

\begin{lemma}\label{go broke}
If the gambler starts with one or more dollars and plays a fair game until
he is broke, then he will go broke with probability 1.
\end{lemma}

\begin{proof}
If the gambler has initial capital $n$ and goes broke in a game without
reaching a goal $T$, then he would also go broke if he were playing and
ignored the goal.  So the probability that he will lose if he keeps
playing without stopping at any goal $T$ must be at least as large as the
probability that he loses when he has a goal $T>n$.

But we know that in a fair game, the probability that he loses is $1 -
n/T$.  This number can be made arbitrarily close to 1 by choosing a
sufficiently large value of $T$.  Hence, the probability of his losing
while playing without any goal has a lower bound arbitrarily close to 1,
which means it must in fact be 1.
\end{proof}

So even if the gambler starts with a million dollars and plays a perfectly
fair game, he will eventually lose it all with probability 1.

\begin{lemma}\label{play forever}
If the gambler starts with one or more dollars and plays a fair game until
he goes broke, then his expected number of plays is infinite.
\end{lemma}

\begin{proof}
Consider the gambler's ruin game where the gambler starts with initial
capital $n$, and let $u_n$ be the expected number of bets for
the \emph{unbounded} game to end.  Also, choose any $T \geq n$, and as
above, let $e_n$ be the expected number of bets for the game to end when
the gambler's goal is $T$.

The unbounded game will have a larger expected number of bets compared to
the bounded game because, in addition to the possibility that the gambler
goes broke, in the bounded game there is also the possibility that the
game will end when the gambler reaches his goal, $T$.  That is,
\[
u_n \geq e_n.
\]
So by~(\ref{Tn}), 
\[
u_n \geq n(T-n).
\]
But $n \geq 1$, and $T$ can be any number greater than or equal to $n$, so
this lower bound on $u_n$ can be arbitrarily large.  This implies that
$u_n$ must be infinite.

Now by Lemma~\ref{go broke}, with probability 1, the unbounded game ends
when the gambler goes broke.  So the expected time for the unbounded game
to \emph{end} is the \emph{same} as the expected time for the gambler to
\emph{go broke}.  Therefore, the expected time to go broke is infinite.
\end{proof}

In particular, even if the gambler starts with just one dollar, his
expected number of plays before going broke is infinite!  Of course, this
does not mean that it is likely he will play for long.  For example, there
is a 50\% chance he will lose the very first bet and go broke right away.

Lemma~\ref{play forever} says that the gambler can ``expect'' to play
forever, while Lemma~\ref{go broke} says that with probability 1 he will
go broke.  These Lemmas sound contradictory, but our analysis showed that
they are not.
}
\end{problem}
\fi
