\documentclass[11pt]{article}

%% \def\showanswer{1}

\usepackage{exercises}
\usepackage[numbers]{natbib}
\usepackage{xr}

\externaldocument{ex4-sol}

\usebiggeometry
\bluehyperref

\newcommand{\cg}{\mathop{\textup{cg}}}
\newcommand{\optgap}{\mathsf{gap}}
\newcommand{\size}{\mathop{\textup{size}}}

\begin{document}

\setcounter{section}{9}

\title{ee364m Exercise Set \thesection\
  \ifdefined\showanswer
  Solutions
  \fi
}

\author{Due date: March 13, 11:59pm}
\date{}
\maketitle

\begin{question}[Properties of log-concave distributions]
  A probability distribution $P$ on $\R^n$ is \emph{log concave} if
  \begin{equation*}
    P(\lambda A + (1 - \lambda) B) \ge P(A)^\lambda P(B)^{1 - \lambda}
  \end{equation*}
  for all (measurable) $A, B \subset \R^n$ and $\lambda \in [0, 1]$.
  \begin{enumerate}[(a)]
  \item Let $P$ have density $p(x) = e^{-u(x)}$ where $u : \R^n \to \R \cup
    \{+\infty\}$ is convex.  Use the Pr\'{e}kopa-Leindler inequality to show
    that $P$ is log-concave.
  \item Let $P$ be a log-concave probability distribution on $\R^n$ with
    continuous density $p$. Show that $p(x) = e^{-u(x)}$ for a convex $u :
    \R^n \to \R \cup \{+\infty\}$.
  \item Let $P$ be a log-concave probability distribution. Show
    that for any convex symmetric $A \subset \R^n$ and $r \ge 1$ that
    \begin{equation*}
      1 - P(r A) \le \left(\frac{1 - P(A)}{P(A)}\right)^{r/2}
      \sqrt{P(A) (1 - P(A))},
    \end{equation*}
    where $r A = \{r x \mid x \in A\}$.
    \emph{Hint.} First, show that if
    $y \not \in rA$ and $x \in A$, then
    $z = \frac{2}{r + 1} y + \frac{r - 1}{r + 1} x$ must be outside $A$.
    Conclude that
    \begin{equation*}
      A^c \supset \frac{2}{r + 1} (rA)^c + \frac{r - 1}{r + 1} A
    \end{equation*}
    and then apply log-concavity.
  \end{enumerate}
  As a comment, the last problem shows that if $P(A)$ is reasonably
  large---even bigger than $\half$---then $rA$ covers an exponentially
  large portion of the probability mass of $P$. For example,
  if $P(A) \ge \frac{e}{e + 1} \approx .731$, then
  $P(rA) \ge 1 - e^{-r/2} \sqrt{e} / (e + 1)
  > 1 - \half e^{-r/2}$.
\end{question}

\end{document}