On the sum of absolute value of Gauss variables Currently I meet with the following interesting problem.
Let $x_1,\cdots,x_n$ be i.i.d standard Gaussian variables. How to calculate the probability distribution of the sum of their absoulte value, i.e., how to calculate
$$\mathbb{P}(|x_1|+\cdots+|x_n|\leq nt).$$
Here I use $nt$ instead of $t$ for sake of possible concise formula.
I cannot find out the exact value. However, a practical lower bound is also good. Here practical means the ratio between the exact value and lower bound is independent of $n$ and $t$, and is small.
Thanks very much!
 A: The moment generating function of a standard Gaussian R.V. $x$ is $\mathbb{E}[e^{tx}] = e^{t^2/2}$ for all $t \in \mathbb{R}$.
Since $x_k$ is a standard Gaussian (and thus has a symmetric distribution), for any $t \in \mathbb{R}$, the moment generating function of $|x_k|$ can be bounded by$$\mathbb{E}\left[e^{t|x_k|}\right] \le \mathbb{E}\left[e^{t|x_k|} + e^{-t|x_k|}\right] = \mathbb{E}\left[e^{tx_k} + e^{-tx_k}\right] = \mathbb{E}\left[e^{tx_k}\right] + \mathbb{E}\left[e^{-tx_k}\right] = 2\mathbb{E}\left[e^{tx_k}\right] = 2e^{t^2/2}.$$
Now, we simply repeat the usual derivation for Chernoff bounds. For any $\lambda > 0$, we have
\begin{align*}
\mathbb{P}\left\{\dfrac{1}{n}\sum_{k = 1}^{n}|x_k| \ge t\right\} &= \mathbb{P}\left\{\exp\left(\dfrac{\lambda}{n}\sum_{k = 1}^{n}|x_k|\right) \ge e^{\lambda t}\right\} & \text{since} \ y \to e^{\lambda y} \ \text{is increasing}
\\
&\le e^{-\lambda t}\mathbb{E}\left[\exp\left(\dfrac{\lambda}{n}\sum_{k = 1}^{n}|x_k|\right)\right] & \text{Markov's Inequality}
\\
&= e^{-\lambda t}\mathbb{E}\left[\prod_{k = 1}^{n}e^{\tfrac{\lambda}{n}|x_k|}\right]
\\
&= e^{-\lambda t}\prod_{k = 1}^{n}\mathbb{E}\left[e^{\tfrac{\lambda}{n}|x_k|}\right] & \text{Since} \ x_1,\ldots,x_n \ \text{are independent}
\\
&\le e^{-\lambda t}\prod_{k = 1}^{n}2e^{\lambda^2/(2n^2)} & \text{use the mgf bound above}
\\
&= 2^ne^{\lambda^2/(2n)-\lambda t}
\end{align*}
Now take $\lambda = nt$ (which minimizes the upper bound) to get $$\mathbb{P}\left\{\dfrac{1}{n}\sum_{k = 1}^{n}|x_k| \ge t\right\} \le 2^ne^{-nt^2/2} \quad \text{for all} \quad t > 0.$$
EDIT: I just realized this is equivalent to using a union bound over the $2^n$ events of the form $\dfrac{1}{n}\displaystyle\sum_{k = 1}^{n}\epsilon_kx_k \ge t$ where $\epsilon_1,\ldots,\epsilon_k \in \{-1,1\}$, and then applying the usual Gaussian tail bound.
A: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\on}[1]{\operatorname{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
&\bbox[5px,#ffd]{\mathbb{P}\pars{\verts{x_{1}} + \cdots + \verts{x_{n}} \leq nt}}
\\[5mm] \equiv &\
\int_{-\infty}^{\infty}
{\exp\pars{-x_{1}^{2}/2} \over \root{2\pi}}\cdots
\int_{-\infty}^{\infty}
{\exp\pars{-x_{n}^{2}/2} \over \root{2\pi}}\ \times
\\[2mm] &\
\underbrace{\bracks{%
nt - \verts{x_{1}} - \cdots - \verts{x_{n}} > 0}}
_{\mbox{Heaviside Theta/Step Function}}\
\dd x_{1}\ldots\dd x_{n}
\\[5mm] = &\
{1 \over \pars{2\pi}^{n/2}}\int_{-\infty}^{\infty}
\exp\pars{-x_{1}^{2}/2}\cdots
\int_{-\infty}^{\infty}
\exp\pars{-x_{n}^{2}/2}\ \times
\\[2mm] &\
\underbrace{\bracks{%
\int_{-\infty}^{\infty}{%
\expo{\ic k\pars{nt - \verts{x_{1}} - \cdots - \verts{x_{n}}}} \over k - \ic 0^{+}}\,{\dd k \over 2\pi\ic}}}
_{\substack{\mbox{Heaviside Theta/Step Function}
\\ \mbox{Integral Representation}}}
\dd x_{1}\ldots\dd x_{n}
\\[5mm] = &\
{1 \over \pars{2\pi}^{n/2}}
\int_{-\infty}^{\infty}{\expo{\ic k n t} \over k - \ic 0^{+}}\ \times
\\[2mm] &\
\pars{\int_{-\infty}^{\infty}\exp\pars{-x^{2}/2}
\expo{-\ic k\verts{x}}\dd x}^{n}{\dd k \over 2\pi\ic}
\\[5mm] = &\
\int_{-\infty}^{\infty}{\expo{\ic k n t} \over k - \ic 0^{+}}\ \times
\\[2mm] &\
\braces{\expo{-k^{2}/2}\bracks{1 - \ic\on{erfi}\pars{k \over \root{2}}}}^{n}{\dd k \over 2\pi\ic}
\\[5mm] = &\
\mrm{P.V.}\int_{-\infty}^{\infty}{\expo{\ic k n t} \over k}\,\expo{-nk^{2}/2}\ \times
\\[2mm] &\
\bracks{1 - \ic\on{erfi}\pars{k \over \root{2}}}^{n}{\dd k \over 2\pi\ic} + {1 \over 2}
\\[1cm] = &\
{1 \over 2} +
{1 \over \pi}\int_{0}^{\infty}
\Im\left\{\expo{-nk^{2}\,/\,2\ +\ \ic k n t}
\right.
\\[2mm] &\ \phantom{{1 \over 2} +
{1 \over \pi}}
\left.\bracks{1 - \ic\on{erfi}\pars{k \over \root{2}}}^{n}\right\}{\dd k \over k}
\end{align}

$\qquad\qquad\qquad\qquad\qquad t$
