\documentclass[11pt,addpoints,answers]{exam}

% Packages
\usepackage{fullpage}
\usepackage{latexsym,amssymb,amsfonts,amsmath,mathrsfs,float, amsthm}
\usepackage[font=small,labelfont=bf, width=.618\textwidth]{caption} % custom captions
\usepackage{xcolor}
\usepackage{tikz, graphics, enumerate}
\usepackage{hyperref}


% Paragraph indentation and spacing
\newcommand{\parset}{
	\setlength{\parskip}{3mm}
  	\setlength{\parindent}{0mm}}
	
% Probability
  \DeclareMathOperator{\var}{Var}
  \renewcommand{\Pr}{\mbox{\rm Pr}}	
  \newcommand{\Exp}{{\mathbb{E}}}
  \newcommand{\E}{\mathbb{E}}

% Sets 
  \newcommand{\R}{\mathbb{R}} % reals
  \newcommand{\C}{\mathbb{C}} % complex numbers
  \newcommand{\N}{\mathbb{N}} % natural numbers
  \newcommand{\Z}{\mathbb{Z}} % integers
  \newcommand{\F}{\mathbb{F}} % field
  \newcommand{\K}{\mathbb K} % field
  \newcommand{\T}{\mathbb T} % circle
\newcommand{\B}{\mathcal{B}} % ball
  \newcommand{\pmset}[1]{\{-1,1\}^{#1}} % hypercube in +-1 basis
  \newcommand{\bset}[1]{\{0,1\}^{#1}} % hypercube
  \newcommand{\sphere}[1]{S^{#1-1}} % real unit sphere of dimension #1
  \newcommand{\ball}[1]{B_{#1}} % real unit ball of dimension $1
  \newcommand{\Orth}[1]{O(\R^{#1})} % orthogonal group
  \DeclareMathOperator{\im}{im} % image
  \DeclareMathOperator{\vspan}{Span} % kernel
  \newcommand{\1}{\mathbf{1}}
  \DeclareMathOperator{\Cball}{\mathcal C}
  \DeclareMathOperator{\cay}{Cay} 
  \DeclareMathOperator{\sol}{Sol} 
\DeclareRobustCommand{\stirling}{\genfrac\{\}{0pt}{}}

% Miscellaneous
  \newcommand{\st}{:\,} % "such that" to define sets
  \newcommand{\ie}{{i.e.}}  
  \newcommand{\eg}{{e.g.}} 
  \newcommand{\eps}{\varepsilon}
  \newcommand{\ip}[1]{\langle #1 \rangle}
  \newcommand{\cF}{{\mathcal F}}   
  \DeclareMathOperator{\U}{\mathcal{U}}
  \DeclareMathOperator{\sign}{sign}
  \newcommand{\poly}{\mbox{\rm poly}}
  \newcommand{\ceil}[1]{\lceil{#1}\rceil}
  \newcommand{\floor}[1]{\lfloor{#1}\rfloor}
  \DeclareMathOperator{\Tr}{\mathsf{Tr}}
  \DeclareMathOperator{\diag}{diag}
  \DeclareMathOperator{\patt}{patt}
  \DeclareMathOperator{\argmin}{arg\,min}
  \DeclareMathOperator{\spec}{Spec}
  \DeclareMathOperator{\enc}{\sf Enc}
  \DeclareMathOperator{\dec}{\sf Dec}
  \DeclareMathOperator{\diam}{diam} 
  \DeclareMathOperator{\spn}{span} 
  \DeclareMathOperator{\geom}{gm}
\DeclareMathOperator{\sinc}{sinc}
\DeclareMathOperator{\disc}{disc}
\DeclareMathOperator*{\argmax}{arg\,max}
  \newcommand{\infnorm}{{\ell_\infty, \ldots, \ell_\infty}}
  \newcommand{\pnorm}{{\ell_p,\dots,\ell_p}}
  \newcommand{\tnorm}{{\ell_t,\dots,\ell_t}}
  
  
% Enviroments
  \newcommand{\beq}{\begin{equation}}
  \newcommand{\eeq}{\end{equation}}
  \newcommand{\beqn}{\begin{equation*}}
  \newcommand{\eeqn}{\end{equation*}}
  \newcommand{\beqr}{\begin{eqnarray}}
  \newcommand{\eeqr}{\end{eqnarray}}
  \newcommand{\beqrn}{\begin{eqnarray*}}
  \newcommand{\eeqrn}{\end{eqnarray*}}
  \newcommand{\bmline}{\begin{multline}}
  \newcommand{\emline}{\end{multline}}
  \newcommand{\bmlinen}{\begin{multline*}}
  \newcommand{\emlinen}{\end{multline*}}
  
  \makeatletter

% END OF SUPPLIED VARIABLES

  \chead{\large \textbf{Week 6 Questions}}

  \lhead{\small
    \textbf{{Boolean Functions}\\{Northwestern \\Winter 2021}}}

  \rhead{\small \textbf{Instructor:
     {Shravas Rao}}\\\textbf{Student}: FIRSTNAME LASTNAME}

  \setlength{\headheight}{20pt}
  \setlength{\headsep}{16pt}                       
  \headrule
% execute homework commands

\begin{document}

\pagestyle{head}                % put header on every page

\medskip

\section*{Lecture 10}

\begin{questions}
\question (O 2.43) Show that for all functions $f:\{-1, 1\}^n \rightarrow \{-1, 1\}$
\[
\frac{1-e^{-2}}{2n} \mathbf{I}[f] \leq NS_{1/n}[f] \leq \frac{1}{n}\mathbf{I}[f].
\]
\begin{solution}

  \end{solution}

\question (O 5.30) Consider the sequence of LTFs $f_n: \{-1, 1\}^n \rightarrow \{0,1\}$ defined by $f_n(x) = 1$ if and only if $\sum_{i=1}^n \frac{1}{\sqrt{n}} x_i > t$.  (I.e., $f_n$ is the indicator of the Hamming ball of radius $\frac{n}{2} - \frac{t}{2}\sqrt{n}$ centered at $(1, 1, \ldots, 1)$.) Show that
        \[
            \lim_{n \to \infty} \E[f_n] = \overline{\Phi}(t), \qquad \lim_{n \to \infty} \mathbf{W}^{1}[f_n] = \phi(t)^2,
        \]
        where $\phi$ is the pdf of a standard Gaussian and $\overline{\Phi}$ is the complementary cdf (i.e., $\overline{\Phi}(u) = \int_{u}^\infty \phi$).  
(Hint for $\mathbf{W}^{1}[f_n]$: use symmetry to show it equals the square of $\E[f_n(x) \sum \frac{1}{\sqrt{n}}x_i]$.)

\begin{solution}

  \end{solution}

\question (O 5.32) Consider the sequence of LTFs defined in the previous problem.  Show that
\[
\lim_{n \to \infty} Stab_{\rho}[f_n] = \Pr[z_1 > t, z_2 > t]
\]
where $z_1$ and $z_2$ are standard Gaussians with correlation $\E[z_1z_2] = \rho$.

\begin{solution}

  \end{solution}

\question (O 5.28) For integer $0 \leq j \leq n$, define $\mathscr{K}_j: \{-1, 1\}^n \rightarrow \R$ by $\mathscr{K}_j(x) = \sum_{|S| = j} x^S$.  Since $\mathscr{K}_j$ is symmetric, the value $\mathscr{K}_j(x)$ depends only on the number $z$ of $-1$'s in $x$;  or equivalently, on $\sum_{i=1}^n x_i$.  Thus we may define $K_j: \{0, 1, \dots, n\} \rightarrow \R$ by $K_j(z) = \mathscr{K}_k(x)$ for any $x$ with $\sum_i x_i = n - 2z$.

\begin{parts}
\part Show that $K_j(z)$ can be expressed as a degree-$j$ polynomial in $z$. It is called the \emph{Kravchuk} (or \emph{Krawtchouk}) \emph{polynomial} of degree $j$. (The dependence on $n$ is usually implicit.)
\begin{solution}

  \end{solution}

\part Show that 
\[
\sum_{j=0}^n \mathscr{K}_j(x) = \begin{cases}2^n & \text{if } x = (1, 1, \ldots, 1) \\ 0 & \text{otherwise} \end{cases}
\]
\begin{solution}

  \end{solution}

\part Show for $\rho \in [-1, 1]$ that $\sum_{j=0}^n \mathscr{K}_j(x) \rho^j = 2^n \Pr[ y = (1, 1, \ldots, 1)]$, where $y \sim N_{p}(x)$.
\begin{solution}

  \end{solution}

\part Deduce the generating function identity, that $K_j(z)$ is the coefficient of $\rho^j$ in $(1-\rho)^x(1+\rho)^{n-x}$.
\begin{solution}

  \end{solution}
\end{parts}


\end{questions}

\section*{Lecture 11}

\begin{questions}
\question  Let $S_1, \ldots, S_t$ be a collection of disjoint subsets of $[n]$ such that $|\widehat{f}(S_i)| \leq \eps$ for all $i$.
Give appropriate generalizations of the level-$1$ inequality and $2/\pi$ theorem.
\begin{solution}

\end{solution}

\question (O 9.1) For every $1 < b < B$ show that there is a $b$-reasonable random variable $X$ such that $1+X$ is not $B$-reasonable.
\begin{solution}

  \end{solution}

\question Show that if $X$ is a nonnegative random variable with $\Pr[X > K] = \delta$ and $\E[X] \geq L > K$
then $\E[X^2] \geq (L-K)^2/\delta$.
\begin{solution}

\end{solution}

\end{questions}
\end{document}