\documentclass{article}
\usepackage{amsmath}
\usepackage{amsthm}



\newcommand{\handout}[5]{
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { {\bf 18.409 The Behavior of Algorithms in Practice} \hfill #2 }
       \vspace{4mm}
       \hbox to 5.78in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{Lecturer: #3}{Scribe: #4}{Lecture #1}}



\begin{document}
\lecture{18}{4/30/2002}{Dan Spielman}{Stephan Kalhamer}


\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{theorem}{Theorem}
\newtheorem{pf}{Pf}

\setlength{\topmargin}{-0.50in} \setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in} \setlength{\textwidth}{6in}
\addtolength{\parskip}{2pt} \addtolength{\itemsep}{0.1in}
\parskip 1.5ex

\renewcommand{\baselinestretch}{1.25}


\section{left off:}

$Prob[ang(z,\delta\Delta(a_{\pi_1}$,...,$a_{\pi_d})) < \epsilon
\mid opt \Delta_2(a...a_n)=\pi_1...\pi_d]$ where $a$...$a_n$ are
the dist. according to $\prod_{i=1}^n \mu_i(\alpha_i)$, $\mu_i$
are Gaussian, $var \sigma^2 \leq1$, center norm $\leq1$.

\section{key idea:}

change of variables
\[a_{\pi_1} \ldots a_{\pi_d} \rightarrow \parallel w \parallel =1, r \geq0 \mbox{ such that} <w,a_{\pi_i}> =r\]
\[b_{\pi_1} \ldots b_{\pi_d}\] be local coords. of $a_{\pi_1} \ldots
a_{\pi_d}$on that plane.

observe that unlikely $\parallel a_i \parallel \geq 1+4 \sqrt{d
\log n}$ so let $\Gamma = 1+\sqrt{d \log n}$.

So can say:
\[ang(z,\delta\Delta(a_{\pi_1}, \ldots ,a_{\pi_d})) \geq \frac{dist(z^{w,r},\delta\Delta(b_{\pi_1}, \ldots ,b_{\pi_d}))<z,w>}{3r}\]
Let $z^{w,r}$ be a point along ray direction on plane w,r, need to
bound:
\[Pr_{w,r,b_{p_1}, \ldots ,b_{p_d}} [\frac{dist(z,\delta\Delta(b_{\pi_1}, \ldots ,b_{\pi_d}))<z,w>}{3r} <\epsilon]\]
where $w,r,b_{p_1}, \ldots ,b_{p_d}$ have density:
\[[\prod_{j \in {\pi_1 \ldots \pi_d}}\int_{a_j}[<w,a_j> \leq r]\mu_i (a_j)](\prod_{j=1}^d\mu_{\pi_i}(a_{\pi_i}))[z^{w,r} \in \Delta(b_{\pi_1}, \ldots ,b_{\pi_d})]Vol(\Delta(b_{\pi_1}, \ldots ,b_{\pi_d}))\]
(suitably re-normalized)

for today show: $\forall z \forall w,r$ such that $\parallel
z^{w,r} \parallel \leq \Gamma$
\[Pr_{b_1}, \ldots ,{b_d}[dist(z^{w,r},\delta\Delta(b_{\pi_1}, \ldots ,b_{\pi_d}))<\epsilon]<\frac {16e^4\Gamma^2(1+\Gamma)}{\sigma^4}\epsilon\]
Where $b_{\pi_1}, \ldots ,b_{\pi_d}$ have density $(\prod_{i=1}^d
\mu \pi_i (a_{\pi_i}))Vol(\Delta(b_{\pi_1}, \ldots
,b_{\pi_d}))[z^{w,r} \in \Delta(b_{\pi_1}, \ldots ,b_{\pi_d})]$
where the first factor of the very last formula is in terms of
$b_{\pi_i}$s Gaussian each. $Var \sigma^2$ center norm $\leq1$.

\begin{theorem} re-stated

Let $b_1 \ldots b_d$ be points in $\Re^{d-1}$

with density $\prod_{i=1}^d \mu_i(b_i) Vol(\Delta(b_1, \ldots
,b_d))[z \in \Delta(b_1, \ldots ,b_d)]$ where $\parallel z
\parallel \leq \Gamma, \mu_i$ Gaussian, $var \sigma^2 \leq1$, norm
center $\leq1$.
\end{theorem}

What is $Pr[dist(z,\delta\Delta(b_1, \ldots ,b_d))<\epsilon]$?

Two steps:

1. Show $b_1$ unlikely near aff. $(b_1 \ldots b_d)$

2. Given $b_1$ is far from aff. $(b_1 \ldots b_d)$, unlikely too
close to aff. $(b_1 \ldots b_d)$. (where aff. denotes an affine
line)

to 1: $Pr[dist(b_1, aff. (b_2 \ldots b_d))<
\epsilon]<e^2(\frac{d(1+\Gamma)\epsilon}{\sigma^2})^3$

to 2: $Pr[dist(z, aff. (b_2 \ldots b_d))< \epsilon dist(b_1, aff.
(b_2 \ldots b_d))< \frac{2e^3d(2p)^2\epsilon}{\sigma^2}]$

These imply Theorem 1. We use change of variables to show 1:

Make z the origin (for notational simplicity), so now the
distances have centers of norm $\leq \Gamma +1$.

Let $\parallel \tau \parallel =1, t \geq0$ be such that
$<b_i,\tau>=t$ for $i=1..d$ and let $c_2..c_d$ be the local
coords. of the  $b_i$s in that plane. Jac is
$Vol(\Delta(c_2..c_d))$
\[dist(b, aff.(b_2..b_d))=t-<b_1,\tau>\]

Let $l=-<b_1,\tau>$, let $c_1$ be the projection of $b_1$ onto the
plane spee by $\tau,t$.

$Pr_{\tau,t,l,c_1, \ldots ,c_d}[(l+t)<\epsilon]$ with density
\[(\prod_{i=1}^d \mu_i(b_i))Vol(\Delta(b_1 \ldots b_d))[O \in \Delta(b_1 \ldots
b_d)]Vol(\Delta(c_2 \ldots c_d))\]

where $Vol(\Delta(c_2 \ldots c_d))$ equals $(l+t)Vol(\Delta(c_2
\ldots c_d)) \sim (1+\alpha)t$  (*)

Note: for any $c_1,c_2,\ldots,c_d,l,t$ such that $O \in \Delta
(b_1,\ldots,b_d)$ if mult. l,t by const.

$\rightarrow$ cl ct still have $O \in \Delta (b_1,\ldots,b_d)$.

let $l=\alpha t$ gives Jacobian $\mid \frac{\delta l}{\delta
\alpha}\mid = t$

$(*)\sum \max_{c_1, \ldots ,c_d,t,\alpha, s.t.
O\in\Delta(b_1,\ldots,b_d)} Pr[(1+\alpha)t<\epsilon]$

where t has density

$(\prod_{i=1}^d \mu_i(b_i))t^2$(, near O in small region looks
like a constant)

We will actually bound
\[Pr[t max(1,\alpha)<\epsilon]\geq Pr[(1+\alpha)t<\epsilon]\]

$b_2=(t,c_2)$

$b_1(-\alpha t, c_1)$

can write this way:

$\mu$ is centered at points of norm $\leq 1+ \Gamma$

So,we claim for $0 \leq t \leq \frac{\sigma ^2}{d(1+ \Gamma)}$

$\mu_i(t,b_i)$ varies by at most $e^\frac{2}{d}$ (former, we
showed similar with no ds)

For $0 \leq t \leq \frac{\sigma ^2}{d(1+ \Gamma)}$

$b\mu_1(-\alpha t, b_1)$ varies by at most $e^\frac{2}{d}$,
setting $t_0 = \frac{\sigma ^2}{d(1+ \Gamma)}
min(1,\frac{1}{\alpha})$ then
\[\frac{\max_{0 \leq t \leq t_0} \prod_{i=1}^d \mu_i(b_i)}{\min_{0 \leq t \leq t_0} \prod_{i=1}^d \mu_i(b_i)} \leq \epsilon^2 \mbox{ (**)}\]

So by  the following Proposition 1, we have

$Pr[t<\epsilon t_0] \leq e^2 \epsilon ^3$ or $Pr[t max(1,\alpha)<
\frac{\epsilon \sigma ^2}{d(1+\Gamma)}] \leq e^2 \epsilon ^3$

$\Rightarrow Pr[t max(1,\alpha)< \epsilon] \leq e^2
(\frac{d(1+\Gamma)}{\sigma ^2} \epsilon)^3$

\begin{proposition} Let t be distributive according to $f(t)t^2$
where
\[\frac{\max_{0 \leq t \leq t_0} f(t)}{\min_{0 \leq t \leq t_0} f(t)} \leq \epsilon^2 \]
then
\[Pr[t<\epsilon t_0] \leq e^2 \epsilon ^3\]
\end{proposition}

\begin{pf} $Pr[t<\epsilon t_0] \leq \frac{Pr[t<\epsilon t_0]}{Pr[t<t_0]}= \frac{\int_{t=0}^{\epsilon t_0 f(t)t^2}}{\int_{t=0}^{t_0 f(t)t^2}} \leq \frac{\max_{0 \leq t \leq \epsilon t_0} f(t)}{\max_{0 \leq t \leq t_0} f(t)} \frac{\int_{t=0}^{\epsilon t_0} t^2}{\int_{t=0}^{t_0} t^2} \leq e^2 \epsilon ^3$
\end{pf}

\bibliographystyle{amsalpha}
\bibliography{bap}

\end{document}
