[math] \newcommand{\indexmark}[1]{#1\markboth{#1}{#1}} \newcommand{\red}[1]{\textcolor{red}{#1}} \newcommand{\NOTE}[1]{$^{\textcolor{red}\clubsuit}$\marginpar{\setstretch{0.5}$^{\scriptscriptstyle\textcolor{red}\clubsuit}$\textcolor{blue}{\bf\tiny #1}}} \newcommand\xoverline[2][0.75]{% \sbox{\myboxA}{$\m@th#2$}% \setbox\myboxB\null% Phantom box \ht\myboxB=\ht\myboxA% \dp\myboxB=\dp\myboxA% \wd\myboxB=#1\wd\myboxA% Scale phantom \sbox\myboxB{$\m@th\overline{\copy\myboxB}$}% Overlined phantom \setlength\mylenA{\the\wd\myboxA}% calc width diff \addtolength\mylenA{-\the\wd\myboxB}% \ifdim\wd\myboxB\lt\wd\myboxA% \rlap{\hskip 0.35\mylenA\usebox\myboxB}{\usebox\myboxA}% \else \hskip -0.5\mylenA\rlap{\usebox\myboxA}{\hskip 0.5\mylenA\usebox\myboxB}% \fi} \newcommand{\smallfrac}[2]{\scalebox{1.35}{\ensuremath{\frac{#1}{#2}}}} \newcommand{\medfrac}[2]{\scalebox{1.2}{\ensuremath{\frac{#1}{#2}}}} \newcommand{\textfrac}[2]{{\textstyle\ensuremath{\frac{#1}{#2}}}} \newcommand{\nsum}[1][1.4]{% only for \displaystyle \mathop{% \raisebox {-#1\depthofsumsign+1\depthofsumsign} \newcommand{\tr}{\operatorname{tr}} \newcommand{\e}{\operatorname{e}} \newcommand{\B}{\operatorname{B}} \newcommand{\Bbar}{\xoverline[0.75]{\operatorname{B}}} \newcommand{\pr}{\operatorname{pr}} \newcommand{\dd}{\operatorname{d}\hspace{-1pt}} \newcommand{\E}{\operatorname{E}} \newcommand{\V}{\operatorname{V}} \newcommand{\Cov}{\operatorname{Cov}} \newcommand{\Bigsum}[2]{\ensuremath{\mathop{\textstyle\sum}_{#1}^{#2}}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\card}{\#} \newcommand{\Conv}{\mathop{\scalebox{1.1}{\raisebox{-0.08ex}{$\ast$}}}}% \usepackage{pgfplots} \newcommand{\filledsquare}{\begin{picture}(0,0)(0,0)\put(-4,1.4){$\scriptscriptstyle\text{\ding{110}}$}\end{picture}\hspace{2pt}} \newcommand{\mathds}{\mathbb}[/math]

\label{PROBL-SIMPLE-CHERNOFF}(Classic example for a Chernoff bound) Let [math]Y_1,\dots,Y_n[/math] be independent Bernoulli random variables with [math]\P[X_i=1]=p\in[0,1][/math] and [math]Y=Y_1+\cdots+Y_n[/math]. Let [math]\delta \gt 0[/math].

• Show that [math]\E(\exp(tY_i))\leqslant\exp(p(\exp(t)-1))[/math] holds for every [math]t \gt 0[/math].
• Use Lemma to conclude the following classic Chernoff bound
  [[math]] \P\bigl[X\geqslant(1+\delta)np\bigr]\leqslant\Bigl(\smallfrac{\e^{\delta}}{(1+\delta)^{1+\delta}}\Bigr)^{np}. [[/math]]
  { \small Hint: It is often not necessary to compute the infimum in Lemma explicitly. Here, one can for example simply choose [math]t=\log(1+\delta)[/math]. }
• Assume you are rolling a fair dice [math]n[/math] times. Apply (ii) to estimate the probability to roll a six in at least 70\% of the experiments.
• Compare the estimate of (ii) with what you get when applying the Markov bound respectively the Chebychev bound, instead. Run a simulation of the experiment to test how tight the predictions of the three bounds are.