%------------------------------------------------------------------------------ %\documentclass[reqno]{amsart} \documentclass[12pt]{amsart} %\setcounter{page}{6} \usepackage[top=1in, bottom=1in, left=1in, right=1in]{geometry} \usepackage[colorlinks=true, urlcolor=blue]{hyperref} \usepackage{amssymb} \usepackage{amsmath,mathrsfs} %\oddsidemargin -0in \evensidemargin .5in %\topmargin=1.25in %\headheight 10pt \headsep 10pt \footheight 10pt \footskip 24pt %\textheight 10in \textwidth 6.5in \columnsep 10pt \columnseprule 0pt %\font\namefont=cmr10 scaled\magstep2 \font\namefont=cmr8 scaled\magstep2 \newcommand{\myindent}{\leftskip=.4in} %\voffset=-.75in \parskip=11pt %extra vertical distance for new paragraph \parindent=0in %\newtheorem{theorem}{Theorem}[section] %\newtheorem{lemma}[theorem]{Lemma} %\newtheorem{lemma}{Lemma}[section] %\newtheorem{theorem}{Theorem}[section] %\newtheorem{lemma}[theorem]{Lemma} %\newtheorem{prop}[theorem]{Proposition} %\newtheorem{cor}[theorem]{Corollary} %\newtheorem{conj}{Conjecture} \usepackage{graphicx} \usepackage{color} \usepackage{subfigure} \usepackage{amssymb} \usepackage{amsmath} \usepackage{colonequals} \usepackage{hyperref} %\usepackage{showlabels} %\usepackage[all]{xypic} %\entrymodifiers={+!!<0pt,\fontdimen22\textfont2>} \theoremstyle{definition} \newtheorem{exercise}{Exercise} \newtheorem{remark}{Remark} \renewcommand{\setminus}{\smallsetminus} \addtolength{\footskip}{17pt} %\numberwithin{table}{section} \renewcommand{\subset}{\subseteq} \renewcommand{\supset}{\supseteq} \renewcommand{\epsilon}{\varepsilon} \newcommand{\abs}[1]{\left|#1\right|} % Absolute value notation \newcommand{\absf}[1]{|#1|} % small absolute value signs \newcommand{\vnorm}[1]{\left|\left|#1\right|\right|} % norm notation \newcommand{\vnormf}[1]{||#1||} % norm notation, forced to be small \newcommand{\im}[1]{\mbox{im}#1} % Pieces of English for math mode \newcommand{\tr}[1]{\mbox{tr}#1} \newcommand{\Proj}[1]{\mbox{Proj}#1} \newcommand{\Vol}[1]{\mbox{Vol}#1} \newcommand{\Z}{\mathbf{Z}} % Blackboard notation \newcommand{\N}{\mathbf{N}} \newcommand{\E}{\mathbf{E}} \renewcommand{\P}{\mathbf{P}} \newcommand{\R}{\mathbf{R}} \newcommand{\C}{\mathbf{C}} \newcommand{\Q}{\mathbf{Q}} \newcommand{\figoneawidth}{.5\textwidth} % Image formatting parameters \newcommand{\lbreak}{\\} % Linebreak \newcommand{\italicize}[1]{\textit {#1}} % formatting commands for bibliography %\newcommand{\embolden}[1]{\textbf {#1}} \newcommand{\embolden}[1]{{#1}} \newcommand{\undline}[1]{\underline {#1}} \newcommand{\e}{\varepsilon} \renewcommand{\epsilon}{\varepsilon} %\renewcommand{\colonequals}{=} \newcommand{\Samplespace}{\Omega} %consider changing this in next revision \newcommand{\samplept}{\omega} \newcommand{\var}[1]{\mbox{var}\left(#1\right)} \thispagestyle{empty} \begin{document} \bigskip Graduate Mathematical Statistics \hfill Steven Heilman\\ \noindent\rule{6.5in}{0.4pt} %\vspace{.2cm} Please provide complete and well-written solutions to the following exercises. Due February 1, at the beginning of class. \vspace{.5cm} \begin{center} {\Large Homework 2} \end{center} \vspace{.5cm} \begin{exercise} You want to complete a set of $100$ baseball cards. Cards are sold in packs of ten. Assume that each individual card in the pack has a uniformly random chance of being any element in the full set of $100$ baseball cards. (In particular, there is a chance of getting identical cards in the same pack.) How many packs of cards should you buy in order to get a complete set of cards? That is, what is the expected number of cards you should buy in order to get a complete set of cards (rounded up to a multiple of ten)? (Hint: First, just forget about the packs of cards, and just think about buying one card at a time. Let $N$ be the number of cards you need to buy in order to get a full set of cards, so that $N$ is a random variable. More generally, for any $1\leq i\leq100$, let $N_{i}$ be the number of cards you need to buy such that you have exactly $i$ distinct cards in your collection (and before buying the last card, you only had $i-1$ distinct cards in your collection). Note that $N_{1}=1$. Define $N_{0}=0$. Then $N=N_{100}=\sum_{i=1}^{100}(N_{i}-N_{i-1})$. You are required to compute $\E N$. You should be able to compute $\E[N_{i}-N_{i-1}]$. This is the expected number of additional cards you need to buy after having already collected $i-1$ distinct cards, in order to see your $i^{th}$ new card.) \end{exercise} \begin{exercise} You are trapped in a maze. Your starting point is a room with three doors. The first door will lead you to a corridor which lets you exit the maze after three hours of walking. The second door leads you through a corridor which puts you back to the starting point of the maze after seven hours of walking. The third door leads you through a corridor which puts you back to the starting point of the maze after nine hours of walking. Each time you are at the starting point, you choose one of the three doors with equal probability. Let $X$ be the number of hours it takes for you to exit the maze. Let $Y$ be the number of the door that you initially choose. \begin{itemize} \item Compute $\E(X|Y=i)$ for each $i\in\{1,2,3\}$, in terms of $\E X$. \item Compute $\E X$. \end{itemize} \end{exercise} \begin{exercise} Let $X_{1},\ldots,X_{n}$ be continuous random variables with joint PDF $f\colon\R^{n}\to[0,\infty)$. Assume that $$f_{X_{1},\ldots,X_{n}}(x_{1},\ldots,x_{n})=\prod_{i=1}^{n}f_{X_{i}}(x_{i}),\qquad\forall\, x_{1},\ldots,x_{n}\in\R.$$ Show that $X_{1},\ldots,X_{n}$ are independent. \end{exercise} \begin{exercise}\label{exercise4} Let $\phi\colon\R\to\R$. We say that $\phi$ is \textbf{convex} if, for any $x,y\in\R$ and for any $t\in[0,1]$, we have $$\phi(tx+(1-t)y)\leq t\phi(x)+(1-t)\phi(y).$$ Let $\phi\colon\R\to\R$. Show that $\phi$ is convex if and only if: for any $y\in\R$, there exists a constant $a$ and there exists a function $L\colon\R\to\R$ defined by $L(x)=a(x-y)+\phi(y)$, $x\in\R$, such that $L(y)=\phi(y)$ and such that $L(x)\leq\phi(x)$ for all $x\in\R$. (In the case that $\phi$ is differentiable, the latter condition says that $\phi$ lies above all of its tangent lines.) (Hint: Suppose $\phi$ is convex. If $x$ is fixed and $y$ varies, show that $\frac{\phi(y)-\phi(x)}{y-x}$ increases as $y$ increases. Draw a picture. What slope $a$ should $L$ have at $x$?) \end{exercise} \begin{exercise}[\embolden{Jensen's Inequality}]\label{jensen} Let $X\colon\Samplespace\to[-\infty,\infty]$ be a random variable. Let $\phi\colon\R\to\R$ be convex. Assume that $\E\abs{X}<\infty$ and $\E\abs{\phi(X)}<\infty$. Then $$\phi(\E X)\leq \E \phi(X).$$ (Hint: use Exercise \ref{exercise4} with $y\colonequals\E X$.) Deduce the \textbf{triangle inequality}: $$\abs{\E X}\leq\E\abs{X}.$$ \end{exercise} \begin{exercise}[\embolden{Markov's Inequality}]\label{exercise5} Let $X\colon\Samplespace\to[-\infty,\infty]$ be a random variable. Then $$\P(\abs{X}\geq t)\leq\frac{\E \abs{X}}{t},\qquad\forall\,t>0.$$ (Hint: multiply both sides by $t$ and use monotonicity of $\E$.) \end{exercise} \begin{exercise}[\embolden{The Chernoff Bound}]\label{exercise7} Let $X$ be a random variable and let $r>0$. Define $M_{X}(t)\colonequals \E e^{tX}$ for any $t\in\R$. Show that, for any $t>0$, $$\P(X>r)\leq e^{-tr}M_{X}(t).$$ Consequently, if $X_{1},\ldots,X_{n}$ are independent random variables with the same CDF, and if $r,t>0$, $$\P\left(\frac{1}{n}\sum_{i=1}^{n}X_{i}>r\right)\leq e^{-trn}(M_{X_{1}}(t))^{n}.$$ For example, if $X_{1},\ldots,X_{n}$ are independent Bernoulli random variables with parameter $0
0$, $$\P\left(\frac{X_{1}+\cdots+X_{n}}{n}-p>r\right)\leq e^{-trn}( e^{-tp}[pe^{t}+(1-p)])^{n}.$$ And if we choose $t$ appropriately, then the quantity $\P\left(\frac{1}{n}\sum_{i=1}^{n}(X_{i}-p)>r\right)$ becomes exponentially small as either $n$ or $r$ become large. That is, $\frac{1}{n}\sum_{i=1}^{n}X_{i}$ becomes very close to its mean. Importantly, the Chernoff bound is much stronger than either Markov's or Cheyshev's inequality, since they only respectively imply that $$\P\left(\abs{\frac{X_{1}+\cdots+X_{n}}{n}-p}>r\right)\leq \frac{2p(1-p)}{r}, % E|X-p| = p (1-p) + (1-p)p=2p(1-p) \quad\P\left(\abs{\frac{X_{1}+\cdots+X_{n}}{n}-p}>r\right)\leq \frac{p(1-p)}{nr^{2}}.$$ % var(X-p)= E(X-p)^2 = p(1-p)^2+(1-p)p^2= p(1-p)[1-p+p]=p(1-p) \end{exercise} \begin{exercise}[\embolden{Confidence Intervals}] Among $625$ members of a bank chosen uniformly at random among all bank members, it was found that $25$ had a savings account. Give an interval of the form $[a,b]$ where $0\leq a,b\leq625$ are integers, such that with about $95\%$ certainty, if we sample $625$ bank members independently and uniformly at random (from a very large bank membership), then the number of these people with savings accounts lies in the interval $[a,b]$. (Hint: if $Y$ is a standard Gaussian random variable, then $\P(-2\leq Y\leq 2)\approx.95$.) \end{exercise} \begin{exercise}[\embolden{Hypothesis Testing}] Suppose we run a casino, and we want to test whether or not a particular roulette wheel is biased. Let $p$ be the probability that red results from one spin of the roulette wheel. Using statistical terminology, ``$p=18/38$'' is the null hypothesis, and ``$p\neq 18/38$'' is the alternative hypothesis. (On a standard roulette wheel, 18 of the 38 spaces are red.) For any $i\geq1$, let $X_{i}=1$ if the $i^{th}$ spin is red, and let $X_{i}=0$ otherwise. Let $\mu\colonequals\E X_{1}$ and let $\sigma\colonequals\sqrt{\mathrm{var}(X_{1})}$. If the null hypothesis is true, and if $Y$ is a standard Gaussian random variable $$\lim_{n\to\infty}\P\left(\,\abs{\frac{X_{1}+\cdots+X_{n}-n\mu}{\sigma\sqrt{n}}}\geq2\right)=\P(\abs{Y}\geq2)\approx.05.$$ To test the null hypothesis, we spin the wheel $n$ times. In our test, we reject the null hypothesis if $\abs{X_{1}+\cdots+X_{n}-n\mu}>2\sigma\sqrt{n}$. Rejecting the null hypothesis when it is true is called a type $I$ error. In this test, we set the type $I$ error percentage to be $5\%$. (The type $I$ error percentage is closely related to the p-value.) Suppose we spin the wheel $n=3800$ times and we get red $1868$ times. Is the wheel biased? That is, can we reject the null hypothesis with around $95\%$ certainty? \end{exercise} \begin{exercise} A community has $m>0$ families. Each family has at least one child. The largest family has $k>0$ children. For each $i\in\{1,\ldots,k\}$, there are $n_{i}$ families with $i$ children. So, $n_{1}+\cdots+n_{k}=m$. Choose a child randomly in the following two ways. \textbf{Method 1}. First, choose one of the families uniformly at random among all of the families. Then, in the chosen family, choose one of the children uniformly at random. \textbf{Method 2}. Among all of the $n_{1}+2n_{2}+3n_{3}+\cdots+kn_{k}$ children, choose one uniformly at random. What is the probability that the chosen child is the first-born child in their family, if you use Method 1? What is the probability that the chosen child is the first-born child in their family, if you use Method 2? \end{exercise} % %\begin{exercise}\label{exercise8} %Let $Y_{1},Y_{2},\ldots\colon\Samplespace\to\R$ be random variables that converge almost surely to a random variable $Y\colon\Samplespace\to\R$. Show that $Y_{1},Y_{2},\ldots$ converges in probability to $Y$ in the following way. %\begin{itemize} %\item For any $\epsilon>0$ and for any positive integer $n$, let %$$A_{n,\epsilon}\colonequals\bigcup_{m=n}^{\infty}\{\omega\in\Samplespace\colon \abs{Y_{m}(\omega)-Y(\omega)}>\epsilon\}.$$ %Show that $A_{n,\epsilon}\supset A_{n+1,\epsilon}\supset A_{n+2,\epsilon}\supset\cdots$. %\item Show that $\P(\cap_{n=1}^{\infty}A_{n,\epsilon})=0$. %\item Using Continuity of the Probability Law, deduce that $\lim_{n\to\infty}\P(A_{n,\epsilon})=0$. %\end{itemize} % %Now, show that the converse is false. That is, find random variables $Y_{1},Y_{2},\ldots$ that converge in probability to $Y$, but where $Y_{1},Y_{2},\ldots$ do not converge to $Y$ almost surely. %\end{exercise} \begin{exercise}\label{exercise8.1} Let $0