\documentclass[12pt]{thesis}

\input{preamble}

\begin{document}

\newcommand{\TR}{\textcolor{red}}

%\title[Worst-Case Find:\ Symbol Comparisons]
%{QuickSelect Tree Process Convergence, With an Application to Distributional Convergence for the Number of Symbol Comparisons Used by Worst-case Find} 

%\author{James Allen Fill and Jason Matterer}
%\address{Department of Applied Mathematics and Statistics,
%The Johns Hopkins University,
%34th and %\hfill\break
%Charles Streets,
%Baltimore, MD 21218-2682 USA}
%\email{jimfill@jhu.edu, jtmatterer@gmail.com}
%\thanks{Research for both authors supported by the Acheson~J.~Duncan Fund for the Advancement of Research in Statistics.}

%\date{last revised August~5, 2013}

%\keywords{QuickSelect; Find; worst-case Find; natural coupling; QuickQuant; QuickVal; symbol comparisons; key comparisons; Banach space; process convergence; $L^p$-convergence; probabilistic source; tameness}

%\subjclass[2010]{Primary:\ 60F25; secondary:\ 68W40, 60F15}

%\maketitle
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Title Page
\title{\quickselect\ Process and \quickval\ Residual Convergence}
\author{Jason Matterer}
\dissertation
\doctorphilosophy
\degreeyear{2015}
\degreemonth{December}
\copyrightnotice

\maketitle

