\documentclass[11pt]{article} 
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsxtra}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{enumitem}
\usepackage{url}
\usepackage{color,hyperref}
\hypersetup{colorlinks,breaklinks,
             linkcolor=blue,urlcolor=blue,
           anchorcolor=blue,citecolor=blue}

\usepackage[margin=3cm]{geometry}
\newcommand{\eps}{\varepsilon}
\newcommand{\Z}{\mathbb{Z}}
\renewcommand{\L}{\mathcal{L}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\K}{\mathcal{K}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\dist}{\text{dist}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}
\renewcommand{\phi}{\varphi}
\newcommand{\limn}{\lim_{n\to \infty}}
\newenvironment{bp}{\color{blue}\begin{proof}}{\end{proof}}
\newenvironment{bs}{\color{blue}\begin{proof}[Solution]}{\end{proof}}
\renewcommand{\bar}[1]{\overline{#1}}
\renewcommand{\Im}{\text{Im}}
\renewcommand{\Re}{\text{Re}}
\newcommand{\dudn}{\frac{\partial u}{\partial n}}
\def\Xint#1{\mathchoice
{\XXint\displaystyle\textstyle{#1}}%
{\XXint\textstyle\scriptstyle{#1}}%
{\XXint\scriptstyle\scriptscriptstyle{#1}}%
{\XXint\scriptscriptstyle\scriptscriptstyle{#1}}%
\!\int}
\def\XXint#1#2#3{{\setbox0=\hbox{$#1{#2#3}{\int}$ }
\vcenter{\hbox{$#2#3$ }}\kern-.6\wd0}}
\def\ddashint{\Xint=}
\def\dashint{\Xint-}

\theoremstyle{plain} \newtheorem{theorem}{Theorem}
\newtheorem*{theorem*}{Theorem}
\newtheorem{conjecture}{Conjecture}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}

\theoremstyle{definition}
\newtheorem{algorithm}{Algorithm}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
\newtheorem{exercise}{Exercise}
\theoremstyle{remark}
\newtheorem{acknowledgement}{Acknowledgement}
\newtheorem{remark}{Remark}
\numberwithin{equation}{section}
\numberwithin{exercise}{section}
\numberwithin{example}{section}
\numberwithin{theorem}{section}
\numberwithin{lemma}{section}
\numberwithin{proposition}{section}
\numberwithin{corollary}{section}
\numberwithin{remark}{section}

\begin{document}

{ \large \textbf{\textsc{Math 8385 -- Homework 3 (Due Wednesday December 18)}}}
\thispagestyle{empty}
\vspace{0.1in}

Complete any one of the problems below.
\begin{enumerate}
\item Perform some numerical experiments to test the convergence rates from Theorems 5.24 and 5.37 in the course notes. What rates of convergence do you see numerically? Is the rate better than provided in the theorems? [If you wish to do this problem, I can provide Matlab or Python code to help you get started.] 
\item Show that the convergence rate in Theorem 5.24 can be improved to read 
\[\max_{x\in \mathcal{X}_N}|u_{N,\eps}(x) -u(x)| \leq C(\|u\|_{C^4(U)}+1)(\lambda + \eps^2)\]
with probability at least $1-C\exp\left( -cN\eps^{n+2}\lambda^2 + 4\log(N) \right)$, provided $\rho\in C^3(\bar{U})$.  If you like, you may prove the result for $\rho\equiv \text{Constant}$ to simplify the proof.
\item  Prove a Poincar\'e inequality on the graph with high probability. That is, show that there exists a constant $C>0$, depending only on $U$, such that with probability at least $1-CN\exp\left( -cN\eps^n \right)$ 
\[\|u\|_{L^2(\mathcal{X}_N)} \leq C\|\nabla_{N,\eps} u\|_{L^2(\mathcal{X}_N\times \mathcal{X}_N)}\]
for all $u\in L^2(\mathcal{X}_N)$ with $u(x)=0$ for all $x\in \mathcal{X}_N\cap \partial_\eps U$.
\item For the variational methods, we proved discrete to continuum control in two steps: First in Section 5.5.2 we studied the extension operator $E_\delta$ that extends a function on the graph to a piecewise constant function on $U$, and then in Section 5.5.3 we constructed a very particular smoothing operator $\Lambda_{\eps,\delta}$, and our discrete to continuum operator was the composition $\Lambda_{\eps,\delta}E_\delta$. 

Let us consider another approach where we skip the extension step and apply the smoothing directly to the discrete function. That is, we define the smoothing extension operator $K_\delta:L^2(\mathcal{X}_N) \to L^2(U)$ by
\[K_\eps u(x) = \frac{1}{\theta_{N}(x)}\sum_{y\in \mathcal{X}_N}\psi_{\eps,0}(|x-y|)u(y),\]
where
\[\theta_N(x) = \frac{1}{N}\sum_{y\in \mathcal{X}_N}\psi_{\eps,0}(|x-y|).\]
Can you prove discrete to continuum convergence using $K_\eps$  in place of $\Lambda_{\eps,\delta}E_\delta$? That is, prove an analogous result to Theorem 5.37 using $K_\eps u_{N,\eps}$ as the extension and smoothing operator. How does the result change, in particular, is the convergence rate different (better or worse), and is the probability with which the rate holds different. [Warning: This is a hard problem.]
\end{enumerate}
\end{document}

