%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% Exercícios de MAC5775 Métodos Probabilísticos em Combinatória      %
% 2o. semestre de 2000                                               %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Tuesday 17 Oct 2000 03:47:00pm BRDT yoshi@rebutosa>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
%----------------------------

\let\:=\colon
\let\epsilon=\varepsilon
\def\e{{\rm e}}
\def\dist{\mathop{\rm dist}\nolimits}
\def\RR{\mathbb R}
\def\NN{\mathbb N}
\def\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
%\let\sim=\thicksim

\def\inR{\mathrel{\in_{\text R}}} 

\def\cA{\mathcal A}
\def\cB{\mathcal B}
\def\cF{\mathcal F}
\def\cG{\mathcal G}
\def\cH{\mathcal H}
\def\cL{\mathcal L}
\def\cR{\mathcal R}

\def\barp{{\bar p}}

\def\Bi{\mathop{{\rm Bi}}\nolimits}
\def\Var{\mathop{{\rm Var}}\nolimits}
\def\Cov{\mathop{{\rm Cov}}\nolimits}
\def\dev{\mathop{{\rm dev}}\nolimits}

\def\EE{\mathop{\hbox{\raise.03ex\hbox{${\mathbb E}$}}}\nolimits}
\def\PP{\mathop{\hbox{\raise.03ex\hbox{${\mathbb P}$}}}\nolimits}
\def\FF{\mathop{\hbox{\raise.03ex\hbox{${\mathbb F}$}}}\nolimits}

\def\RP{\mathbf{RP}}
\def\BPP{\mathbf{BPP}}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother

\def\datedue#1{$\{$\textsl{Data de entrega}: #1$\}$}

\begin{document}
\title[MAC5775 Métodos Probabilísticos]{Exercícios de Métodos
  Probabilísticos\\2{\tiny o.} semestre de 2000} 
\date{Versão de \today}
\maketitle

\begin{enumerate}\thispagestyle{empty}
\item Prove as seguintes estimativas.  Nesta questão, escrevemos~$O(f(x))$
  para qualquer termo~$y$ tal que~$|y|\leq C|f(x)|$ para todo~$x$
  satisfazendo~$|x|\leq x_0$, onde~$C$ e~$x_0>0$ são constantes absolutas.
  (Observe que, nestas estimativas, estamos intessados em uma vizinhança
  de~$0$.)
  \begin{enumerate}
  \item[(\textit{i})]$1+x\leq\e^x$ para todo~$x\in\RR$.
  \item[(\textit{ii})]$1+x>\exp\big\{x-x^2/2\big\}$ para todo~$0<x\leq1$. 
  \item[(\textit{iii})]$1-x>\exp\big\{-x-x^2\big\}$ para todo~$0<x<x_0$,
    para algum~$x_0>0$.  De fato, podemos tomar, por exemplo,~$x_0=0{.}68$.  
  \item[(\textit{iv})]$1+x\geq\exp\big\{x+O(x^2)\big\}$ para todo~$x>-1$. 
  \item[(\textit{v})]$1+x\geq\exp\big\{x-x^2/2+O(x^3)\big\}$ para
    todo~$x>-1$.  
  \end{enumerate}
  [\textsl{Sugestão.} Lembre que~$1/(1-x)=1+x+x^2+\dots$ uniformemente
  se~$|x|\leq x_0$ e~$x_0<1$.  Integre ambos os lados para obter
  $$
  -\log(1-x)=x+{1\over2}x^2+{1\over3}x^3+\dots]
  $$
\datedue{4/9/2000}

\item Prove as seguintes estimativas para~$a\choose b$, onde~$a$ e~$b$ são
  inteiros não-negativos.
  \begin{enumerate}
  \item[(\textit{i})] 
    \begin{equation}
       \label{eq:binom_lwbd}
       {a\choose b}\geq\(a\over b\)^b.
    \end{equation}
     
  \item[(\textit{ii})]
    \begin{equation}
       \label{eq:binom_upbd1}
       {a\choose b}\leq{a^b\over b!}.
    \end{equation}

  \item[(\textit{iii})]Para todo~$b>0$, 
    \begin{equation}
       \label{eq:binom_upbd2}
       {a\choose b}\leq\(\e a\over b\)^b.
    \end{equation}
    [\textsl{Sugestão para~$(\text{\textit{iii}}\,)$.} Avalie~$(1+x)^a$ por
    cima e por baixo para~$x=b/a$.  Use, para tanto, $1+x\leq\e^x$ e o binômio
    de Newton.]
  \end{enumerate}
  \datedue{4/9/2000}
  