%\vspace{1.5in}
%\begin{center}
%REFINED ASYMPTOTICS OF QUICKSELECT AND QUICKVAL UNDER GENERAL COST FUNCTIONS
%
%\vspace{1in}
%
%by\\
%Jason Matterer
%
%\vspace{1.5in}
%
%A dissertation submitted to Johns Hopkins University in conformity with the requirements for the degree of Doctor of Philosophy
%
%\vspace{.5in}
%
%Baltimore, Maryland\\
%May, 2015
%
%\vspace{1.5in}
%\textcopyright~2015 Jason Matterer \\
%All Rights Reserved
%\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\TR{I don't know about the dissertation title, in regard to the first half of your dissertation.  Can QuickSelect tree process convergence and distributional convergence for worst-case {\tt Find} really be classified under "refined asymptotics"?}

\abstract
We define a sequence of tree-indexed processes closely related to the operation of the \quickselect\ search algorithm (also known as {\tt Find}) for all the various values of~$n$ (the number of input keys) and~$m$ (the rank of the desired order statistic among the keys).  As a ``master theorem'' we establish convergence of these processes in a certain Banach space, from which known distributional convergence results as $n \to \infty$ about 
\begin{enumerate}
\item[(1)] the number of key comparisons required 
\end{enumerate}
are easily recovered 
\begin{enumerate}
\item[(a)] when $m / n \to \alpha \in [0, 1]$, and 
\item[(b)] in the worst case over the choice of~$m$.  
\end{enumerate}
From the master theorem it is also easy, for distributional convergence of 
\begin{enumerate}
\item[(2)] the number of symbol comparisons required,
\end{enumerate}
both to recover the known result in the case~(a) of fixed quantile~$\alpha$ and to establish our main new result in the case~(b) of worst-case {\tt Find}.

Our techniques allow us to unify the treatment of cases~(1) and~(2) and indeed to consider many other cost functions as well.  Further, all our results provide a stronger mode of convergence (namely, convergence in $L^p$ or almost surely) than convergence in distribution.  Extensions to 
{\tt MultipleQuickSelect} are discussed briefly.

Under mild assumptions on a general class of cost functions, Fill and Nakama \cite{fn2013} proved that the scaled cost of \quickval\ $S_n^{ \left( V \right) }/n$ converges in $L^p$ and almost surely to a limit random variable $S$. For a general cost function, we consider what we term the \quickval\ residual:
\begin{equation*}
  R_n^{\rm (V)}:=\frac{\SV}{n} - S.
\end{equation*}
The residual is of natural interest (especially in light of the previous analogous work on 
{\tt QuickSort} \cite{n2013,f2015,gk2014,s2015}).
In the case of {\tt QuickMin} with key-comparisons cost, we are able to calculate---\`{a} la Bindjeme and Fill for {\tt QuickSort} \cite{bf2012}---the exact (and asymptotic) $L^2$-norm of the residual.  
We take the result as motivation for the scaling factor $\sqrt{n}$ for the {\tt QuickVal} residual for \emph{general} population quantiles and for \emph{general} cost.  We then show \emph{in general} that $\sqrt{n}\,R_n^{\rm (V)}$ converges in law to a scale-mixture of centered Gaussians.  In the motivating case of {\tt QuickMin} with key-comparisons cost, we also prove convergence of moments.  
Following Fuchs for {\tt QuickSort} \cite{f2015}, this was part of our original attempt at proving convergence in distribution for $\sqrt{n}\,R_n^{\rm (V)}$:\ using the method of moments.  
However, this approach encountered two roadblocks:\ first, because the approach is inherently recursive, we don't know how to extend beyond the motivating case; second, in the case of \quickmin\ with key-comparisons cost, we can show via Krein's condition \cite{a1965} that the moments of the limiting distribution do \emph{not} uniquely define a distribution . In the case of \quickval\ with general cost functions, it is still an open question whether the limiting residual distribution is uniquely defined by its moments for any value of $\alpha$. 

%Under minor conditions on the source, we show that $\sqrt{n}R_n^{\rm (V)}$ converges in law to a scale-mixture of centered Gaussians. Using key-comparisons cost ($\beta\equiv 1$), we calculate the $L^2$ norm of the \quickmin\ residual \emph{exactly} and asymptotically, motivating the scaling factor of $\sqrt{n}$. Additionally
%%, under the assumption of key-comparison costs, 
%for key-comparisons cost,
%we prove that the moments of the normalized \quickmin\ residual converge to the corresponding moments of a scale-mixture of centered Gaussians. 
%By an elementary result in probability (e.g.,\ \cite[Theorem~4.5.2]{c2001}), these moments agree with those of the limit law. 
%However, it can be shown using Krein's condition \cite{a1965} that these moments do not uniquely define the distribution. 
%whether it agrees with the limit law result in \refCh{c:quickval_residual}.
%\TR{even whether these moments are the moments of the limit law.}
\endabstract
\bigskip

\noindent
%\TR{
%Because of the forced line-breaks you used for the titles of Sections 7.1 and 7.3, the corresponding entries in the table of contents look bad.  Is there any way to fix that?} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\acknowledgment
Writing a dissertation is a long process full of ups and downs. What I have accomplished would not have been possible if it were not for the constant support of everyone around me. 
I could not have asked for a better advisor in Professor Jim Fill, whose insight and patience proved invaluable throughout the research process.
If I were to try to list what I have learned from Professor Fill over the years from mathematical 
results down to typographical practices that would entail a dissertation of its own.

I owe a debt of gratitude to Emily Cahill, my girlfriend, for always being there to listen to my endless rambling about the work that makes up this dissertation.
Without the nourishing support from my parents, I would never have developed my love of mathematics which makes all this possible.
%

\endacknowledgment
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\tableofcontents


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Introduction}\label{S:intro}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\input{introduction}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Set-up and Preliminaries}\label{S:set-up}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\input{set-up.and.prelim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Process convergence}\label{S:proc_conv}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\input{quickselect.process.convergence}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Exact $L^2$ Asymptotics for \quickmin\ Residual}\label{c:exact_L2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\input{exact.L2.residual.quickmin}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Convergence of \quickval\ Residual}\label{c:quickval_residual}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\input{quickval.residual.clt}
%\input{quickquant.residual.clt}
\input{residual.quickval.moments}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Moments of \quickmin\ Residual}\label{c:quickmin_moments}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\input{residual.quickmin.moments}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{plain}
\bibliography{references}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter*{Curriculum Vitae}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\input{matterer.cv}

\end{document}

