exercise:Dfadfac430: Difference between revisions

From Stochiki
(Created page with "<div class="d-none"><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...")
 
No edit summary
 
Line 1: Line 1:
<div class="d-none"><math>
<div class="d-none"><math>
\newcommand{\indexmark}[1]{#1\markboth{#1}{#1}}
\newcommand{\smallfrac}[2]{\frac{#1}{#2}}
\newcommand{\red}[1]{\textcolor{red}{#1}}
\newcommand{\medfrac}[2]{\frac{#1}{#2}}
\newcommand{\NOTE}[1]{$^{\textcolor{red}\clubsuit}$\marginpar{\setstretch{0.5}$^{\scriptscriptstyle\textcolor{red}\clubsuit}$\textcolor{blue}{\bf\tiny #1}}}
\newcommand{\textfrac}[2]{\frac{#1}{#2}}
\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<\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{\tr}{\operatorname{tr}}
\newcommand{\e}{\operatorname{e}}
\newcommand{\e}{\operatorname{e}}
\newcommand{\B}{\operatorname{B}}
\newcommand{\B}{\operatorname{B}}
\newcommand{\Bbar}{\xoverline[0.75]{\operatorname{B}}}
\newcommand{\Bbar}{\overline{\operatorname{B}}}
\newcommand{\pr}{\operatorname{pr}}
\newcommand{\pr}{\operatorname{pr}}
\newcommand{\dd}{\operatorname{d}\hspace{-1pt}}
\newcommand{\dd}{\operatorname{d}\hspace{-1pt}}
Line 33: Line 12:
\newcommand{\V}{\operatorname{V}}
\newcommand{\V}{\operatorname{V}}
\newcommand{\Cov}{\operatorname{Cov}}
\newcommand{\Cov}{\operatorname{Cov}}
\newcommand{\Bigsum}[2]{\ensuremath{\mathop{\textstyle\sum}_{#1}^{#2}}}
\newcommand{\Bigsum}[2]{\mathop{\textstyle\sum}_{#1}^{#2}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\card}{\#}
\newcommand{\card}{\#}
\newcommand{\Conv}{\mathop{\scalebox{1.1}{\raisebox{-0.08ex}{$\ast$}}}}%
\renewcommand{\P}{\operatorname{P}}
\renewcommand{\L}{\operatorname{L}}
\newcommand{\mathds}{\mathbb}</math></div>


\usepackage{pgfplots}
(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 > 0</math>.
\newcommand{\filledsquare}{\begin{picture}(0,0)(0,0)\put(-4,1.4){$\scriptscriptstyle\text{\ding{110}}$}\end{picture}\hspace{2pt}}
\newcommand{\mathds}{\mathbb}</math></div>
\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 > 0</math>.
<ul style="list-style-type:lower-roman"><li> Show that <math>\E(\exp(tY_i))\leqslant\exp(p(\exp(t)-1))</math> holds for every <math>t > 0</math>.
<ul style="list-style-type:lower-roman"><li> Show that <math>\E(\exp(tY_i))\leqslant\exp(p(\exp(t)-1))</math> holds for every <math>t > 0</math>.


</li>
</li>
<li> Use [[#CHERNOFF-RECEIPE |Lemma]] to conclude the following classic Chernoff bound
<li> Use [[guide:B846f441d7#CHERNOFF-RECEIPE |Lemma]] to conclude the following classic Chernoff bound


<math display="block">
<math display="block">
Line 51: Line 29:
</math>
</math>


{
''Hint: ''It is often not necessary to compute the infimum in [[guide:B846f441d7#CHERNOFF-RECEIPE |Lemma]] explicitly. Here, one can for example simply choose <math>t=\log(1+\delta)</math>.
\small
 
''Hint: ''It is often not necessary to compute the infimum in [[#CHERNOFF-RECEIPE |Lemma]] explicitly. Here, one can for example simply choose <math>t=\log(1+\delta)</math>.
}


</li>
</li>
<li> 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.
<li> 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.


</li>
</li>

Latest revision as of 02:14, 2 June 2024

[math] \newcommand{\smallfrac}[2]{\frac{#1}{#2}} \newcommand{\medfrac}[2]{\frac{#1}{#2}} \newcommand{\textfrac}[2]{\frac{#1}{#2}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\e}{\operatorname{e}} \newcommand{\B}{\operatorname{B}} \newcommand{\Bbar}{\overline{\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]{\mathop{\textstyle\sum}_{#1}^{#2}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\card}{\#} \renewcommand{\P}{\operatorname{P}} \renewcommand{\L}{\operatorname{L}} \newcommand{\mathds}{\mathbb}[/math]

(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]]
    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.