\documentclass[11pt,french]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[a4paper]{geometry}
\usepackage{babel}
\usepackage[tbtags]{amsmath}
\usepackage{amsthm}
\usepackage{bbm} %package for the indicator
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{epstopdf}
\usepackage{dsfont}
\usepackage{fancyhdr}
\usepackage[svgnames]{xcolor}

\newtheorem{q}{Q}
\newtheorem{rem}{Remark}

\setlength{\paperwidth}{21cm} \setlength{\paperheight}{32cm}
\setlength{\evensidemargin}{-0cm} \setlength{\oddsidemargin}{-0.5cm}
\setlength{\topmargin}{-2cm} \setlength{\headsep}{0.7cm}
\setlength{\headheight}{1cm} \setlength{\textheight}{26.5cm}
\setlength{\textwidth}{17.5cm}
\setlength{\topskip}{0.cm}
\setlength{\footskip}{1cm}
\pagestyle{fancy}
\fancyhf{}
\fancyhead[L]{{\footnotesize  Teor\'ia asint\'otica}}
\fancyhead[R]{{\footnotesize Doctorado/Maestr\'ia 2019/2020}}


%Command specific to the paper
\usepackage{mathtools}
\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\newcommand{\esp}[1]{\mathbb{E}\left[#1\right]} % The expected value
\newcommand{\var}[1]{\text{Var}\left(#1\right)} % The variance
\newcommand{\prob}[1]{\mathbb{P}\left(#1\right)} % The probability
\newcommand{\probi}[2]{\mathbb{P}_{#1}\left(#2\right)} % The probability with ind
\newcommand{\R}{\mathbb{R}} %The R set
\newcommand{\A}{\mathcal{A}}
\newcommand{\Sh}{\mathcal{S}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\C}{\mathbb{C}} %The set of complexes
\newcommand{\N}{\mathbb{N}^*} %The integers
\newcommand{\ex}{\noindent \underline{Ex :} }
\newcommand{\1}[1]{\mathbbm{1}_{#1}} %The indicator
\newcommand{\X}{\mathcal{X}}
\newcommand{\funk}[5]{
\begin{displaymath}
#1:
  \begin{array}{rcl}
    #2 & \longrightarrow & #3 \\
    #4 & \longmapsto & #5 \\
  \end{array}
\end{displaymath}}

\date{}
\begin{document}
\begin{center}
\Huge{Tarea n$^{\circ}$3}
\end{center}
Digamos que una función $f :\mathcal{X}^n \to [0,\infty)$ tiene la propiedad de ser \textit{acotada por si misma} si para cada $i$ existe una función $f_i: \mathcal{X}^n \to \mathbb{R}$ tal que
\[
0 \le f(x_1,\dots,x_n)-f_i(x_1,\dots,x_{i-1},x_{i+1},\dots,x_n) \le 1
\]
y
\[
\sum_{i=1}^n f(x_1,\dots,x_n)-f_i(x_1,\dots,x_{i-1},x_{i+1},\dots,x_n) \le  f(x_1,\dots,x_n).
\]


\noindent\underline{Notaciones :}
\begin{enumerate}
  \item $\text{Ent}(X)=\esp{X\log X}-\E X \log (\E X)$
  \item $X^{(i)}=(X_1,\dots,X_{i-1},X_{i+1},\dots,X_n)$ y $\E^{(i)}[.]=\E [.|X^{(i)}]$.
  \item $\text{Ent}^{(i)}(X)=\E^{(i)} [X\log X]-\E^{(i)} X \log (\E^{(i)} X)$.
  \item $\phi(u)=e^u-1-u$.
  \item $\psi_{Z-\E Z}(\lambda) = \log \esp{e^{\lambda (Z-\E Z)}}$
\end{enumerate}

Se \textbf{admite} la desigualdad de sub-aditividad de entropías : $\text{Ent}(Z)\le \E\sum_{i=1}^n  \text{Ent}^{(i)}(Z)$.



\paragraph{P.1} Sea $I \subset \R$ un intervalo abierto y $f: I \to \R$ una función convexa y derivable. Sea $X$ una variable tal que $X\in I$. Mostrar que
\[
\esp{f(X)-f(\E X)} = \inf_{a \in I}\esp{f(X)-f(a)-f'(a)(X-a)}
\]

\paragraph{P.2} Sea $Y$ una variable no negativa tal que $\esp{Y \log Y} <\infty$. Mostrar que
\[
\text{Ent}(Y) = \inf_{u>0} \esp{Y(\log Y - \log u)-(Y-u)}.
\]
\paragraph{P.3} Sea $Z_i$ una función de las variables en $X^{(i)}$. Mostrar que
\[
\text{Ent}^{(i)}\left(e^{\lambda Z}\right) \le \E^{(i)}\left[e^{\lambda Z}\phi (-\lambda (Z-Z_i))\right].
\]

\paragraph{P.4} Mostrar que
\[
\text{Ent}\left(e^{\lambda Z}\right) \le \sum_{i=1}^n\E\left[e^{\lambda Z}\phi (-\lambda (Z-Z_i))\right].
\]

\paragraph{P.5} Justificar que $\forall \lambda \in \R $ y $\forall u \in [0,1]$, $\phi (-\lambda u) \le u \phi (-\lambda)$. Sea $Z=f(X_1,\dots,X_n)$ donde $f$ es acotada por si misma. Deducir la desigualdad diferencial
\[
\left(\frac{\psi_{Z-\E Z}(\lambda)}{e^{\lambda}-1}\right)' \le \E Z \cdot \left(\frac{-\lambda}{e^\lambda-1}\right)'
\]

\paragraph{P.6} Mostrar que $\log \esp{e^{\lambda (Z-\E Z)}} \le \phi(\lambda)\E Z$ y que $\prob{Z \ge \E Z +t} \le \exp \left(-\frac{t^2}{2\E Z+2t/3}\right)$\\

\noindent Una variable definida por una función acotada por si misma se \textbf{concentra}.
\newpage
{\center\Large{\textbf{Preguntas opcionales :}}}\\

Una propiedad $\Pi$ \textit{definida sobre una union finita de productos} de un conjunto $\mathcal{X}$ es una secuencia $\Pi_1,\dots,\Pi_n$ tal que $\Pi_1 \subset \X,\dots,\Pi_n \subset \X^n$. Digamos que la $(x_1,\dots,x_m)\in \X^m$ satisface la propiedad $\Pi$ si $(x_1,\dots,x_m)\in \Pi_m$.
Una propiedad es \textit{hereditaria} si por cada secuencia $(x_1,\dots,x_m)$ que satisfaga la propiedad $\Pi$ cada sub-secuencia $(x_{i_1},\dots,x_{i_k})$ satisface $\Pi$.\\

\paragraph{P'.1} (Ejercicios Hora 3) Sea $f$ acotada por si misma y $Z=f(X_1,\dots,X_n)$ donde los $X_i$ son variables aleatorias independientes.
Mostrar que $\text{Var}(Z) \le \mathbb{E}Z$.

\paragraph{P'.2} Sea $\Pi$ una propiedad hereditaria. Para cada $(x_1,\dots,x_m)$, se asocia el tamaño máximo de una sub-secuencia de $(x_1,\dots,x_m)$ que satisfaga $\Pi$. Denotamos $f_{\Pi}(x_1,\dots,x_m)$ este valor. Mostrar que $f_\Pi$ es acotada por si misma.\\

Una función $f$ tal que existe una propiedad $\Pi$ tal que $f=f_\Pi$ se llama \textit{función de configuración}.

\paragraph{P'.3} Sean $X_1,\dots,X_n$ i.i.d. discretas. Sea $Z$ el numero de valores distintos que tomen las variables $X_1,\dots,X_n$. Mostrar que $Z$ es una función de configuración de las $X_1,\dots,X_n$.

\paragraph{P'.4} (Utilizamos las notaciones de la tarea 2) Para una clase $\A$ de subconjuntos de $\R^d$ y elementos $x_1,\dots, x_n \in \R^d$, digamos que $\A$ rompe $(x_1,\dots, x_n)$ si $|\A(x_1^n)|=2^n$. Denotamos $VC(\A,x_1^n)$ el tamaño máximo de una sub-secuencia de $(x_1,\dots, x_n)$ que está rota por $\A$. Mostrar que este noción de dimensión VC es una función de configuración.


\end{document}
