\documentclass[12pt]{article}
%%%begin Larry Shepp macros
%\usepackage{latexsym}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsmath}
\usepackage{dsfont}
\usepackage{placeins}
\usepackage{amssymb}
\usepackage{wasysym}
\usepackage{abstract}
\usepackage{hyperref}
\usepackage{parskip}

%\usepackage{pstricks,pst-node,pst-tree}

%\usepackage{algpseudocode}
%\usepackage{amsthm}
%\usepackage{hyperref}
%\usepackage{mathrsfs}
%\usepackage{amsfonts}
%\usepackage{bbding}
%\usepackage{listings}
%\usepackage{appendix}
\usepackage[margin=1in]{geometry}
%\geometry{papersize={8.5in,11in},total={6.5in,9in}}
%\usepackage{cancel}
%\usepackage{algorithmic, algorithm}

\newcounter{probnum}
\setcounter{probnum}{1}

%create definition to allow local margin changes
\def\changemargin#1#2{\list{}{\rightmargin#2\leftmargin#1}\item[]}
\let\endchangemargin=\endlist 

%allow equations to span multiple pages
\allowdisplaybreaks

%define colors and color typesetting conveniences
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{black}{rgb}{0,0,0}
\definecolor{white}{rgb}{1,1,1}
\definecolor{blue}{rgb}{0.5,0.5,1}
\newcommand{\inblue}[1]{\color{blue}#1 \color{black}}
\definecolor{green}{rgb}{0.133,0.545,0.133}
\newcommand{\ingreen}[1]{\color{green}#1 \color{black}}
\definecolor{yellow}{rgb}{1,0.549,0}
\newcommand{\inyellow}[1]{\color{yellow}#1 \color{black}}
\definecolor{red}{rgb}{1,0.133,0.133}
\newcommand{\inred}[1]{\color{red}#1 \color{black}}
\definecolor{purple}{rgb}{0.58,0,0.827}
\newcommand{\inpurple}[1]{\color{purple}#1 \color{black}}
\definecolor{backgcode}{rgb}{0.97,0.97,0.8}
\definecolor{Brown}{cmyk}{0,0.81,1,0.60}
\definecolor{OliveGreen}{cmyk}{0.64,0,0.95,0.40}
\definecolor{CadetBlue}{cmyk}{0.62,0.57,0.23,0}

%define new math operators
\DeclareMathOperator*{\argmax}{arg\,max~}
\DeclareMathOperator*{\argmin}{arg\,min~}
\DeclareMathOperator*{\argsup}{arg\,sup~}
\DeclareMathOperator*{\arginf}{arg\,inf~}
\DeclareMathOperator*{\convolution}{\text{\Huge{$\ast$}}}
\newcommand{\infconv}[2]{\convolution^\infty_{#1 = 1} #2}
%true functions

%%%% GENERAL SHORTCUTS

%shortcuts for pure typesetting conveniences
\newcommand{\bv}[1]{\boldsymbol{#1}}

%shortcuts for compound constants
\newcommand{\BetaDistrConst}{\dfrac{\Gamma(\alpha + \beta)}{\Gamma(\alpha)\Gamma(\beta)}}
\newcommand{\NormDistrConst}{\dfrac{1}{\sqrt{2\pi\sigma^2}}}

%shortcuts for conventional symbols
\newcommand{\tsq}{\tau^2}
\newcommand{\tsqh}{\hat{\tau}^2}
\newcommand{\sigsq}{\sigma^2}
\newcommand{\sigsqsq}{\parens{\sigma^2}^2}
\newcommand{\sigsqovern}{\dfrac{\sigsq}{n}}
\newcommand{\tausq}{\tau^2}
\newcommand{\tausqalpha}{\tau^2_\alpha}
\newcommand{\tausqbeta}{\tau^2_\beta}
\newcommand{\tausqsigma}{\tau^2_\sigma}
\newcommand{\betasq}{\beta^2}
\newcommand{\sigsqvec}{\bv{\sigma}^2}
\newcommand{\sigsqhat}{\hat{\sigma}^2}
\newcommand{\sigsqhatmlebayes}{\sigsqhat_{\text{Bayes, MLE}}}
\newcommand{\sigsqhatmle}[1]{\sigsqhat_{#1, \text{MLE}}}
\newcommand{\bSigma}{\bv{\Sigma}}
\newcommand{\bSigmainv}{\bSigma^{-1}}
\newcommand{\thetavec}{\bv{\theta}}
\newcommand{\thetahat}{\hat{\theta}}
\newcommand{\thetahatmle}{\hat{\theta}_{\mathrm{MLE}}}
\newcommand{\thetavechatmle}{\hat{\thetavec}_{\mathrm{MLE}}}
\newcommand{\muhat}{\hat{\mu}}
\newcommand{\musq}{\mu^2}
\newcommand{\muvec}{\bv{\mu}}
\newcommand{\muhatmle}{\muhat_{\text{MLE}}}
\newcommand{\lambdahat}{\hat{\lambda}}
\newcommand{\lambdahatmle}{\lambdahat_{\text{MLE}}}
\newcommand{\etavec}{\bv{\eta}}
\newcommand{\alphavec}{\bv{\alpha}}
\newcommand{\minimaxdec}{\delta^*_{\mathrm{mm}}}
\newcommand{\ybar}{\bar{y}}
\newcommand{\xbar}{\bar{x}}
\newcommand{\Xbar}{\bar{X}}
\newcommand{\Phat}{\hat{P}}
\newcommand{\iid}{~{\buildrel iid \over \sim}~}
\newcommand{\inddist}{~{\buildrel ind \over \sim}~}
\newcommand{\approxdist}{~{\buildrel approx \over \sim}~}
\newcommand{\equalsindist}{~{\buildrel d \over =}~}
\newcommand{\loglik}[1]{\mathcal{L}\parens{#1}}
\newcommand{\thetahatkminone}{\thetahat^{(k-1)}}
\newcommand{\thetahatkplusone}{\thetahat^{(k+1)}}
\newcommand{\thetahatk}{\thetahat^{(k)}}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\third}{\frac{1}{3}}
\newcommand{\twothirds}{\frac{2}{3}}
\newcommand{\fourth}{\frac{1}{4}}
\newcommand{\fifth}{\frac{1}{5}}
\newcommand{\sixth}{\frac{1}{6}}
\newcommand{\tenth}{\frac{1}{10}}

%shortcuts for vector and matrix notation
\newcommand{\A}{\bv{A}}
\newcommand{\At}{\A^T}
\newcommand{\Ainv}{\inverse{\A}}
\newcommand{\B}{\bv{B}}
\newcommand{\K}{\bv{K}}
\newcommand{\Kt}{\K^T}
\newcommand{\Kinv}{\inverse{K}}
\newcommand{\Kinvt}{(\Kinv)^T}
\newcommand{\M}{\bv{M}}
\newcommand{\Bt}{\B^T}
\newcommand{\Q}{\bv{Q}}
\newcommand{\Qt}{\Q^T}
\newcommand{\R}{\bv{R}}
\newcommand{\Rt}{\R^T}
\newcommand{\Z}{\bv{Z}}
\newcommand{\X}{\bv{X}}
\newcommand{\Xsub}{\X_{\text{(sub)}}}
\newcommand{\Xsubadj}{\X_{\text{(sub,adj)}}}
\newcommand{\I}{\bv{I}}
\newcommand{\Y}{\bv{Y}}
\newcommand{\sigsqI}{\sigsq\I}
\renewcommand{\P}{\bv{P}}
\newcommand{\Psub}{\P_{\text{(sub)}}}
\newcommand{\Pt}{\P^T}
\newcommand{\Pii}{P_{ii}}
\newcommand{\Pij}{P_{ij}}
\newcommand{\IminP}{(\I-\P)}
\newcommand{\Xt}{\bv{X}^T}
\newcommand{\XtX}{\Xt\X}
\newcommand{\XtXinv}{\parens{\Xt\X}^{-1}}
\newcommand{\XtXinvXt}{\XtXinv\Xt}
\newcommand{\XXtXinvXt}{\X\XtXinvXt}
\newcommand{\x}{\bv{x}}
\newcommand{\onevec}{\bv{1}}
\newcommand{\oneton}{1, \ldots, n}
\newcommand{\yoneton}{y_1, \ldots, y_n}
\newcommand{\yonetonorder}{y_{(1)}, \ldots, y_{(n)}}
\newcommand{\Yoneton}{Y_1, \ldots, Y_n}
\newcommand{\iinoneton}{i \in \braces{\oneton}}
\newcommand{\onetom}{1, \ldots, m}
\newcommand{\jinonetom}{j \in \braces{\onetom}}
\newcommand{\xoneton}{x_1, \ldots, x_n}
\newcommand{\Xoneton}{X_1, \ldots, X_n}
\newcommand{\xt}{\x^T}
\newcommand{\y}{\bv{y}}
\newcommand{\yt}{\y^T}
\renewcommand{\c}{\bv{c}}
\newcommand{\ct}{\c^T}
\newcommand{\tstar}{\bv{t}^*}
\renewcommand{\u}{\bv{u}}
\renewcommand{\v}{\bv{v}}
\renewcommand{\a}{\bv{a}}
\newcommand{\s}{\bv{s}}
\newcommand{\yadj}{\y_{\text{(adj)}}}
\newcommand{\xjadj}{\x_{j\text{(adj)}}}
\newcommand{\xjadjM}{\x_{j \perp M}}
\newcommand{\yhat}{\hat{y}}
\newcommand{\yhatsub}{\yhat_{\text{(sub)}}}
\newcommand{\yhatstar}{\yhat^*}
\newcommand{\yhatstarnew}{\yhatstar_{\text{new}}}
\newcommand{\z}{\bv{z}}
\newcommand{\zt}{\z^T}
\newcommand{\bb}{\bv{b}}
\newcommand{\bbt}{\bb^T}
\newcommand{\bbeta}{\bv{\beta}}
\newcommand{\beps}{\bv{\epsilon}}
\newcommand{\bepst}{\beps^T}
\newcommand{\e}{\bv{e}}
\newcommand{\Mofy}{\M(\y)}
\newcommand{\KofAlpha}{K(\alpha)}
\newcommand{\ellset}{\mathcal{L}}
\newcommand{\oneminalph}{1-\alpha}
\newcommand{\SSE}{\text{SSE}}
\newcommand{\SSEsub}{\text{SSE}_{\text{(sub)}}}
\newcommand{\MSE}{\text{MSE}}
\newcommand{\RMSE}{\text{RMSE}}
\newcommand{\SSR}{\text{SSR}}
\newcommand{\SST}{\text{SST}}
\newcommand{\JSest}{\delta_{\text{JS}}(\x)}
\newcommand{\Bayesest}{\delta_{\text{Bayes}}(\x)}
\newcommand{\EmpBayesest}{\delta_{\text{EmpBayes}}(\x)}
\newcommand{\BLUPest}{\delta_{\text{BLUP}}}
\newcommand{\MLEest}[1]{\hat{#1}_{\text{MLE}}}

%shortcuts for Linear Algebra stuff (i.e. vectors and matrices)
\newcommand{\twovec}[2]{\bracks{\begin{array}{c} #1 \\ #2 \end{array}}}
\newcommand{\threevec}[3]{\bracks{\begin{array}{c} #1 \\ #2 \\ #3 \end{array}}}
\newcommand{\fivevec}[5]{\bracks{\begin{array}{c} #1 \\ #2 \\ #3 \\ #4 \\ #5 \end{array}}}
\newcommand{\twobytwomat}[4]{\bracks{\begin{array}{cc} #1 & #2 \\ #3 & #4 \end{array}}}
\newcommand{\threebytwomat}[6]{\bracks{\begin{array}{cc} #1 & #2 \\ #3 & #4 \\ #5 & #6 \end{array}}}

%shortcuts for conventional compound symbols
\newcommand{\thetainthetas}{\theta \in \Theta}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\complexes}{\mathbb{C}}
\newcommand{\rationals}{\mathbb{Q}}
\newcommand{\integers}{\mathbb{Z}}
\newcommand{\naturals}{\mathbb{N}}
\newcommand{\forallninN}{~~\forall n \in \naturals}
\newcommand{\forallxinN}[1]{~~\forall #1 \in \reals}
\newcommand{\matrixdims}[2]{\in \reals^{\,#1 \times #2}}
\newcommand{\inRn}[1]{\in \reals^{\,#1}}
\newcommand{\mathimplies}{\quad\Rightarrow\quad}
\newcommand{\mathlogicequiv}{\quad\Leftrightarrow\quad}
\newcommand{\eqncomment}[1]{\quad \text{(#1)}}
\newcommand{\limitn}{\lim_{n \rightarrow \infty}}
\newcommand{\limitN}{\lim_{N \rightarrow \infty}}
\newcommand{\limitd}{\lim_{d \rightarrow \infty}}
\newcommand{\limitt}{\lim_{t \rightarrow \infty}}
\newcommand{\limitsupn}{\limsup_{n \rightarrow \infty}~}
\newcommand{\limitinfn}{\liminf_{n \rightarrow \infty}~}
\newcommand{\limitk}{\lim_{k \rightarrow \infty}}
\newcommand{\limsupn}{\limsup_{n \rightarrow \infty}}
\newcommand{\limsupk}{\limsup_{k \rightarrow \infty}}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}

%shortcuts for environments
\newcommand{\beqn}{\vspace{-0.25cm}\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
\newcommand{\bneqn}{\vspace{-0.25cm}\begin{eqnarray}}
\newcommand{\eneqn}{\end{eqnarray}}
\newcommand{\benum}{\begin{enumerate}}
\newcommand{\eenum}{\end{enumerate}}

%shortcuts for mini environments
\newcommand{\parens}[1]{\left(#1\right)}
\newcommand{\squared}[1]{\parens{#1}^2}
\newcommand{\angbrace}[1]{\left<#1\right>}
\newcommand{\tothepow}[2]{\parens{#1}^{#2}}
\newcommand{\prob}[1]{\mathbb{P}\parens{#1}}
\newcommand{\littleo}[1]{o\parens{#1}}
\newcommand{\bigo}[1]{O\parens{#1}}
\newcommand{\Lp}[1]{\mathbb{L}^{#1}}
\renewcommand{\arcsin}[1]{\text{arcsin}\parens{#1}}
\newcommand{\prodonen}[2]{\bracks{\prod_{#1=1}^n #2}}
\newcommand{\mysum}[4]{\sum_{#1=#2}^{#3} #4}
\newcommand{\sumonen}[2]{\sum_{#1=1}^n #2}
\newcommand{\infsum}[2]{\sum_{#1=1}^\infty #2}
\newcommand{\infprod}[2]{\prod_{#1=1}^\infty #2}
\newcommand{\infunion}[2]{\bigcup_{#1=1}^\infty #2}
\newcommand{\infinter}[2]{\bigcap_{#1=1}^\infty #2}
\newcommand{\infintegral}[2]{\int^\infty_{-\infty} #2 ~\text{d}#1}
\newcommand{\supthetas}[1]{\sup_{\thetainthetas}\braces{#1}}
\newcommand{\bracks}[1]{\left[#1\right]}
\newcommand{\braces}[1]{\left\{#1\right\}}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\abss}[1]{\left|#1\right|}
\newcommand{\norm}[1]{\left|\left|#1\right|\right|}
\newcommand{\normsq}[1]{\norm{#1}^2}
\newcommand{\inverse}[1]{\parens{#1}^{-1}}
\newcommand{\rowof}[2]{\parens{#1}_{#2\cdot}}

%shortcuts for functionals
\newcommand{\realcomp}[1]{\text{Re}\bracks{#1}}
\newcommand{\imagcomp}[1]{\text{Im}\bracks{#1}}
\newcommand{\range}[1]{\text{range}\bracks{#1}}
\newcommand{\colsp}[1]{\text{colsp}\bracks{#1}}
\newcommand{\rowsp}[1]{\text{rowsp}\bracks{#1}}
\newcommand{\tr}[1]{\text{tr}\bracks{#1}}
\newcommand{\rank}[1]{\text{rank}\bracks{#1}}
\newcommand{\proj}[2]{\text{Proj}_{#1}\bracks{#2}}
\newcommand{\projcolspX}[1]{\text{Proj}_{\colsp{\X}}\bracks{#1}}
\newcommand{\median}[1]{\text{median}\bracks{#1}}
\newcommand{\mean}[1]{\text{mean}\bracks{#1}}
\newcommand{\dime}[1]{\text{dim}\bracks{#1}}
\renewcommand{\det}[1]{\text{det}\bracks{#1}}
\newcommand{\expe}[1]{\mathbb{E}\bracks{#1}}
\newcommand{\expeabs}[1]{\expe{\abss{#1}}}
\newcommand{\expesub}[2]{\mathbb{E}_{\,#1}\bracks{#2}}
\newcommand{\indic}[1]{\mathds{1}_{#1}}
\newcommand{\var}[1]{\mathbb{V}\text{ar}\bracks{#1}}
\newcommand{\sd}[1]{\mathbb{S}\text{D}\bracks{#1}}
\newcommand{\cov}[2]{\mathbb{C}\text{ov}\bracks{#1,\,#2}}
\newcommand{\corr}[2]{\text{Corr}\bracks{#1, #2}}
\newcommand{\se}[1]{\text{SE}\bracks{#1}}
\newcommand{\seest}[1]{\hat{\text{SE}}\bracks{#1}}
\newcommand{\bias}[1]{\text{Bias}\bracks{#1}}
\newcommand{\partialop}[2]{\dfrac{\partial}{\partial #1}\bracks{#2}}
\newcommand{\secpartialop}[2]{\dfrac{\partial^2}{\partial #1^2}\bracks{#2}}
\newcommand{\mixpartialop}[3]{\dfrac{\partial^2}{\partial #1 \partial #2}\bracks{#3}}

%shortcuts for functions
\renewcommand{\exp}[1]{\mathrm{exp}\parens{#1}}
\renewcommand{\cos}[1]{\text{cos}\parens{#1}}
\renewcommand{\sin}[1]{\text{sin}\parens{#1}}
\newcommand{\sign}[1]{\text{sign}\parens{#1}}
\newcommand{\are}[1]{\mathrm{ARE}\parens{#1}}
\newcommand{\natlog}[1]{\ln\parens{#1}}
\newcommand{\oneover}[1]{\frac{1}{#1}}
\newcommand{\overtwo}[1]{\frac{#1}{2}}
\newcommand{\overn}[1]{\frac{#1}{n}}
\newcommand{\oneoversqrt}[1]{\oneover{\sqrt{#1}}}
\newcommand{\sqd}[1]{\parens{#1}^2}
\newcommand{\loss}[1]{\ell\parens{\theta, #1}}
\newcommand{\losstwo}[2]{\ell\parens{#1, #2}}
\newcommand{\cf}{\phi(t)}

%English language specific shortcuts
\newcommand{\ie}{\textit{i.e.} }
\newcommand{\AKA}{\textit{AKA} }
\renewcommand{\iff}{\textit{iff}}
\newcommand{\eg}{\textit{e.g.} }
\newcommand{\st}{\textit{s.t.} }
\newcommand{\wrt}{\textit{w.r.t.} }
\newcommand{\mathst}{~~\text{\st}~~}
\newcommand{\mathand}{~~\text{and}~~}
\newcommand{\ala}{\textit{a la} }
\newcommand{\ppp}{posterior predictive p-value}
\newcommand{\dd}{dataset-to-dataset}

%shortcuts for distribution titles
\newcommand{\logistic}[2]{\mathrm{Logistic}\parens{#1,\,#2}}
\newcommand{\bernoulli}[1]{\mathrm{Bernoulli}\parens{#1}}
\newcommand{\betanot}[2]{\mathrm{Beta}\parens{#1,\,#2}}
\newcommand{\stdbetanot}{\betanot{\alpha}{\beta}}
\newcommand{\multnormnot}[3]{\mathcal{N}_{#1}\parens{#2,\,#3}}
\newcommand{\normnot}[2]{\mathcal{N}\parens{#1,\,#2}}
\newcommand{\classicnormnot}{\normnot{\mu}{\sigsq}}
\newcommand{\stdnormnot}{\normnot{0}{1}}
\newcommand{\uniform}[2]{\mathrm{U}\parens{#1,\,#2}}
\newcommand{\stduniform}{\uniform{0}{1}}
\newcommand{\exponential}[1]{\mathrm{Exp}\parens{#1}}
\newcommand{\gammadist}[2]{\mathrm{Gamma}\parens{#1, #2}}
\newcommand{\poisson}[1]{\mathrm{Poisson}\parens{#1}}
\newcommand{\binomial}[2]{\mathrm{Binomial}\parens{#1,\,#2}}
\newcommand{\rayleigh}[1]{\mathrm{Rayleigh}\parens{#1}}
\newcommand{\multinomial}[2]{\mathrm{Multinomial}\parens{#1,\,#2}}
\newcommand{\gammanot}[2]{\mathrm{Gamma}\parens{#1,\,#2}}
\newcommand{\cauchynot}[2]{\text{Cauchy}\parens{#1,\,#2}}
\newcommand{\invchisqnot}[1]{\text{Inv}\chisq{#1}}
\newcommand{\invscaledchisqnot}[2]{\text{ScaledInv}\ncchisq{#1}{#2}}
\newcommand{\invgammanot}[2]{\text{InvGamma}\parens{#1,\,#2}}
\newcommand{\chisq}[1]{\chi^2_{#1}}
\newcommand{\ncchisq}[2]{\chi^2_{#1}\parens{#2}}
\newcommand{\ncF}[3]{F_{#1,#2}\parens{#3}}

%shortcuts for PDF's of common distributions
\newcommand{\logisticpdf}[3]{\oneover{#3}\dfrac{\exp{-\dfrac{#1 - #2}{#3}}}{\parens{1+\exp{-\dfrac{#1 - #2}{#3}}}^2}}
\newcommand{\betapdf}[3]{\dfrac{\Gamma(#2 + #3)}{\Gamma(#2)\Gamma(#3)}#1^{#2-1} (1-#1)^{#3-1}}
\newcommand{\normpdf}[3]{\frac{1}{\sqrt{2\pi#3}}\exp{-\frac{1}{2#3}(#1 - #2)^2}}
\newcommand{\normpdfvarone}[2]{\dfrac{1}{\sqrt{2\pi}}e^{-\half(#1 - #2)^2}}
\newcommand{\chisqpdf}[2]{\dfrac{1}{2^{#2/2}\Gamma(#2/2)}\; {#1}^{#2/2-1} e^{-#1/2}}
\newcommand{\invchisqpdf}[2]{\dfrac{2^{-\overtwo{#1}}}{\Gamma(#2/2)}\,{#1}^{-\overtwo{#2}-1}  e^{-\oneover{2 #1}}}
\newcommand{\exponentialpdf}[2]{#2\exp{-#2#1}}
\newcommand{\poissonpdf}[2]{\dfrac{e^{-#1} #1^{#2}}{#2!}}
\newcommand{\binomialpdf}[3]{\binom{#2}{#1}#3^{#1}(1-#3)^{#2-#1}}
\newcommand{\rayleighpdf}[2]{\dfrac{#1}{#2^2}\exp{-\dfrac{#1^2}{2 #2^2}}}
\newcommand{\gammapdf}[3]{\dfrac{#3^#2}{\Gamma\parens{#2}}#1^{#2-1}\exp{-#3 #1}}
\newcommand{\cauchypdf}[3]{\oneover{\pi} \dfrac{#3}{\parens{#1-#2}^2 + #3^2}}
\newcommand{\Gammaf}[1]{\Gamma\parens{#1}}

%shortcuts for miscellaneous typesetting conveniences
\newcommand{\notesref}[1]{\marginpar{\color{gray}\tt #1\color{black}}}

%%%% DOMAIN-SPECIFIC SHORTCUTS

%Real analysis related shortcuts
\newcommand{\zeroonecl}{\bracks{0,1}}
\newcommand{\forallepsgrzero}{\forall \epsilon > 0~~}
\newcommand{\lessthaneps}{< \epsilon}
\newcommand{\fraccomp}[1]{\text{frac}\bracks{#1}}

%Bayesian related shortcuts
\newcommand{\yrep}{y^{\text{rep}}}
\newcommand{\yrepisq}{(\yrep_i)^2}
\newcommand{\yrepvec}{\bv{y}^{\text{rep}}}


%Probability shortcuts
\newcommand{\SigField}{\mathcal{F}}
\newcommand{\ProbMap}{\mathcal{P}}
\newcommand{\probtrinity}{\parens{\Omega, \SigField, \ProbMap}}
\newcommand{\convp}{~{\buildrel p \over \rightarrow}~}
\newcommand{\convLp}[1]{~{\buildrel \Lp{#1} \over \rightarrow}~}
\newcommand{\nconvp}{~{\buildrel p \over \nrightarrow}~}
\newcommand{\convae}{~{\buildrel a.e. \over \longrightarrow}~}
\newcommand{\convau}{~{\buildrel a.u. \over \longrightarrow}~}
\newcommand{\nconvau}{~{\buildrel a.u. \over \nrightarrow}~}
\newcommand{\nconvae}{~{\buildrel a.e. \over \nrightarrow}~}
\newcommand{\convd}{~{\buildrel \mathcal{D} \over \rightarrow}~}
\newcommand{\nconvd}{~{\buildrel \mathcal{D} \over \nrightarrow}~}
\newcommand{\withprob}{~~\text{w.p.}~~}
\newcommand{\io}{~~\text{i.o.}}

\newcommand{\Acl}{\bar{A}}
\newcommand{\ENcl}{\bar{E}_N}
\newcommand{\diam}[1]{\text{diam}\parens{#1}}

\newcommand{\taua}{\tau_a}

\newcommand{\myint}[4]{\int_{#2}^{#3} #4 \,\text{d}#1}
\newcommand{\laplacet}[1]{\mathscr{L}\bracks{#1}}
\newcommand{\laplaceinvt}[1]{\mathscr{L}^{-1}\bracks{#1}}
\renewcommand{\min}[1]{\text{min}\braces{#1}}

\newcommand{\Vbar}[1]{\bar{V}\parens{#1}}
\newcommand{\expnegrtau}{\exp{-r\tau}}

%%% problem typesetting
\newcommand{\problem}{\vspace{0.2cm} \noindent {\large{\textsf{Problem \arabic{probnum}~}}} \addtocounter{probnum}{1}}
%\newcommand{\easyproblem}{\ingreen{\noindent \textsf{Problem \arabic{probnum}~}} \addtocounter{probnum}{1}}
%\newcommand{\intermediateproblem}{\noindent \inyellow{\textsf{Problem \arabic{probnum}~}} \addtocounter{probnum}{1}}
%\newcommand{\hardproblem}{\inred{\noindent \textsf{Problem \arabic{probnum}~}} \addtocounter{probnum}{1}}
%\newcommand{\extracreditproblem}{\noindent \inpurple{\textsf{Problem \arabic{probnum}~}} \addtocounter{probnum}{1}}

\newcommand{\easysubproblem}{\ingreen{\item}}
\newcommand{\intermediatesubproblem}{\inyellow{\item}}
\newcommand{\hardsubproblem}{\inred{\item}}
\newcommand{\extracreditsubproblem}{\inpurple{\item}}
\renewcommand{\labelenumi}{(\alph{enumi})}

%%%others
\newcommand{\sddist}{\mathbb{S}}
\newcommand{\pval}{p_{\text{val}}}
\newcommand{\fpycs}{f_{\text{PYCS}}}
\newcommand{\fpois}{f_{\text{Pois}}}
\newcommand{\lik}[1]{\text{L}\parens{#1}}

\newcommand{\setequalzero}{\buildrel \text{set} \over = 0}
%%%end Larry Shepp macros

\def\lam{{\lambda}}

\title{Pick up sticks}
\author{{\it Larry} Shepp, {\it Doron} Zeilberger, {\it Cun-Hui} Zhang}
%\date{Thursday, Sept 20, 2012}

\renewcommand{\abstractname}{Instructions}

\begin{document}
\maketitle

\section{Introduction}

Break a ruler of length $n$ inches with indentations at each inchmark into $n$ sticks of length one by repeatedly picking up all the fragments 
which are still of length greater than one and throwing them down all at once until all the sticks are of length one. 
Assume that each stick breaks into exactly two sticks uniformly at the inchmarks. What is the expected number of throws needed to complete the $n-1$ breaks?

We show that the answer to this question is $(4.31107\dots) \cdot \ln n \, \cdot (1+ o(1))$
by, as mathematicians are fond of doing, {\it reducing it to an already solved problem}.
The problem that we reduce it to-or rather show that it is almost trivially equivalent to- is the problem of finding
the asymptotic average height of a {\it binary search tree}.
The latter problem was first solved by  Luc Devroye[D], with a later refinement by Bruce Reed[Re].

We also present a possibly new (and we hope elegant) proof that $(4.31107\dots) \cdot \ln n \, \cdot (1+ o(1))$ is
an {\it upper bound} , first proved in 1979 by Robson[Ro].
Our approach is to first prove
a simple generating function for the number of throws needed to isolate the $j$\underline{th} stick and 
then use Chernoff's inequality.
The constant $\alpha = 4.31107\dots$ is the root of $\alpha \ln(2e/\alpha) = 1$. 

The {\it worst} case, if you are extremely unlucky, requires $n-1$ throws. In this case, first the stick breaks into a one-inch piece
and an $(n-1)$-inch piece, then the next throw breaks the $(n-1)$-inch stick into a one-inch piece and an $(n-2)$-inch piece and so on.

The {\it best} case (if $n=2^k$) is $\log_2 n$. First it breaks into two equal pieces each of length
$n/2$ inches, then into four pieces each of length $n/4$ inches etc., and in $k=\log_2 n$ throws into $n$ one-inch pieces.

But if you do it {\it many} times, and $n$ is large, what is the {\it expected} number of throws?
As we have already stated, the answer is $(4.31107 \dots) \cdot (\ln n) \cdot (1+o(1))$,
so the ratio of the asymptotic average to the best case is only
$(4.31107 \dots) \cdot \ln 2 \cdot (1+o(1))= 2.98821+o(1)$.

Recall that a {\it full binary tree} is a ``family tree'' (but with single-parenthood), with a {\it root}
(Eve), and where every vertex either has two children (called the left-child and the right-child) or
no children at all. Childless vertices are called {\it leaves}. 
The {\it height} of a full binary tree is the length of a maximal path from the root to a leaf.

Each scenario of completely breaking an $n$-inch stick into $n$ one-inch pieces can be naturally associated with a full binary tree
with $n$ leaves. The first drop of the interval $[0,n]$ results either in $[0,1]$ and $[1,n]$, or
$[0,2]$ and $[2,n]$, \dots, or $[0,n-1]$ and $[n-1,n]$. Now each of the two pieces goes its own way,
generating its own full binary subtree. Of course, the ``number of throws needed to completely break the stick''
is the height of the corresponding full binary tree.

To see all the  $14$ breaking scenarios for a five-inch ruler go to: \hfill\break
{\tt http://www.math.rutgers.edu/\~{}zeilberg/shepp/S5.html} \quad .

To see all the  $42$ breaking scenarios for a six-inch ruler go to: \hfill\break
{\tt http://www.math.rutgers.edu/\~{}zeilberg/shepp/S6.html} \quad .


Now to each internal vertex (i.e. a vertex that is {\it not} a leaf) assign the label ``number of leaves in the subtree whose root it is''. It is obvious
that the {\it probability} of the breaking  scenario corresponding to any given full binary tree is the
product of $1/(i-1)$ over all the labels of non-leaves, since a stick of length $i$ may be broken
into two smaller pieces in $i-1$ equally likely ways.

So the {\it expectation} of the random variable ``number of throws needed to completely break an $n$-inch ruler''
is nothing but the {\it expected height} of all full binary trees with $n$ leaves, under the above
probability distribution. Let's call it $a(n)$.

Recall (or go to wikipedia) that any list of $n$ different numbers gives rise to
a {\it binary search tree} of $n$ vertices where the first record, let's call it $i_1$ is put at the root,
and its left (respectively right) subtree consists, recursively of the binary search tree of
the sublist (in the same order) consisting of all entries smaller  (respectively larger) than $i_1$.
If a list is empty, then it corresponds to the empty tree with no vertices.

For example, the binary search tree corresponding to the permutation $[4,3,9,1,5, 6, 2,11, 7,8, 10,12]$ can be seen here:  \hfill\break
{\tt http://www.math.rutgers.edu/\~{}zeilberg/shepp/BS12.html} \quad .

It is obvious that a binary search tree corresponds to a (not-necesssarily full) binary tree,
where every vertex may either have no children, or only a left-child, or only a right-child,
or both left- and right-children with $n$ vertices.

To see all the  $14$ binary search trees for the four records $\{1,2,3,4\}$  go to: \hfill\break
{\tt http://www.math.rutgers.edu/\~{}zeilberg/shepp/BS4.html} \quad .


To see all the  $42$ binary search trees for the five records $\{1,2,3,4, 5\}$  go to: \hfill\break
{\tt http://www.math.rutgers.edu/\~{}zeilberg/shepp/BS5.html} \quad .

If you pick a permutation of $\{1, \dots, n\}$ uniformly at random, it is clear that
the probability of it having a certain binary search tree is simply the 
product of $1/i(v)$, over all vertices $v$ of the tree,
where $i(v)$ is defined to be ``the number of vertices in the subtree rooted at $v$''.
For example, the probability of the tree shown in: \hfill\break
{\tt http://www.math.rutgers.edu/\~{}zeilberg/shepp/BS12.html} \quad .

is
$$
(1/12)(1/3)(1/2)(1/1)(1/8)(1/4)(1/3)(1/2)(1/1)(1/3)(1/1)(1/1) \quad .
$$

This is the probability assigned to a random binary search tree, and the average is defined according to
that probability distribution.

In a famous paper in theoretical computer science, 
Bruce Reed[Re] improved on a seminal paper 
of Luc Devroye[D] (who only had the highest-order asymptotics) by proving that 
if $b(n)$ is the average height of  binary tree with $n$ vertices under the above probability distribution, then
$$
b(n)= \alpha \ln n \, - \, \beta  \ln \ln  n + O(1) \quad,
$$
where $\alpha=4.31107\dots$ is the unique root in $[2, \infty)$ of the equation
$$
\alpha \ln ((2e)/\alpha)=1 \quad ,
$$
and $\beta=1.953 \dots$.

We are almost done! It is trivial to see (e.g. by induction) that a full binary tree with $n$ leaves has
$n-1$ {\it internal vertices} (i.e. non-leaves). There is a well-known, obvious, bijection between
binary trees with $n-1$ vertices to full binary trees with $n$ leaves. If a vertex has both children
leave it alone. If it only has a left-child, create for it a right-child that is a leaf.
If it only has a right-child, create for it a left-child that is a leaf. If it has no children (i.e. is a leaf
in the original tree), create for it both a left- and right-child, both leaves.
To go back is even easier! {\it Remove all the leaves}!

By removing all the leaves, the height gets reduced by one, 
(and all the labels as well, but the probability stays the same, due to the different definitions in both cases)
so we have the following relation between
the stick problem and the well-known average height of a random search tree problem:
$$
a(n)=b(n-1)+1 \quad .
$$
Of course, the asymptotics of $a(n)$ is the same as that of $b(n)$.

\section{ A Quick Proof of the Upper Bound}

We now give a quick argument that reproves the inequality
$a(n) \leq  \alpha \ln n \cdot (1+o(1))$, first proved by Robson[Ro],
thereby proving {\it half} of the Devroye result.

We hope, in the future, to extend our approach to proving the other half, namely $a(n) \geq  \alpha \ln n \cdot (1+o(1))$, 
thereby yielding a hopefully simpler proof, or at least an alternative one, of Devroye's result.

\subsection{The generating function for the time to isolate the $j$\underline{th} stick}

Let $\tau_{j,n}, j=1,\ldots,n$ denote the number of throws needed until the $j$\underline{th} inch stick is isolated and let
$f_{j,n}(\rho)$ denote the generating function of $\tau_{j,n}$,
\beqn
f_{j,n}(\rho) = \expe{\rho^{\tau_{j,n}}}.
\eeqn
It is clear that $f_{1,1}(\rho) = 1$, since $\tau_{1,1} = 0$, and that the recurrence,
\beqn
f_{1,n} = \frac{1}{n-1} \sum_{k=1}^{n-1} \rho f_{1,k}(\rho)
\eeqn
holds for the generating function of the number of throws needed to isolate the {\it first} stick. 
An easy induction shows that
\beqn
f_{1,n}(\rho) = \prod_{l=1}^{n-1} (1+\frac{\rho-1}{l}).
\eeqn
Since the number of throws to isolate the $j$\underline{th} stick is the sum of the number of throws needed until the
first break at $j-1$ {\it plus} the number until the first break at the $j$\underline{th} inchmark, and these numbers
are independent, so we see that $f_{j,n}(\rho) = f_{1,j-1}(\rho) f_{1,n-j}(\rho)$ which gives the general result that
\beqn
f_{j,n}(\rho) = \prod_{l=1}^{j-1}(1+\frac{\rho-1}{l}) \prod_{l^\prime = 1}^{n-j}(1+\frac{\rho-1}{l^\prime}).
\eeqn

\subsection{Expectation}

We now prove that the expected total number of throws needed to completely break the stick 
is no greater than $$\alpha \ln(n+1) - 1.$$ 
Since $\max_{j\le n}\tau_{j,n}$ is the number of throws needed, this assertion is equivalent to 
$$
\sum_{x=1}^{n-1} P\Big\{\max_{j\le n}\tau_{j,n} \ge x \Big\} \le \alpha\ln(n+1) - 1. 
$$

The explicit formula of the generating function allows us to apply the Chernoff bound 
$$
P\big(\tau_{j,n} > x \big) \le \rho^{-x} f_{j,n}(\rho)
$$ 
to each $\tau_{j,n}$. Let $m=(n+1)/2$.  
For $\rho\ge 2$, $(1+(\rho-1)/k)\le (1+1/k)^{\rho-1}$, so that 
$$
f(\rho)\le \left\{\prod_{l=1}^{j-1}\Big(1+\frac{1}{l}\Big) \prod_{l^\prime = 1}^{n-j}\Big(1+\frac{1}{l^\prime}\Big)\right\}^{\rho-1}
= \{j(n-j+1)\}^{\rho-1}\le m^{2\rho-2}. 
$$ 
Let $x > \alpha\ln m$, $y = x/\ln m$ and $\rho = y/2$. Since $\rho > \alpha/2 > 2$, 

\beqn
P\big(\max_{j\le n}\tau_{j,n} \ge x \big) 
&\le&  \sum_{j=1}^n \rho^{-x} f_{j,n}(\rho)
\cr &\le& 2\,\exp{\ln m - y \ln m \ln\rho + (2\rho-2)\ln m} 
\cr &=& 2\,\exp{(-1 + y\ln(2e/y))\ln m}. 
\eeqn
Since $(d/dt)((-1 + t\ln(2e/t)) = \ln(2/t) \le \ln(2/\alpha)$ for $\alpha\le t\le y$, 
$$
(-1 + y\ln(2e/y))\ln m \le (y-\alpha)\ln(2/\alpha) \ln m 
= (x - \alpha\ln m)\ln(2/\alpha). 
$$
It follows that $P\big(\max_{j\le n}\tau_{j,n} \ge x \big) \le 2(2/\alpha)^{x-\alpha\ln m}$. 
Let $u$ be the decimal part of $\alpha\ln m - \ln 2/\ln(2/\alpha)$. We find 
\beqn
\sum_{x=1}^{n-1}P\big(\max_{j\le n}\tau_{j,n} \ge x \big) 
& \le &  \sum_{x=1}^{n-1}\min{1,2(2/\alpha)^{x-\alpha\ln m}}
\cr &\le&  \alpha\ln m - \ln 2/\ln(2/\alpha) - u + \sum_{k=1}^\infty (2/\alpha)^{k-u}. 
\eeqn
Since the function $ - u + \sum_{k=1}^\infty (2/\alpha)^{k-u}$ is convex in $u\in [0,1]$ and takes a greater value at $u=1$ 
than $u=0$, its maximum, $1/(1-2/\alpha)-1=2/(\alpha-2)$, is attained at $u=1$. Consequently, the expectation 
of $\max_{j\le n}\tau_{j,n}$ is no greater than 
$$
\alpha\ln(n+1) - \alpha\ln 2 - \ln 2/\ln(2/\alpha) + 2/(\alpha-2). 
$$
The conclusion follows from $- \alpha\ln 2 - \ln 2/\ln(2/\alpha) + 2/(\alpha-2)< -1$. 

A slightly different simple argument using the Poisson dominance of Bernoulli yields 
an upper bound with the $\ln\ln n$ term: 
$$
E \max_{j\le n}\tau_{j,n} \le \alpha\ln  n - (\beta/3)\ln\ln n + O(1)
$$
with $\beta = (3/2)/\log(\alpha/2) = 1.953026$. However, the coefficient for the second order term,  
$\beta/3$, is not sharp according Reed's refinement of Devroye's result that states that


{\bf Remark}. The individual times, $\tau_j$, are rather smaller than the maximum of the $\tau$'s. Indeed, using the generating function of $\tau_j$
it is not hard to show that as $n \rightarrow \infty$,

\beqn
\tau_j = 2 \log{n} + \sqrt{2 \log{n}} \eta_j + o(\sqrt{log{n}})
\eeqn

where $\eta_j$ is standard normal random variable. Thus, it is only the relative independence of the $\tau$'s that allows the maximum to be as large as in Reed's theorem, $\sim 4.13\ldots \log{n}$.

{\bf Acknowledgement}: The stick problem was inspired by
the interesting paper [IK].


\section{Maple Packages}

This article is accompanied by two Maple packges for experimenting, and simulating, both
binary trees under the uniform distribution (not discussed in this article), and for the
stick problem (alias binary search trees). The most important one is
{\tt BinaryTrees} and the lesser one is {\tt ArbresBinaires}. 
There is yet another Maple package, {\tt EtzBinary}, mainly for plotting, and that's
how we drew the pictures linked to above. All three packages, as well as
some sample input and output files, can be gotten from the ``front'' of this article: \hfill\break

{\tt http://www.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/stick.html} .

\section{ References}

[D] Luc Devroye, {\it A note on the height of a binary search tree}, J. of the ACM {\bf 33}(3) (July 1989), 489-493.


[IK] Yoshiaki Itoh and  P. L. Krapivsky,
{\it Continuum cascade model of directed random graphs: traveling wave analysis}, {\tt http://arxiv.org/abs/1206.3711 } .

[Re] Bruce Reed, {\it The height of a random binary search tree},
Journal of the ACM {\bf 50} (2003), 306-332.

[Ro] J.M. Robson, {\it The height of binary search trees}, Aust. Computing J. {\bf 11} (1979), 151-153.

\bigskip
\hrule
\bigskip
Lawrence Shepp, Wharton School, University of Pennsylvania,  {\tt shepp@wharton.upenn.edu}
\smallskip
Doron Zeilberger, Department of Mathematics, Rutgers University, {\tt zeilberg@math.rutgers.edu}
\smallskip
Cun-Hui Zhang, Department of Statistics, Rutgers University, {\tt czhang@stat.rutgers.edu}
\end{document}