\item Suponha que~$n$ é um inteiro positivo e que~$0\leq p\leq1$.  Seja~$X$
  uma v.a.{} binomial de parâmetros~$n$ e~$p$: $X\sim\Bi(n,p)$.  Isto é, 
  $$
  \PP(X=k)={n\choose k}p^k(1-p)^{n-k}
  $$ 
  para todo~$k$ inteiro.  Prove que
  \begin{equation}
    \label{eq:bin_upbd}
    \PP(X\geq k)\leq{n\choose k}p^k\leq\(\e\mu\over k\)^k, 
  \end{equation}
  onde~$\mu=\EE(X)$. \datedue{4/9/2000}
  
\item Suponha~$2\leq k\leq n$.  Prove que existe uma família de
  conjuntos~$\cF\subset{[n]\choose k}$ \textit{linear} (i.e., $|F\cap
  F'|\leq1$ para todo~$F$ e~$F'\in\cF$ distintos) com
  \begin{equation}
    \label{eq:pSTS_lwbd}
    |\cF|\geq c_k{n\choose 2}, 
  \end{equation}
  onde~$c_k$ é uma constante positiva que depende apenas de~$k$ (procure
  maximizar~$c_k$).  Prove que qualquer tal família
  satisfaz
  \begin{equation}
    \label{eq:STS_upbd}
    |\cF|\leq{k\choose2}^{-1}{n\choose2},
  \end{equation}
  e portanto a melhor constante possível em~\eqref{eq:pSTS_lwbd}
  é~${k\choose2}^{-1}$.  [\textsl{Sugestão.} Para provar a existência da
  família~$\cF$, ponha em uma família auxiliar~$\cG$ cada elemento
  de~${[n]\choose k}$ com probabilidade~$p$, independentemente.  Para cada
  par~$(G,G')\in\cG\times\cG$ com~$1<|G\cap G'|<k$, remova~$G'$ de~$\cG$.
  Escolha um~$p$ adequado para que a família resultante~$\cF$
  satisfaça~\eqref{eq:pSTS_lwbd}.] \datedue{4/9/2000}

\item Prove que existe uma família linear~$\cF\subset{[n]\choose3}$ com
  $$
  |\cF|\geq\({1\over3}-o(1)\){n\choose2},
  $$
  onde~$o(1)$ denota um termo que tende a~$0$ conforme~$n\to\infty$.  Note
  que, em vista de~\eqref{eq:STS_upbd}, tal família~$\cF$ tem tamanho
  assintoticamente ótimo.  [\textsl{Sugestão.} Para
  cada~$\{a,b,c\}\in{[n]\choose3}$, considere~$a+b+c\pmod n$.]
  \datedue{4/9/2000} 
  
\item Generalize o resultado da questão anterior, mostrando que existe uma
  família~$\cF$ de $k$-subconjuntos de~$[n]$ tal que quaisquer dois de seus
  membros têm no máximo~$k-2$ elementos em comum e
  $$
  |\cF|\geq\({1\over k}-o(1)\){n\choose k-1}.
  $$
  Mostre que tal~$\cF$ tem tem tamanho assintoticamente
  ótimo. \datedue{4/9/2000} 
  
\item Suponha que~$p=p(n)=\omega n^{-1/3}$, onde~$\omega=\omega(n)\to\infty$
  conforme~$n\to\infty$, e considere o grafo aleatório~$G(n,p)$.
  Seja~$0<\epsilon<1$ uma constante arbitrária.  Mostre que para quase
  todo~$G=G(n,p)$ (i.e., que com probabilidade tendendo a~$1$
  conforme~$n\to\infty$) temos que todo conjunto de vértices~$S\subset V(G)$
  com~$|S|\geq\epsilon n$ induz um triângulo~$K^3$ em~$G$.
  [\textsl{Sugestão.}  Considere famílias lineares de triplas em~$S$.]
  \datedue{11/9/2000} 
  
\item \label{Q:8} Seja~$G$ um grafo.  Escrevemos~$\chi_3(G)$ para o
  \textit{número $K^3$-cromático} de~$G$, i.e., o número mínimo de partes em
  uma partição~$V(G)=\bigcup_iV_i$, onde cada~$V_i$ induz um subgrafo livre
  de~$K^3$ em~$G$.  Equivalentemente, $\chi_3(G)$ é o número mínimo de cores
  com que podemos colorir os vértices de~$G$ de forma que não haja nenhum
  triângulo monocromático.
  \begin{enumerate}
  \item[(\textit{i})]Mostre que~$K^7$ é tal que~$\chi_3(K^7)>3$.
  \item[(\textit{ii})]Mostre que existem grafos~$G$ com~$\chi_3(G)>3$ livres
    de~$K^7$ (i.e., que não contêm~$K^7$ como subgrafo).
  \end{enumerate} \datedue{11/9/2000}
  
\item Lembre que escrevemos~$\nu(n)$ para o número de primos que dividem~$n$.
  Seja~$N$ um inteiro positivo, e considere~$[N]$ como um espaço de
  probabilidade, com todos os seus elementos equiprováveis.  
  Mostramos que
  \begin{equation}
    \label{eq:nu_ave}
    \EE(\nu)=\log\log N+O(1)
  \end{equation}
  e que
  \begin{equation}
    \label{eq:nu_Var}
    \Var(\nu)\leq\log\log N+O(1).
  \end{equation}
  \begin{enumerate}
  \item[(\textit{i})] Deduza cuidadosamente de~\eqref{eq:nu_ave}
    e~\eqref{eq:nu_Var} que se~$\lambda>1$ é uma constante, então
    \begin{equation}
      \label{eq:nu_Prob}
      \PP\big\{|\nu-\log\log N|>\lambda\sqrt{\log\log N}\big\}
      \leq\lambda^{-2}+o(1)
    \end{equation}
    conforme~$N\to\infty$.
  \item[(\textit{ii})] Deduza de~\eqref{eq:nu_Prob} que
    $$
    \nu(n)\sim\log\log N
    $$
    para quase todo~$n\in[N]$, isto é, 
    $$
    \lim_{N\to\infty}\PP\big\{|\nu-\log\log N|>\epsilon\log\log N\big\}=0. 
    $$
    para todo~$\epsilon>0$ fixo.
  \end{enumerate} \datedue{11/9/2000}

\item Suponha que
  \begin{equation}
    \label{eq:p_def}
    p=p(n)={\log n+f\over n}, 
  \end{equation}
  onde~$f=f(n)$, e considere o grafo aleatório~$G(n,p)$.  Prove que as
  seguintes asserções valem para quase todo~$G=G(n,p)$.
  \begin{enumerate}
  \item[(\textit{i})] Se~$f=f(n)\to\infty$, então~$G$ não tem vértices isolados.
  \item[(\textit{ii})] Se~$f=f(n)\to-\infty$ e~$|f|\leq\log n$, então~$G$ tem
    vértices isolados.  De fato, o número de vértices isolados~$X=X(G)$ em~$G$
    satisfaz
    $$
    X\sim\exp\{-f\}.
    $$
  \item[(\textit{iii})] O que você consegue dizer sobre o caso em
    que~$f=f(n)\to f_0$ para alguma contante~$f_0$?
  \end{enumerate}
  \datedue{11/9/2000}
  
% \bigskip
% \noindent\textbf{Observação.} \textsl{As questões abaixo ainda podem sofrer alguma
%   mutação.}

\item Considere a identidade
  \begin{equation}
    \label{eq:linha_Pascal}
    \sum_{0\leq k\leq n}{n\choose k}=2^n,
  \end{equation}
  e seja~$\omega=\omega(n)$ uma função com~$\omega\to\infty$
  conforme~$n\to\infty$.  Podemos dizer que a soma em~\eqref{eq:linha_Pascal}
  está `concentrada' nos termos com~$k$ satisfazendo
  \begin{equation}
    \label{eq:cond_k}
    \left|k-{n\over2}\right|\leq\omega\sqrt n,
  \end{equation}
  pois
  \begin{equation}
    \label{eq:concentracao}
    \sum_k\nolimits^*{n\choose k}\sim2^n,
  \end{equation}
  onde~$\sum_k^*$ indica soma sobre todos os~$k$
  satisfazendo~\eqref{eq:cond_k} e escrevemos~$f(n)\sim g(n)$
  se~$\lim_nf(n)/g(n)=1$.  
  
  Suponha agora que~$\epsilon>0$ é um número real fixo.  Podemos dizer que a
  soma em~\eqref{eq:linha_Pascal} está `exponencialmente concentrada' nos
  termos com~$k$ satisfazendo
  \begin{equation}
    \label{eq:cond_k2}
    \left|k-{n\over2}\right|\leq\epsilon n,
  \end{equation}
  pois
  \begin{equation}
    \label{eq:concentracao2}
    \sum_k\nolimits'{n\choose k}\leq2^n\exp\{-c_\epsilon n\},
  \end{equation}
  onde~$\sum_k'$ indica soma sobre todos os~$k$
  para os quais~\eqref{eq:cond_k2} \textit{não vale},
  e~$c_\epsilon>0$ é uma constante que depende apenas de~$\epsilon$.
  \begin{enumerate}
  \item[(\textit{i})]Prove~\eqref{eq:concentracao}.  
  \item[(\textit{ii})]Prove que a condição de que~$\omega\to\infty$ é
    necessária para que~\eqref{eq:concentracao} valha.  Para tanto, use a
    fórmula de Stirling.  Uma versão desta fórmula é como segue: para
    todo~$n\geq1$, existe~$\alpha_n$ com~$1/(12n+1)<\alpha_n<1/12n$ tal que 
    \begin{multline}
      \label{eq:Stirling}
      \hspace{2.5cm}n!=\sqrt{2\pi n}\(n\over\e\)^n\e^{\alpha_n}\\
      =\sqrt{2\pi n}\(n\over\e\)^n\(1+{1\over12n}+O\(1\over n^2\)\).
      \qquad
    \end{multline}
    Use~\eqref{eq:Stirling} para provar que se~$k=k(n)=n/2+c_n\sqrt n$,
    onde~$c_n\to c$ ($n\to\infty$) e~$c$ é uma constante, então
    \begin{equation}
      \label{eq:middle_binom}
      {n\choose k}={n!\over k!(n-k)!}\sim{d\over\sqrt n}2^n,
    \end{equation}
    onde~$d=d(c)>0$ é uma constante que depende apenas de~$c$.
  \item[(\textit{iii})]Prove~\eqref{eq:concentracao2}.
  \end{enumerate}
  \datedue{25/9/2000} 

\item Para todo~$N$, definimos~$\cR_N\subset2^{[N]}$ como sendo o hipergrafo
  cujos membros são as progressões aritméticas contidas em~$[N]$.  Ademais,
  pomos 
  \begin{equation}
    \label{eq:dev_def}
    \dev(\cR_N)=\min_f\max_P\Big|\sum_{x\in P}f(x)\Big|,
  \end{equation}
  onde o mínimo é tomado sobre todas as funções~$f\:[N]\to\{\pm1\}$ e o máximo
  é tomado sobre todos membros~$P\in\cR_N$.  Prove que existem~$c>0$
  e~$N_0\geq1$ tais que
  \begin{equation}
    \label{eq:low_dev}
    \dev(\cR_N)\leq c(N\log N)^{1/2}
  \end{equation}
  para todo~$N\geq N_0$. \datedue{25/9/2000}
  
\item Seja~$0<\eta<1$ um número real fixo.  Mostre que existe uma
  constante~$c=c(\eta)>0$ para o qual vale o seguinte.  Para
  todo~$\epsilon>0$, existe um inteiro~$N_0=N_0(\eta,\epsilon)\geq1$ tal que
  se~$N\geq N_0$, então existe~$A\subset[N]$ tal que
  (\textit{i})~$\big||A|-\eta N\big|\leq\epsilon\eta N$ e (\textit{ii})~para
  toda progressão aritmética~$P\in\cR_N$, temos
  \begin{equation}
    \label{eq:eta_PA_dev}
      \big||P\cap A|-\eta|P|\big|\leq c(N\log N)^{1/2}.
  \end{equation}\datedue{25/9/2000}

\item Mostre que existem constantes absolutas~$c>0$ e~$N_0\geq1$ para os quais
  temos 
  \begin{equation}
    \label{eq:high_dev}
    \dev(\cR_N)\geq cN^{1/4}
  \end{equation}
  para todo~$N\geq N_0$.  Use o teorema de Roth (veja Teorema~25A de Beck e
  Chen) que afirma que o `desvio' em~\eqref{eq:eta_PA_dev} (isto é, o lado
  esquerdo daquela desigualdade) é~$\geq c'(\eta(1-\eta))^{1/2}N^{1/4}$
  ($c'>0$) para algum~$P=P_A\in\cR_N$ para todo~$A\subset[N]$ com~$|A|=\eta
  N$.  Para tanto, considere~$M=2N$ e se~$f\:[N]\to\{\pm1\}$,
  considere~$A\subset[M]$ tal que~$A\cap[N]=\{x\in[N]\:f(x)=+1\}$
  e~$A\cap([M]\setminus[N])=\{x\in[M]\setminus[N]\:f(x-N)=-1\}$.
  \datedue{25/9/2000} 
  
\item\label{Q:15}Suponha que as variáveis aleatórias~$X_1,\dots,X_n$ assumem
  apenas um número finito de valores.  Dizemos que estas variáveis são
  \textit{independentes} se para todo~$I\subset[n]$, e para toda
  família~$(R_i)_{i\in I}$ com~$R_i\subset\RR$ ($i\in I$), temos
  \begin{equation}
    \label{eq:independent_def}
    \PP\Big(X_i\in R_i\text{ para todo }i\in I\Big)
    =\prod_{i\in I}\PP\(X_i\in R_i\).
  \end{equation}
  \begin{enumerate}
  \item[(\textit{i})]Suponha que as variáveis aleatórias~$X_1,\dots,X_n$
    como acima são independentes.  Deduza que
    \begin{equation}
      \label{eq:independent_def2}
      \EE\Big(\prod_{i\in I}X_i\Big)=\prod_{i\in I}\EE\(X_i\).
    \end{equation}
  \item[(\textit{ii})]Suponha que~$X_1,\dots,X_n$ sejam variáveis aleatórias
    independentes, que assumem valores em~$\{\pm1\}$, e com~$\EE(X_i)=0$ para
    todo~$1\leq i\leq n$.  Mostre que o espaço~$\Omega$ em que estas variáveis
    aleatórias estão definidas precisa satisfazer~$|\Omega|\geq2^n$.  A
    hipótese de que estas variáveis tenham esperança nula é essencial?
    \datedue{25/9/2000}
  \end{enumerate}
  
% \item\label{Q:15'}Seja~$\epsilon>0$ um número real, e suponha
%   que~$X_1,\dots,X_n$ sejam variáveis aleatórias que assumem valores
%   em~$\{\pm1\}$ e com~$\EE(X_i)=0$ para todo~$1\leq i\leq n$.  Dizemos que
%   os~$X_i$ ($1\leq i\leq n$) são \textit{$\epsilon$-quase-independentes} se,
%   para todo~$I\subset[n]$, temos
%   \begin{equation}
%     \label{eq:independent_def}
%     \left|\EE\Big(\prod_{i\in I}X_i\Big)\right|\leq\epsilon. 
%   \end{equation}
%   Seja~$p$ um primo com~$p\geq(n/\epsilon)^2$.  Considere~$\Omega=\FF_p$, os
%   inteiros módulo~$p$, e ponha
%   \begin{equation}
%     \label{eq:Weil_vars}
%     X_i\:\Omega\to\{\pm1\}
%   \end{equation}



%   Mostre que existem~$hmmm$

%   Para todo inteiro~$n\geq n_0$, construa um espaço de
%   probabilidade~$(\Omega,\PP)$ com~$|\Omega|=2m$ e variáveis aleatórias
%   $\epsilon$-quase-independentes~$X_1,\dots,X_n$ definidas
%   sobre~$(\Omega,\PP)$ com~$m\leq Cn$.


%   Suponha que~$X_1,\dots,X_n$ sejam variáveis aleatórias independentes, que
%   assumem valores em~$\{\pm1\}$, e com~$\EE(X_i)=0$ para todo~$1\leq i\leq n$.
%   Mostre que o espaço~$\Omega$ em que estas variáveis aleatórias estão
%   definidas precisa satisfazer~$|\Omega|\geq2^n$.  A hipótese de que estas
%   variáveis tenham esperança nula é essencial?  \datedue{25/9/2000}
  
\item\label{Q:16} Dizemos que as variáveis aleatórias~$X_1,\dots,X_n$ sao
  \textit{$k$-a-$k$ independentes} se, para todo~$I\subset[n]$ com~$|I|=k$, as
  variáveis~$X_i$ ($i\in I$) formam uma família de~$k$ variáveis
  independentes.
  \begin{enumerate}
  \item[(\textit{i})]Fixe~$k\geq1$ e~$n=2^k$.  Construa um espaço de
    probabilidade~$(\Omega,\PP)$ com~$|\Omega|=n$ e variáveis
    aleatórias~$X_1,\dots,X_{n-1}$ definidas sobre~$\Omega$, tomando valores
    em~$\{\pm1\}$, duas-a-duas independentes, e com~$\EE(X_i)=0$ para
    todo~$1\leq i<n$.  [\textsl{Sugestão.}  Considere as matrizes
    $$
    \begin{pmatrix}
      +&+\\
      +&-
    \end{pmatrix},
    \qquad
    \begin{pmatrix}
      +&+&+&+\\
      +&-&+&-\\
      +&+&-&-\\
      +&-&-&+\\
    \end{pmatrix},
    \qquad\text{etc.}
    $$
    Calcule o quadrado das matrizes acima.]
  \item[(\textit{ii})]Suponha que~$X_1,\dots,X_{n-1}$ é uma seqüência de
    variáveis aleatórias definidas sobre~$(\Omega,\PP)$, com~$|\Omega|=n=2^k$
    e~$k\geq1$ é um inteiro.  Suponha que, para um certo inteiro~$\ell$, a
    família~$X_i$ ($1\leq i<n$) é uma família de variáveis aleatórias
    $\ell$-a-$\ell$ independentes.  Dê um limitante superior para~$\ell$.
  \item[(\textit{iii})]Suponha que~$X_1,\dots,X_m$ é uma seqüência de
    variáveis aleatórias definidas sobre~$\Omega$, com~$|\Omega|=n$, tomando
    valores em~$\{\pm1\}$, duas-a-duas independentes, e com~$\EE(X_i)=0$ para
    todo~$1\leq i\leq m$.  Mostre que~$m<n$.  [\textsl{Sugestão.} Considere o
    espaço vetorial sobre~$\RR$ das funções reais definidas em~$\Omega$.
    Observe que~$\<X_i,X_j\>=|\Omega|\EE(X_iX_j)$, onde~$\<f,g\>$ denota o
    produto escalar canônico.  Prove que, devido às hipóteses sobre os~$X_i$,
    temos que a variável constante igual a~$1$ e os~$X_i$ ($1\leq i\leq m$)
    são linearmente independentes.]
  \end{enumerate}
  \datedue{25/9/2000}
  
\item Sejam~$Y_1,\dots,Y_n$ variáveis aleatórias independentes com
  $\PP(Y_i=1)=1-\PP(Y_i=0)=p_i$ ($1\leq i\leq n$).  Ponha~$Y=\sum_{1\leq i\leq
    n}Y_i$.  Seja
  $$
  \barp={1\over n}\sum_{1\leq i\leq n}p_i,
  $$
  e considere uma variável aleatória binomial~$X$ de parâmetros~$n$
  e~$\barp$, isto é, $X\sim\Bi(n,\barp)$.
  \begin{enumerate}
  \item[(\textit{i})]Use um argumento de convexidade para provar que 
    \begin{equation}
      \label{eq:X_vs_Y}
      \begin{split}
        \EE(\e^{uY})&=\prod_{1\leq i\leq n}\big(1+p_i(\e^u-1)\big)\\
        &\qquad\qquad\leq\big(1+\barp(\e^u-1)\big)^n=\EE(\e^{uX})
      \end{split}
    \end{equation}
    para todo~$u\in\RR$.
    
  \item[(\textit{ii})]Deduza de~\eqref{eq:X_vs_Y} que se~$\mu=\EE(Y)$, então,
    para todo~$0\leq t\leq n-\mu$, temos
    \begin{equation*}
      \PP\big(Y\geq\EE(Y)+t\big)
      \leq\(\mu\over\mu+t\)^{\mu+t}\(n-\mu\over n-\mu-t\)^{n-\mu-t}.
    \end{equation*}
    Note que podemos portanto concluir as desigualdades
    \begin{equation}
      \label{eq:Y1}
      \PP\big(Y\geq\EE(Y)+t\big)
      \leq\exp\(-{t^2\over2(\mu+t/3)}\)
    \end{equation}
    e
    \begin{equation}
      \label{eq:Y2}
      \PP\big(Y\leq\EE(Y)-t\big)
      \leq\exp\(-{t^2\over2\mu}\)
    \end{equation}
    para todo~$t\geq0$.  Ademais, para todo~$0\leq\epsilon\leq3/2$, temos
    \begin{equation}
      \label{eq:Y3}
      \PP\big(|Y-\EE(Y)|\geq\epsilon\EE(Y)\big)
      \leq2\exp\(-{\epsilon^2\over3}\EE(Y)\).
    \end{equation}
    (Não é necessário deduzir~\eqref{eq:Y1}--\eqref{eq:Y3} explicitamente.) 
  \end{enumerate}\datedue{2/10/2000}
  
\item Dado um conjunto ~$A=\{a_1<a_2<\dots\}\subset\NN$, escrevemos~$f_A(n)$
  para o número de pares~$(i,j)$ tais que~$i<j$ e~$a_i+a_j=n$ ($n\in\NN$).
  Ademais, pomos~$A(n)=\#\{a\in A\:a\leq n\}$.  Seja~$0<\epsilon<1/2$ um
  número real fixo.  Mostre que existe um conjunto~$A$ satisfazendo as
  seguinte duas condições:
  \begin{enumerate}
  \item[($P_1$)]Temos
    \begin{equation}
      \label{eq:dense}
      \lim_{n\to\infty}A(n)n^{-1/2+\epsilon}=\infty.
    \end{equation}
  \item[($P_2$)]Existe uma constante~$C=C(\epsilon)$ para a qual temos 
    \begin{equation}
      \label{eq:bounded_reps}
      f_A(n)\leq C\text{ para todo }n\geq n_0,
    \end{equation}
    onde~$n_0=n_0(A)$ é uma constante.
  \end{enumerate}
  Este é um resultado de Erd\H os e Rényi.  \datedue{2/10/2000}
  
\item Seja~$k$ um inteiro arbitrário.  Mostre que existem grafos~$G$
  com
  $$
  \chi_3(G)>k
  $$
  livres de~$K^4_-$, o grafo completo com $4$~vértices com uma aresta
  removida.  Nesta questão, estamos usando a notação da Questão~\ref{Q:8}.
  Note que aqui provamos algo mais forte que o resultado daquela questão.
  [\textsl{Sugestão.} Use a desigualdade de Janson e aprecie o poder deste
  resultado.]  \datedue{2/10/2000}
  
% \item Vimos na Questão~\ref{Q:16}(\textit{ii}) (ou~\ref{Q:15}) que se uma
%   família de variáveis aleatórias definidas sobre um espaço~$(\Omega,\PP)$ é
%   $\ell$-a-$\ell$ independente, então $\ell\leq\log_2|\Omega|$.  Nesta
%   questão, vamos ver que podemos construir, explicitamente, famílias de
%   variáveis aleatórias que são `quase' $\ell$-a-$\ell$ independente para
%   valores de~$\ell$ muito maiores.

  
\item\label{Q:20}
  Suponha que~$\cH$ seja uma família $2$-universal de funções $h\:U\to T$;
  isto é, para todo~$(x,y)\in U\times U$ e para todo~$(z_1,z_2)\in T\times T$,
  temos
  \begin{equation*}
    \PP_{h\inR\cH}\big((h(x),h(y))=(z_1,z_2)\big)={1\over t^2},
  \end{equation*}
  onde~$t=|T|$.  Acima, o índice~`$h\inR\cH$' indica que a probabilidade é
  tomada sobre uma escolha uniforme de um membro~$h$ de~$\cH$.
  \begin{enumerate}
  \item[(\textit{i})]Prove que para todo~$x\in U$ e para todo~$z\in T$, temos
    \begin{equation*}
      \PP_{h\inR\cH}(h(x)=z)={1\over t}.
    \end{equation*}
  \item[(\textit{ii})]Fixe~$x$, $y\in U$ e seja~$B\subset T$.
    Ponha~$Z_w=[h(w)\in B]$ para~$w\in\{x,y\}$, onde~$[P]=1$ se~$P$ ocorre
    e~$[P]=0$ caso contrário.  Prove que
    \begin{equation*}
      \Cov(Z_x,Z_y)=\EE(Z_xZ_y)-\EE(Z_x)\EE(Z_y)=0
    \end{equation*}
    se~$x\neq y$.
  \item[(\textit{iii})]Seja~$A\subset U$ e ponha~$Z=\sum_{x\in A}Z_x$, onde a
    notação é como em~(\textit{ii}).  Determine~$\EE(Z)$ e~$\Var(Z)$.
  \end{enumerate}\datedue{30/10/2000}
  
\item Suponha que~$\cH$ seja uma família $2$-universal de funções $h\:U\to T$.
  Sejam dados~$A\subset U$ e~$B\subset T$ e~$\epsilon>0$.  Dizemos
  que~$h\in\cH$ é \textit{$(A,B,\epsilon)$-bom} se 
  \begin{equation*}
    \Big|\PP_{x\inR U}\big(x\in A\text{ e }h(x)\in B\big)
    -\mu(A)\mu(B)\Big|\leq\epsilon,
  \end{equation*}
  onde~$\mu(A)=|A|/|U|$ e~$\mu(B)=|B|/|T|$.  Prove que, para quaisquer~$A$,
  $B$, e~$\epsilon>0$ como acima, temos
  \begin{equation*}
    \PP_{h\inR\cH}\big(h\text{ é $(A,B,\epsilon)$-bom}\big)
    \geq1-{\mu(A)\mu(B)(1-\mu(B))\over\epsilon^2|U|}.
  \end{equation*}
  [\textsl{Sugestão.} Use os resultados da Questão~\ref{Q:20}.]
  \datedue{30/10/2000}

\def\cSIM{c_{\text{SIM}}}
\def\cNAO{c_{\text{NAO}}}
\item\label{Q:22} No que segue, pomos~$\Sigma=\{0,1\}$.  Uma
  linguagem~$\cL\subset\Sigma^*$ pertence à classe~$\RP$ se existem uma
  constante~$\cSIM>0$ , um polinômio~$r(n)=r_\cL(n)$, e um
  predicado~$q(x,y)=q_\cL(x,y)$ verificável em tempo polinomial para os quais
  temos que se~$x\in\cL$, então~$|W_x|\geq\cSIM2^n$ e se~$x\notin\cL$,
  então~$W_x=\emptyset$, onde
  \begin{equation}
    \label{eq:W_x_def}
    W_x=\{y\in\Sigma^r\:q(x,y)=1\},
  \end{equation}
  $r=r(n)$, e~$n=|x|$ é o comprimento de~$x$.  Mostre que se~$\cL\in\RP$
  e~$\epsilon>0$ é uma constante positiva, então existe um algoritmo
  probabilístico de tempo polinomial~$\cA$ para o qual temos que
  \begin{equation}
    \label{eq:cA_RP+}
    \text{se }x\in\cL\text{ então }\PP(\cA(x)=1)\geq1-\epsilon,
  \end{equation}
  e
  \begin{equation}
    \label{eq:cA_RP-}
    \text{se }x\notin\cL\text{ então }\PP(\cA(x)=0)=1.
  \end{equation}
  Formalmente, um \textit{algoritmo probabilístico de tempo polinomial~$\cA$}
  é uma máquina de Turing com duas fitas de entrada que admite um
  polinômio~$r(n)=r_\cA(n)$ que se comporta como segue: $\cA$~recebe um par de
  palavras~$x$ e~$y\in\Sigma^*$ como entrada, com cada palavra em uma fita,
  com~$|y|=r(|x|)$; a máquina~$\cA$ devolve~$0$ ou~$1$ em tempo polinomial
  em~$|x|+|y|$.  Para cada~$n\geq0$, consideramos~$\Sigma^r$, onde~$r=r(n)$,
  como um espaço de probabilidade uniforme.  (Intuitivamente, $x$~é a
  instância e~$y\in\{0,1\}^{r(|x|)}$ é um string de `bits aleatórios.')
  Podemos considerar os eventos `$\cA(x,y)=u$' ($u\in\{0,1\}$).  Assim, por
  exemplo, a probabilidade que ocorre em~\eqref{eq:cA_RP+} é
  \begin{equation*}
    \PP_{y\inR\Sigma^r}(\cA(x,y)=1).
  \end{equation*}
  \datedue{30/10/2000}
  
\item Uma linguagem~$\cL\subset\Sigma^*$ pertence à classe~$\BPP$ se existem
  constantes~$0\leq\cNAO<\cSIM\leq1$, um polinômio~$r(n)=r_\cL(n)$, e um
  predicado~$q(x,y)=q_\cL(x,y)$ verificável em tempo polinomial para os quais
  temos que se~$x\in\cL$, então~$|W_x|\geq\cSIM2^r$ e se~$x\notin\cL$,
  então~$|W_x|\leq\cNAO2^r$, onde~$W_x$ é como em~\eqref{eq:W_x_def}.  Mostre
  que se~$\cL\in\BPP$ e~$\epsilon>0$ é uma constante positiva, então existe um
  algoritmo probabilístico de tempo polinomial~$\cA$ para o qual temos que
  \begin{equation}
    \label{eq:cA_BPP+}
    \text{se }x\in\cL\text{ então }\PP(\cA(x)=1)\geq1-\epsilon,
  \end{equation}
  e
  \begin{equation}
    \label{eq:cA_BPP-}
    \text{se }x\notin\cL\text{ então }\PP(\cA(x)=0)\geq1-\epsilon.
  \end{equation}
  \datedue{30/10/2000}
  
\item Defina a classe~$\BPP\mathbf{''}$ como sendo a família das
  linguagens~$\cL\in\Sigma^*$ que admitem um polinômio~$r(n)$ e um
  predicado~$q(x,y)$ para os quais temos que se~$x\in\cL$,
  então~$|W_x|>(1/r)2^r$ e se~$x\notin\cL$, então~$|W_x|\leq(1/r^2)2^r$.
  Mostre que~$\BPP=\BPP\mathbf{''}$. \datedue{30/10/2000}

\end{enumerate}



\end{document}

% Local Variables: 
% mode: latex
% eval: (Portug-mode)
% TeX-master: t
% End: 

