\documentclass[12pt]{article}
\usepackage{amsmath,amssymb}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{epsfig}

%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Created=Tue Mar 02 23:03:32 2004}
%TCIDATA{LastRevised=Mon Jul 26 14:51:04 2004}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="Journal Articles\Standard LaTeX Article">}
%TCIDATA{CSTFile=LaTeX article (bright).cst}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{assumption}[theorem]{Assumption}
%\newtheorem{remark}[theorem]{Remark}
\newtheorem{rema}{Remark}
\newenvironment{remark}{\begin{rema} \rm}{\end{rema}}
%\newtheorem{example}[theorem]{Example}
\newtheorem{exam}{Example}
\newenvironment{example}{\begin{exam} \rm}{\end{exam}}

\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\def\R{\mathbb{R}}
\def\Rd{\R^d}
\def\E{\mathbb E}
\def\EXP{{\E}}
\def\expec{{\EXP}}
\def\PROB{{\mathbb P}}
\def\var{{\rm Var}}
\def\shat{{\mathbb S}}
\def\IND#1{{\mathbb I}_{{\left[ #1 \right]}}}
%\def\IND#1{{\mathbb I}_{{ #1 }}}
\def\I{{\mathbb I}}
\def\pr{\PROB}
\def\prob{\PROB}
\def\wh{\widehat}
\def\ol{\overline}
\newcommand{\deq}{\stackrel{\scriptscriptstyle\triangle}{=}}
\newcommand{\defeq}{\stackrel{\rm def}{=}}
\def\isdef{\defeq}
\newcommand{\xp}{\mbox{$\{X_i\}$}}
\def\diam{\mathop{\rm diam}}
\def\argmax{\mathop{\rm arg\, max}}
\def\argmin{\mathop{\rm arg\, min}}
\def\essinf{\mathop{\rm ess\, inf}}
\def\esssup{\mathop{\rm ess\, sup}}
\def\supp{\mathop{\rm supp}}
\def\cent{\mathop{\rm cent}}
\def\dim{\mathop{\rm dim}}
\def\sgn{\mathop{\rm sgn}}
\def\logit{\mathop{\rm logit}}
\def\proof{\medskip \par \noindent{\sc proof.}\ }
\def\proofsketch{\medskip \par \noindent{\sc Sketch of proof.}\ }
%% Not in latex2e:
%  \def\qed{\hfill $\Box$ \medskip}
%  \def\qed{$\Box$}
\def\blackslug{\hbox{\hskip 1pt \vrule width 4pt height 8pt depth 1.5pt
\hskip 1pt}}
\def\qed{\quad\blackslug\lower 8.5pt\null\par}
\newcommand{\F}{{\cal F}}
\newcommand{\G}{{\cal G}}
\newcommand{\X}{{\cal X}}
\newcommand{\D}{{\cal D}}
\newcommand{\cR}{{\cal R}}
\newcommand{\COND}{\bigg\vert} % for conditional expectations
%
\def\C{{\cal C}}
\def\B{{\cal B}}
\def\A{{\cal A}}
\def\N{{\cal N}}
\def\F{{\cal F}}
\def\L{{\cal L}}
\def\eps{{\varepsilon}}
\def\Var{{\rm Var}}
%\newcommand{\IND}{\mbox{\bf 1}_}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\EE}{\mathbb{E}}
\newcommand{\Prob}[1]{\mathbb{P}\left\{ #1 \right\} }

\allowdisplaybreaks

\title{How to bootstrap basic statistics?}
\author{St\'ephan Cl\'emen\c con}

\begin{document}

\maketitle

As a first go, we present two ways of bootstrapping statistics. Here is the framework. Our population of interest is described by a probability distribution $F(dx)$ on $\mathbb{R}^d$ and we are interested in estimating a particular feature $\theta=\theta(F)\in \mathbb{R}$ of the latter (ex: mean, median, variance, \textit{etc}.) based on a sample $\mathcal{D}$ of independent observations $X_1,\ldots, X_n$ drawn from $F$. The input matrix is of dimensions $n\times d$.
\medskip

\par We may start off by computing a dedicated estimate $\widehat{\theta}$ (ex: the sample mean, median, variance \textit{etc.}) but our goal is rather to determine confidence regions $\mathcal{I}_n(\alpha)$ at prescribed levels $\alpha \in ]0,1[$:
\[
\mathbb{P}\left\{ \theta \in \mathcal{I}_n(\alpha)\right\} \approx 1-\alpha.
\]
Asymptotic theory developed in the field of mathematical statistics tells us that under certain circumstances, it is possible to identify the limiting distribution $G$ of the deviation $(\widehat{\theta}-\theta)/\sigma$, when properly normalized (in the domain of attraction of the gaussian, the norming constant is generally the variance of the estimator). A confidence interval can be then built from quantiles of $G$. Roughly speaking, the variability of the statistic is described by the corresponding theoretical limit theorem and it is rather difficult for a non-mathematician to rely on such an abstract result to think the randomness of its statistic.  The bootstrap permits to avoid this theoretical approach and furnishes a fully data-driven approach which allows for visualizing the variability of the estimation procedure: indeed, it provides a population of (bootstrap) statistics.
\medskip

All bootstrap methods are implemented from bootstrap data samples. A bootstrap sample is a set $\mathcal{D}^*$ of observations $X_1^*,\ldots, X_N^*$ sampled from the original data with replacement. More precisely, we need to generate $B$ bootstrap samples for Monte-Carlo estimation purpose.\\
$\Rightarrow$ we thus need to incorporate a routine for generating bootstrap data samples: {\bf resampling.m}

\begin{remark} ({\sc On the resampling procedure}) In general, we will generate bootstrap samples with the same number of observations as the original data sample: $N=n$. The number $B$ of bootstrap samples will be large, typically $B=5000$. In thee case where the data exhibits a particular structure of dependence (ANOVA, random-effect model, \textit{etc.}), it is necessary to take latter into account when implementing the resampling procedure: typically, a certain number of variables will describe the dependence structure and will enter as input in the resampling routine. 
\end{remark}
\bigskip

\noindent {\bf The bootstrap-$t$.}\\
\noindent This method requires to know a way of properly renormalizing $\widehat{\theta}-\theta$. In absence of further indications, we use the standard deviation $\widehat{\sigma}=\widehat{\sigma}(X_1,\ldots, X_n)$, estimating $\sqrt{var(\widehat{\theta})}$, as norming constant. In a few cases only, a precise formula for computing $\widehat{\sigma}^2$ is available. It is the case of the sample mean for instance, which may be studentized using the sample variance. In such an ideal case, the algorithm is as follows


\fbox{
\begin{minipage}[t]{12.5cm}
\small{
\begin{center}
\medskip

{\sc Bootstrap-t}
\end{center}


\begin{enumerate}
\item Draw $B$ bootstrap samples of length $n=size(\mathcal{D}, 1)$: $$\mathcal{D}^{*(b)}=\{ X_1^{*(b)},\ldots, X_n^{*(b)}\}, \;\;b=1,\ldots, B.$$

\item For each bootstrap data sample $\mathcal{D}^{*(b)}$, compute bootstrap versions of the statistic and its renormalization: $\widehat{\theta}^{*(b)}$ and $\widehat{\sigma}_n^{*(b)}$. Then, compute: $\forall b \in \{1,\ldots, B\}$,
$$
T_n^{*(b)}=\frac{\widehat{\theta}^{*(b)}-\widehat{\theta}}{\widehat{\sigma}^{*(b)}}.
$$

\item Compute the sampling  cumulative distribution function of the $T^{*(b)}$'s:
$$
G_{boot}(x)=\frac{1}{B}\sum_{b=1}^B\mathbb{I}\{T^{*(b)}\leq x\},\; x\in \mathbb{R}.
$$

\item In order to produce a confidence interval of level $1-\alpha$, determine:
\begin{eqnarray*}
q_{\alpha/2}&=&G_{boot}^{-1}(\alpha/2)=\inf \{b\in \{1,\ldots, B\}:\; G_{boot}(b)\geq \alpha/2\},\\
q_{1-\alpha/2}&=&\inf \{b\in \{1,\ldots, B\}:\; G_{boot}(b)\geq 1-\alpha/2\}.\\
\end{eqnarray*}
Then, ouput
$$
\mathcal{I}_{boot}(\alpha)=\left[ \widehat{\theta}- \widehat{\sigma}\cdot q_{1-\alpha/2} ;\; \widehat{\theta}+\widehat{\sigma}\cdot q_{\alpha/2} \right].
$$
\end{enumerate}
}
\end{minipage}
}

\newpage


However, in general, we will use a \textit{nested bootstrap}. Precisely, for each bootstrap sample $\mathcal{D}^{*(b)}$, $b\in \{1,\;\ldots,B\}$, we will generate independently $B'$ independent bootstrap samples by drawing with replacement in $\mathcal{D}^{*(b)}$: $\mathcal{D}'_1{}^{*(b)},\ldots,\; \mathcal{D}'_{B'}{}^{*(b)}$.  The norming constant of $\widehat{\theta}^{*(b)}$ is then estimated by bootstrap. 
\bigskip

\fbox{
\begin{minipage}[t]{12.5cm}
\small{
\begin{center}
\medskip

{\sc Nested bootstrap-t}
\end{center}


\begin{enumerate}
\item Draw $B$ bootstrap samples of length $n=size(\mathcal{D}, 1)$: $$\mathcal{D}^{*(b)}=\{ X_1^{*(b)},\ldots, X_n^{*(b)}\}, \;\;b=1,\ldots, B.$$

\item For each bootstrap data sample $\mathcal{D}^{*(b)}$, 
\begin{enumerate}
\item compute a bootstrap version of the statistic of interest $\widehat{\theta}^{*(b)}$
\item generate $B'$ bootstrap replicates of $\mathcal{D}^{*(b)}$, as well as bootstrap versions of $\widehat{\theta}^{*(b)}$:
$$
\widehat{\theta}_1^{*(b)},\ldots,\; \widehat{\theta}_{B'}^{*(b)}
$$
\item estimate the variance of $\widehat{\theta}^{*(b)}$:
$$v^{*(b)}{}^2_{boot}=\frac{1}{B'-1} \sum_{b'=1}^{B'}\left(\widehat{\theta}^{*(b)}_{b'} -\widehat{\theta}^{*(b)}\right)^2  $$

\end{enumerate}

\item Apply steps 2-4 with $v^{*(b)}{}^2_{boot}$ replacing $\widehat{\sigma}^{*(b)}{}^2_{boot}$.
\end{enumerate}
\medskip

}
\end{minipage}
}
\newpage

\noindent {\bf The bootstrap percentile.}\\
\noindent A much more easy to implement bootstrap method consists of simply identifying the quantiles of the bootstrap statistic. The algorithm is as follows. 


\fbox{
\begin{minipage}[t]{12.5cm}
\small{
\begin{center}
\medskip

{\sc Bootstrap percentile}
\end{center}


\begin{enumerate}
\item Draw $B$ bootstrap samples of length $n=size(\mathcal{D}, 1)$: $$\mathcal{D}^{*(b)}=\{ X_1^{*(b)},\ldots, X_n^{*(b)}\}, \;\;b=1,\ldots, B.$$

\item For each bootstrap data sample $\mathcal{D}^{*(b)}$, compute bootstrap versions of the statistic: $\widehat{\theta}^{*(b)}$. 
\item Compute the sampling  cumulative distribution function of the $\widehat{\theta}^{*(b)}$'s:
$$
H_{boot}(x)=\frac{1}{B}\sum_{b=1}^B\mathbb{I}\{\widehat{\theta}^{*(b)}\leq x\},\; x\in \mathbb{R}.
$$

\item In order to produce a confidence interval of level $1-\alpha$, determine:
\begin{eqnarray*}
Q_{\alpha/2}&=&H_{boot}^{-1}(\alpha/2)=\inf \{b\in \{1,\ldots, B\}:\; H_{boot}(b)\geq \alpha/2\},\\
Q_{1-\alpha/2}&=&\inf \{b\in \{1,\ldots, B\}:\; H_{boot}(b)\geq 1-\alpha/2\}.\\
\end{eqnarray*}
Then, ouput
$$
\mathcal{I}_{boot}(\alpha)=\left[ Q_{\alpha/2},\;  Q_{1-\alpha/2} \right].
$$
\end{enumerate}
}
\end{minipage}
}

\bigskip

There exist refinements of the methods presented above, which will be developed later. 



\end{document}
