%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Short Sectioned Assignment
% LaTeX Template
% Version 1.0 (5/5/12)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% Original author:
% Frits Wenneker (http://www.howtotex.com)
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%----------------------------------------------------------------------------------------
% PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------
\documentclass[paper=a4, fontsize=11pt]{scrartcl} % A4 paper and 11pt font size
\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
\usepackage{fourier} % Use the Adobe Utopia font for the document - comment this line to return to the LaTeX default
\usepackage[english]{babel} % English language/hyphenation
\usepackage{amsmath,amsfonts,amsthm,amssymb} % Math packages
\usepackage{lipsum} % Used for inserting dummy 'Lorem ipsum' text into the template
\usepackage{sectsty} % Allows customizing section commands
\allsectionsfont{\centering \normalfont\scshape} % Make all sections centered, the default font and small caps
\usepackage{fancyhdr} % Custom headers and footers
\pagestyle{fancyplain} % Makes all pages in the document conform to the custom headers and footers
\fancyhead{} % No page header - if you want one, create it in the same way as the footers below
\fancyfoot[L]{} % Empty left footer
\fancyfoot[C]{} % Empty center footer
\fancyfoot[R]{\thepage} % Page numbering for right footer
\renewcommand{\headrulewidth}{0pt} % Remove header underlines
\renewcommand{\footrulewidth}{0pt} % Remove footer underlines
\setlength{\headheight}{13.6pt} % Customize the height of the header
\numberwithin{equation}{section} % Number equations within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)
\numberwithin{figure}{section} % Number figures within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)
\numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)
\setlength\parindent{0pt} % Removes all indentation from paragraphs - comment this line for an assignment with lots of text
%----------------------------------------------------------------------------------------
% TITLE SECTION
%----------------------------------------------------------------------------------------
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height
\newcommand{\argmax}{\arg\!\max}
\title{
\normalfont \normalsize
\textsc{University of Texas at Austin} \\ [25pt] % Your university, school and/or department name(s)
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge Stat/Discrete Methods for Sci Computing Problem Set 1 \\ % The assignment title
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
}
\author{Qi Lei} % Your name
\date{\normalsize\today} % Today's date or a custom date
\begin{document}
\maketitle % Print the title
%----------------------------------------------------------------------------------------
% PROBLEM 1
%----------------------------------------------------------------------------------------
\section{Exercise 1}
%\lipsum[2] % Dummy text
(1) Given the distribution $\frac{1}{3\sqrt{2\pi}}e^{-\frac{1}{2}(\frac{x}{3})2}$ what is the probability that $x>1$?\\
Solution: \begin{align}
\nonumber
P(x>1) &= \int_1^{\infty}\frac{1}{3\sqrt{2\pi}}xe^{-\frac{1}{2}(\frac{x}{3})^2}dx\\
\nonumber
&=\frac{1}{3\sqrt{2\pi}}\int_1^{\infty}\frac{1}{2}e^{-\frac{1}{18}x^2}dx^2~~~~~~~~~~~~~~~~~~(y\doteq \frac{1}{18}x^2)\\
\nonumber
&=\frac{3}{\sqrt{2\pi}}\int_{\frac{1}{18}}^{\infty}-e^{-y}dy\\
\nonumber
&=\frac{3}{\sqrt{2\pi}}e^{-\frac{1}{18}}
\end{align}
(2) Compare the Markov and Chebyshev bounds for the following probability distributions:\\
\begin{equation*}
\text{a})~~p(x)=\left\{
\begin{array}{rl}
1, & x=1\\
0, & \text{otherwise}
\end{array}\right.
\end{equation*}
\begin{equation*}
\text{b})~~p(x)=\left\{
\begin{array}{rl}
\frac{1}{2}, & 0\leq x\leq 2\\
0, & \text{otherwise}
\end{array}\right.
\end{equation*}
Solution:\\
For a), $E(x)=1$, $Var(x)=0$. So Markov inequality for a) is $Prob(x\geq a)\leq \frac{1}{a}$, while Chebyshev inequality for a) vanishes to $Prob(|x-1|>0)=0$.\\
For b), $E(x)=\int_0^2 \frac{1}{2}xdx=1$, $Var(x)=\int_0^2 \frac{1}{2}(x-1)^2dx=\frac{1}{3}$. So Markov inequality for b) is $Prob(x\geq a)\leq \frac{1}{a}$ (which is the same as in problem a)), while Chebyshev inequality for b) is $Prob(|x-1|>\sqrt{\frac{1}{3}}a)\leq \frac{1}{a^2}$.\\
\\
(3) Let $s$ be the sum of $n$ independent ransom variables $x_1,x_2,\cdots,x_n$ where for each $i$,\\
\begin{equation*}
x_i=\left\{
\begin{array}{rl}
0, & \text{Prob is }p\\
1, & \text{Prob is }1-p
\end{array}\right.
\end{equation*}
How large must $\delta$ be if we wish to have Prob($s>(1+\delta)n)<\epsilon$\\
Solution:\\
$E(x_i)=1-p,~Var(x)=(1-(1-p))^2(1-p)+(0-(1-p))^2p=p^2(1-p)+(1-p)^2p=p^2-p^3+p-2p^2+p^3=p-p^2$.\\
So $Prob(x\geq a)\leq \frac{1-p}{a}$ for each $i$. So $E(s)=n(1-p)$, $Var(s)=np(1-p)$.\\
Applying Markov inequality we get Prob($x\geq n(1+\delta))\leq\frac{n(1-p)}{n(1+\delta)}=\epsilon$. So $\delta=\frac{1-p}{\epsilon}-1$\\
Applying Chebyshev inequality we get Prob($|s-n(1-p)|>anp(1-p))\leq\frac{1}{a^2}=\epsilon$. So $a=\sqrt{\frac{1}{\epsilon}}$ Prob($x< n(1-p)-\sqrt{\frac{1}{\epsilon}}np(1-p)\leq \epsilon$. Therefore take $\delta\doteq 1-(1-p)(1-\sqrt{\frac{1}{\epsilon}}p)$. We have for sure that Prob$(x<n(1-\delta)=$Prob($x<n(1-p)(1-\sqrt{\frac{1}{\epsilon}}p)\leq \epsilon$.
\section{Exercise 2}
(1) For what values of $d$ do area, $A(d)$, and the volume, $V(d)$, of a $d$-dimensional unit sphere take on their maximum values?\\
\begin{eqnarray*}
A(d)&=&\frac{2\pi^{d/2}}{\Gamma(\frac{d}{2})}\\
\frac{A(d+2)}{A(d)}&=&\frac{2\pi}{d}\left\{
\begin{array}{rl}
<1, & d\geq 7\\
>1, & d\leq 6
\end{array}\right.
\end{eqnarray*}
This means $\cdots<A(11)<A(9)<A(7)>A(5)>A(3)$ and $\cdots<A(10)<A(8)>A(6)>A(4)$. $A(7)$ and $A(8)$ are the largest $A(d)$ for respectively odd $d$ and even $d$. While $A(7)=\frac{2\pi^{3.5}}{\Gamma(3.5)}\approx 33.07$, and $A(8)=\frac{2\pi^4}{\Gamma(4)}\approx 32.47$. So $A(7)=\frac{2\pi^{3.5}}{\Gamma(3.5)}$ is the largest $A(d)$ for every $d\geq 1$.\\
\begin{eqnarray*}
V(d)&=&\frac{2\pi^{d/2}}{d\Gamma(\frac{d}{2})}\\
\frac{V(d+2)}{V(d)}&=&\frac{2\pi }{d+2}\left\{
\begin{array}{rl}
<1, & d\geq 5\\
>1, & d\leq 4
\end{array}\right.
\end{eqnarray*}
This means $V(5)$ and $V(6)$ are the largest volumes $V(d)$ fo respectively odd $d$ and even $d$. Turns out $V(5)=\frac{2\pi^{2.5}}{5\Gamma(2.5)}\approx 5.26~(>V(6)\approx 5.17)$ is the largest volume. \\
\\
(2) How do the area and the volume of a sphere with \textit{radius}=2 behave as the dimension of the space increases? What if the radius was larger than two but independent of $d$?\\
\textit{radius}=2
\begin{eqnarray*}
A(d)&=&\frac{2\pi^{d/2}2^{d-1}}{\Gamma(\frac{d}{2})}\\
\frac{A(d+2)}{A(d)}&=&\frac{8\pi}{d}\left\{
\begin{array}{rl}
<1, & d\geq 26\\
>1, & d\leq 25
\end{array}\right.
\end{eqnarray*}
This means $A(26)$ and $A(27)$ are the largest area $A(d)$ fo respectively even $d$ and odd $d$. Turns out $A(26)=\frac{2^14\pi^{13}}{\Gamma(13)}\approx 4.07\times 10^5~(>V(27)\approx 4.04\times 10^5)$ is the largest area. \\
\begin{eqnarray*}
V(d)&=&\frac{2\pi^{d/2}2^d}{d\Gamma(\frac{d}{2})}\\
\frac{V(d+2)}{V(d)}&=&\frac{8\pi}{d+2}\left\{
\begin{array}{rl}
<1, & d\geq 24\\
>1, & d\leq 23
\end{array}\right.
\end{eqnarray*}
This means $V(24)$ and $V(25)$ are the largest volumes $V(d)$ fo respectively even $d$ and odd $d$. Turns out $V(24)=\frac{2^22\pi^{12}}{3\Gamma(12)}\approx 3.24\times 10^4~(>V(25)\approx 3.21\times 10^4)$ is the largest volume. \\
As we can see from the previous analysis, both area and volume increase with respect to d for smaller d and decrease when d is large.
And when radius is larger than 2, this boundary between increase and decrease will be larger, meaning $\argmax_d A(d)$ and $\argmax_d V(d)$ will be larger. \\
\\
(3) What function of $d$ would the radius need to be for a sphere of radius $r$ to have approximately constant volume as the dimension increases?\\
\begin{eqnarray*}
V(d,r)&=&\frac{2\pi^{d/2}r^d}{d\Gamma(\frac{d}{2})}\\
\frac{V(d+2,r)}{V(d,r)}&=&\frac{2\pi r^2}{d+2}=1\\
\therefore r&=&\sqrt{\frac{d+2}{2\pi}}\\
\text{Then}~ V(d)&=&\left\{
\begin{array}{rl}
\sqrt{\frac{6}{\pi}}, & d~\text{odd}\\
2, & d~\text{even}
\end{array}\right.
\end{eqnarray*}
\section{Exercise 3}
(1) For each of $a=2$, and 3 give a probability distribution for a nonnegative random variable $x$ were Prob$(x\geq aE(x))=\frac{1}{a}.$\\
Solution:\\
\begin{equation*}
\text{a=2:}~~p(x)=\left\{
\begin{array}{rl}
1/2, & x=2\\
1/2, & x=0
\end{array}\right.\\
E(x)=1.\\
\text{Prob}(x\geq aE(x))=\text{Prob}(x\geq 2)=\frac{1}{2}=\frac{1}{a}
\end{equation*}
\begin{equation*}
\text{a=3:}~~p(x)=\left\{
\begin{array}{rl}
1/3, & x=3\\
2/3, & x=0
\end{array}\right.
E(x)=1.\\
\text{Prob}(x\geq aE(x))=\text{Prob}(x\geq 3)=\frac{1}{3}=\frac{1}{a}
\end{equation*}
\\
(2)
\begin{equation*}
p(x)=\left\{
\begin{array}{rl}
1/a, & x=a\\
1-1/a, & x=0
\end{array}\right.
E(x)=1.\\
\text{Prob}(x\geq aE(x))=\text{Prob}(x\geq a)=\frac{1}{a}
\end{equation*}
%------------------------------------------------
\section{Exercise 4}
Suppose sphere 1 is centered at origin, while sphere 2 is centered at $ae_1=(a,0,0,\cdots,0)$. The intersection becomes
\begin{equation*}
\left\{
\begin{array}{rl}
(x_1-a)^2+x_2^2+\cdots+x_d^2\leq 1\\
x_1^2+x_2^2+\cdots+x_d^2\leq 1
\end{array}\right.
\end{equation*}
Consider the cap of $S_1$
\begin{equation*}
\left\{
\begin{array}{rl}
x_1\geq \frac{a}{2}\\
x_1^2+x_2^2+\cdots+x_d^2\leq 1
\end{array}\right.
\end{equation*}
It's easy to see this cap is also contained in $S_2$. ($(x_1-a)^2+x_2^2+\cdots+x_d^2\leq (x_1-a)^2+1-x_1^2\leq (\frac{a}{2}-1)^2+1-(\frac{a}{2})^2=1$)
Likewise the cap of $S_2$
\begin{equation*}
\left\{
\begin{array}{rl}
x_1\leq \frac{a}{2}\\
(x_1-a)^2+x_2^2+\cdots+x_d^2\leq 1
\end{array}\right.
\end{equation*}
is also contained in $S_1$. So by considering the volume of these two caps we can decide the volume of their intersection.\\
Applying the Lemma with the plane $x_1=\frac{a}{2}$, ($c=\frac{a\sqrt{d-1}}{2}$) we get the fraction of the volume of the cap is below $\frac{2}{c}e^{-\frac{c^2}{2}}=\frac{4}{a\sqrt{d-1}}e^{-\frac{a^2(d-1)}{8}}$
\end{document}
