\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 2020}}

\DeclareMathOperator{\Vol}{Vol}

%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{\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{\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}$2}
\end{center}

In this tarea se busca comparar la técnica de `regular chaining' con la de `generic chaining'. La fecha de entrega de la tarea es el \textbf{06/04/2020}.\\

En lo que sigue, \(T\) es un espacio métrico y llamamos \(d\) la distancia asociada. Digamos que una sucesión \((\mathcal{A}_n)_n\) de particiones crecientes (i.e. \(\mathcal{A}_n\subset \mathcal{A}_{n+1}\)) de \(T\) es \textbf{admisible} si \(|\mathcal{A}_n|\le 2^{2^n}=:N_n\) para cada \(n\ge 1\) y \(|\mathcal{A}_0|=1\). Por un elemento \(t\in T\), se denota \(A(t)\) el único elemento de \(\mathcal{A}_n\) que contiene \(t\). Usaremos la notación \(\Delta(A)\) para designar el diámetro de \(A\in \mathcal{A}_n\).
\begin{enumerate}
  \item Sea \((\mathcal{A}_n)\) una sucesión admisible y \(\mathcal{B}_n=\mathcal{A}_{n-1}\times \mathcal{A}_n\) si \(n\ge 1\) y \(\mathcal{B}_{-1}=\mathcal{B}_0=\{T\}\times\{T\}\). Mostrar que \((\mathcal{B}_{n-1})_{n\ge 0}\) es admisible por el espacio \(T\times T\).
  \item Mostrar que si dos sucesiones \(\mathcal{B}_n\) y \(\mathcal{C}_n\) son admisibles entonces la sucesión \(\mathcal{A}_n\) de las particiones dondes los elementos son de la forma \(B\cap C\) con \(B\in\mathcal{B}_{n-1}\) y \(C\in\mathcal{C}_{n-1}\) y tal que \(\mathcal{A}_0=\{T\}\) es admisible.
  \item Dado una sucesión admisible \((\mathcal{A}_n)_n\), decir como construir mapeos \(\Pi_n : T \to A_n\) tal que \(\forall t\in T\)
  \begin{equation*}
    d(\Pi_n(t),\Pi_{n+1}(t))\le \Delta(A_n(t)).
  \end{equation*}
  \item Sea \((X_t)_{t\in T}\) un proceso de incrementos sub-Gaussianos y tal que \(\forall t\in T,\ \esp{X_t}=0\). Mostrar que  \(\forall n\ge 0\) y \(\forall u>\sqrt{16 \log 2}\),
  \begin{equation*}
    \prob{\sup_{t\in T}\frac{X_{\Pi_{n+1}(t)}-X_{\Pi_{n}(t)}}{\Delta(A_n(t))}\ge u2^{n/2}}\le N_{n+2}\exp(-u^22^{n-1}) \le \exp(-u^22^{n-2}).
  \end{equation*}
  Mostrar que \(\sum_{n\ge 0}\exp(-u^22^{n-2})\le \sum_{n\ge 1}\exp(-\frac{u^2}{4}n)\le 2\exp (-\frac{u^2}{4})\).
  \item Usando 4., mostrar que
  \begin{equation*}
    \prob{\forall t \in T,\ X_t < u \sum_{n\ge 0}2^{n/2}\Delta(A_n(t))}\ge 1-2\exp(-u^2/4)
  \end{equation*}
y deducir que existe una constante \(L>0\) universal tal que
  \begin{equation*}
    \esp{\sup_{t\in T}X_{t}}\le L \inf_{(\mathcal{A}_p)_p \text{ admisible}}\sup_{t\in T}\sum_{n\ge 0}2^{n/2}\Delta(A_n(t)).
  \end{equation*}
  Esa cota se llama cota de \textbf{generic chaining}.
  \item Para cada \(n\), definimos \(e_n=\inf_{(\mathcal{A}_p)_p}\sup_t \Delta (A_n(t))\). Mostrar que \(e_n=2\inf\{\varepsilon : \mathcal{N}(\varepsilon,T,d)\le N_n\}\).
   Deducir que existe una constante universal \(C\) tal que
  \begin{equation*}
   \inf_{(\mathcal{A}_p)_p \text{ admisible}}\sup_{t\in T}\sum_{n\ge 0}2^{n/2}\Delta(A_n(t)) \le  \sum_{n\ge 0}2^{n/2}e_n \le C \int_{0}^{\infty}\sqrt{\log \mathcal{N}(\varepsilon,T,d)}d\varepsilon.
  \end{equation*}
  La cota de \textbf{generic chaining} es mejor que la cota de \textbf{Dudley}.
  \item Sea \((a_i)_{i\ge 1}\) una sucesión decreciente t.q. \(a_i>0\), definimos el elipsoide
  \begin{equation*}
    \mathcal{E}=\left\{t\in \ell^2 : t_i >0 \text{ y }\sum_i \frac{t_i^2}{a_i^2} \le 1\right\}.
  \end{equation*}
  Sea \((g_i)_{i\ge 1}\) una sucesión i.i.d. de variables Gaussianas estandares.
  Consideramos el proceso \(X_t=\sum_{t\in \mathcal{E}}t_ig_i\). Mostrar que
  \begin{equation*}
    \esp{\sup_{t\in T}X_t}\le \left(\sum_{i\ge 1}a_i^2\right)^{1/2}\le \left(\sum_{n\ge 0}2^na_{2^n}^2\right)^{1/2}.
  \end{equation*}
  \item En esa pregunta queremos probar que el orden de \(\sum_{n\ge 0}2^{n/2}e_n\) is of order larger than \((\sum_{n\ge 0} 2^{n}a_{2^n}^2)^{1/2}\). Sea
  \begin{equation*}
    \mathcal{E}_n=\left\{t\in \R^{2^n} : t_i >0 \text{ y }\sum_i \frac{t_i^2}{a_i^2}  \le 1\right\}.
  \end{equation*}
  \begin{enumerate}
    \item Mostrar que \(e_n(\mathcal{E}_n)\le e_n(\mathcal{E})\).
    \item Sea \(B\) la bola unitaria Euclidiana de \(\R^{2^n}\), sea \(T \subset \mathcal{E}_n\) un conjunto finito t.q \(|T|\le N_n\) y sea \(\varepsilon>0\). Mostrar que
    \begin{equation*}
      \Vol \left(\cup_{t\in T}(\varepsilon B+t)\right)\le (2\varepsilon)^{2^n}\Vol (B).
    \end{equation*}
    \item Mostrar que \(\Vol (\mathcal{E}_n) \ge a_{2^n}^{2^n}\Vol (B)\). Deducir que \(\mathcal{E}_n \subset \cup_{t\in T}(\varepsilon B+t) \implies 2 \varepsilon \ge a_{2^n}\).
    \item Finalmente, probar que \(e_n(\mathcal{E}) \ge a_{2^n}/2\) y concluir.
  \end{enumerate}
\end{enumerate}
En generalidad completa, la cantidad \(\inf_{\mathcal{A}_n \text{ admisible}}\sup_{t\in T}\sum_{n\ge 0}2^{n/2}\Delta(A_n(t))\) siempre tiene el orden de magnitud correcto aun que la cota de Dudley es demasiado conservativa.
\end{document}
