\documentclass[noamsfonts]{amsproc}
\usepackage{aspmproc}
%% It semms that ASPM doesn't admit \cal and \mathbb fonts %%
\def\cal{}
\def\Cal{}
\def\mathbb{\bf}
\newtheorem{prp}{Proposition}
\newtheorem{lem}[prp]{Lemma}
\newtheorem{thm}[prp]{Theorem}
\title[Scaling limit of $w'=-w^2$]{
Scaling limit of successive approximations for $w'=-w^2$
and its consequences on the theories of random sequential bisections
and height of binary search trees
}
%%%%%% sample of multiple authors
\author[T. Hattori and H. Ochiai]{Tetsuya Hattori and Hiroyuki Ochiai
$^{1}$\footnote{$^{1}$
The research of H.~Ochiai is supported in part by a Grant-in-Aid for
Scientific Research (B) 15340005 from the Ministry of Education,
Culture, Sports, Science and Technology.}
}
%%%%%%%%%%%%%
%%%%%% sample of multiple authors
\address{
{\rm Tetsuya Hattori}\\
Mathematical Institute\\
Graduate School of Science\\
Tohoku University\\
Aoba-ku, Sendai 980--8578\\
Japan\\
E-mail: hattori@math.tohoku.ac.jp\\
\\
{\rm Hiroyuki Ochiai}\\
Graduate School of Mathematics\\
Nagoya University\\
Chikusa-ku, Nagoya 464--8602\\
Japan\\
E-mail: ochiai@math.nagoya-u.ac.jp}
%%%%%%%%%%%%%%%%%%%
\rcvdate{June 20, 2005}% to be supplied by the volume editor
\rvsdate{June 24, 2005}% to be supplied by the volume editor
%% \thanks{Partially supported by *****}
%% \dedicatory{Dedicated to Professor ASPM}
\setcounter{firstpage}{1} % to be supplied by the volume editor
\setcounter{lastpage}{8} % to be supplied by the folume editor
\begin{document}
\begin{abstract}
We prove existence of scaling limits
of sequences of functions defined by
the recursion relation $w_{n+1}'(x)=-w_n(x)^2$.
Namely, $w_n$ approach the exact solution as $n\to\infty$
in asymptotically conformal ways,
$\displaystyle w_n(x)\asymp q_n \bar{w}(q_n x)$,
for a sequence of numbers $\{q_n\}$.
We also discuss the implications of the results in terms of
random sequential bisections of a rod and binary search trees.
\end{abstract}
\maketitle
\section{Introduction and main results.}
\label{s:intro}
A solution of a linear differential equation has no singularities
at regular points of the equation.
On the other hand, a solution of a non-linear differential equation
without singularities may have a singularity.
Such a singularity may change its position among solutions
with different initial conditions,
hence is called a \textit{moving singularity}.
Let us consider a simplest example of such differential equations
\begin{equation}
\label{e:e1}
{dw \over dx}(x)=-w(x)^2.
\end{equation}
While the equation (\ref{e:e1}) has no singularities,
its solution
\begin{equation}
\label{e:s1}
w(x)={1 \over x-C}\,,
\end{equation}
where $C$ is an arbitrary constant,
has a pole at $x=C$.
Due to translational invariance of (\ref{e:e1}),
% a change in $C$ is equivalent to replacing $x$ by $x+C$, hence
without loss of generality we may choose $C=0$ and consider
the solution $w(x)=1/x$ in the following.
Equivalently,
we may choose the boundary condition at infinity as
\begin{equation}
\label{e:e2}
w(x)=x^{-1}+o(x^{-2}),
\ x\to\infty.
\end{equation}
Among possible ways of constructing solutions, let us consider
the method of successive approximation (iteration by integration).
We obtain a sequence $w_n$, $n=0,1,2,\cdots$, of functions defined
recursively, by
\begin{equation}
\label{e:e25}
{dw_{n+1} \over dx}(x)=-w_n(x)^2,\ x\ge 0,
\ \ n=0,1,2,\cdots,
\end{equation}
or, equivalently,
\begin{equation}
\label{e:e3}
w_{n+1}(x)=\int_x^{\infty} w_n(y)^2\,dy,\ x\ge 0,
\ n=0,1,2,\cdots,
\end{equation}
with an initial approximation
\begin{equation}
\label{e:initcond}
w_0(x)=x^{-1}+o(x^{-2}),\ x\to\infty.
\end{equation}
Successive approximation (\ref{e:e3}) gives a sequence of functions
converging to an exact solution $1/x$ of the differential equation
(\ref{e:e1}).
For a solution without singularities, or in a domain where
a solution is regular, the successive approximation converges
uniformly to the exact solution on compact sets.
In a neighborhood of a singularity of the exact solution
`uniform convergence' is obviously impossible,
and we need a framework for discussing the speed of convergence there.
Here we adopt renormalization group picture,
and formulate our results in terms of scaling limits.
To be specific,
we define the
scaling limit of the sequence of functions $w_n$, $n=0,1,2,\cdots$,
as a bounded function defined by
\begin{equation}
\label{e:scalinglimitdef}
\bar{w}(x)=\lim_{n\to\infty} q_n^{-1} w_n(q_n^{-1} x),
\end{equation}
for some sequence of positive numbers
$q_n$, $n=0,1,2,\cdots$, which diverges to $\infty$ as $n\to\infty$.
Note that the scaling factor for $x$ and the scaling factor for $w_n$
should be equal for the present problem,
because $w_n(x)\approx x^{-1}$ for very large $n$.
Also, to have a bounded limit $\bar{w}$, $q_n$ should diverge like $w_n(0)$,
hence we shall, for simplicity, put $q_n=w_n(0)$ in the following.
Let ${\cal W}$ be a set of continuous
functions $\bar{w}:\ [0,\infty)\to{\mathbb R}$, satisfying $\bar{w}(0)=1$ and
asymptotic behavior as in (\ref{e:initcond}),
and define $R:\ {\cal W}\to {\cal W}$ by
\begin{equation}
\label{e:RGrealspace}
R(\bar{w})(x)={1\over r} \int_{x/r}^{\infty} \bar{w}(y)^2\,dy,
\ \ \mbox{ where }
\ \ r=\int_0^{\infty} \bar{w}(y)^2\,dy.
\end{equation}
Note that the definition of ${\cal W}$ implies that
$r$ in (\ref{e:RGrealspace}) is finite, hence
$\bar{w}\in {\cal W}$ implies $R(\bar{w})\in {\cal W}$.
For $\bar{w}_0\in {\cal W}$,
define a sequence of functions $\bar{w}_n\in {\cal W}$, $n=1,2,3,\cdots$,
by
\begin{equation}
\label{e:normalizedsequence}
\bar{w}_{n+1}=R(\bar{w}_n), \ n=0,1,2,\cdots.
\end{equation}
Comparing (\ref{e:e3}) and (\ref{e:RGrealspace}) we see that if we put
\begin{equation}
\label{e:normalizedinitial}
\bar{w}_0(x)=q_0^{-1}w_0(q_0^{-1}x),\ x\ge 0,\ \ \mbox{ with }
\ \ q_0=w_0(0),
\end{equation}
then for $n=1,2,\cdots$,
\begin{equation}
\label{e:phiscd}
\bar{w}_n(x)=q_n^{-1}w_n(q_n^{-1} x),\ \ \mbox{ with }
\ \ q_n=w_n(0),
\end{equation}
and
\begin{equation}
\label{e:ratio}
r_n = \int_0^{\infty} \bar{w}_n(y)^2\,dy
\end{equation}
satisfying
\begin{equation}
\label{e:ratioq}
r_n={q_{n+1} \over q_n}\,.
\end{equation}
Therefore the existence of scaling limit for $w_n$ is equivalent to
the existence of $\lim_{n\to\infty} \bar{w}_n$.
The sequence $\{\bar{w}_n\}$ is uniformly bounded
(in fact, $|\bar{w}_n(x)|\le \bar{w}_n(0)=1$ for $n\ge1$),
and (\ref{e:normalizedsequence}) implies
$\displaystyle \left|{d\bar{w}_{n+1} \over dx}(x)\right|\le
{1 \over r_{n}^2} \bar{w}_{n}^2({x \over r_{n}})\le {1 \over r_{n}^2}$
for $n\ge1$,
hence the Ascoli--Arzel\`{a} Theorem implies that
if the sequence $\{r_{n}^{-2}\}$ is bounded, then
$\{\bar{w}_n\}$ is relatively compact in the topology of uniform convergence
on $[0,\infty)$.
To go further, we will below work in a complex analytic class of functions,
to ensure that the scaling limit actually exists.
To our knowledge,
the problem of existence and properties of scaling limits for successive
approximations to differential equations with moving singularities
has not been studied or even noticed,
though the recursion (\ref{e:e25}) has
attracted attention \cite{unsolved}.
A motivation of the present study is to shed first light on this
potentially interesting, but somehow so far overlooked, problem.
The main results and the organization of the present paper are as follows.
Denote by ${\cal C}$ a set of entire functions
$\bar{w}:\ {\mathbb C}\to{\mathbb C}$, with $\bar{w}(0)=1$,
whose coefficients in the Maclaurin series have alternating signs;
\[ \bar{w}(z)=\sum_{k=0}^{\infty} (-1)^k a_k z^k,\ a_k\ge0,
\ k=0,1,2,\cdots,\ \ \mbox{ (with $a_0=1$),} \]
positive on positive real axis,
and asymptotic behavior in the positive real direction as in
(\ref{e:initcond}).
In Section~\ref{s:main} we prove the following.
\begin{thm}
\label{t:main}
Let $\bar{w}_0\in {\cal C}$
and $\bar{w}_n$, $n=0,1,2,\cdots$, be
a sequence defined recursively by (\ref{e:normalizedsequence}).
Then for each $n$,
$\bar{w}_n$ are analytically continued to ${\mathbb C}$
and $\bar{w}_n\in{\cal C}$ holds.
Furthermore, if the sequence (\ref{e:ratio})
converges to a number greater than $1$:
\begin{equation}
\label{e:rhor}
r =\lim_{n\to\infty} r_n >1,
\end{equation}
then $\bar{w}_n$
converges uniformly on any compact sets in ${\mathbb C}$
to an entire function
\begin{equation}
\label{e:scalinglimitexpansion}
\bar{w}(z)=\sum_{k=0}^{\infty} (-1)^k \alpha_{k} z^k
\end{equation}
defined by
\begin{equation}
\label{e:scalinglimit}
\alpha_0=1,\ \ \alpha_k ={1 \over kr^{k+1}}
\sum_{j=1}^{k} \alpha_{k-j} \alpha_{j-1},\ k=1,2,3,\cdots.
\end{equation}
$\bar{w}$ also satisfies
\begin{equation}
\label{e:scalelimitintegraleq}
\bar{w}(x)={1 \over r}\int_{x/r}^{\infty} \bar{w}(y)^2\,dy,\ \ x\ge 0,
\ \ \ \mbox{and}\ \ \ \int_{0}^{\infty} \bar{w}(y)^2\,dy=r.
\end{equation}
\end{thm}
Theorem~\ref{t:main} gives,
through the correspondence (\ref{e:phiscd}),
a sufficient condition for a sequence of
successive approximations $\{w_n\}$ to have a scaling limit
and its explicit form
in terms of the Taylor coefficients $\alpha_k$\,.
Theorem~\ref{t:main} says that
we have a family of possible scaling limit functions parametrized by
`the scaling factor' $r$ of (\ref{e:rhor}).
Then it is of interest to know whether,
given $r$,
there exists an initial approximation
$w_0$ satisfying (\ref{e:initcond}),
such that the sequence of successive approximations has a scaling limit
with the scaling factor $r$.
The following examples give affirmative answers.
For $b>2$, consider
\begin{equation}
\label{e:rexample}
w_0(x)={1 \over x}\,(1-e^{-x})-{1 \over x^b}\,\gamma(b,x),\ \ x\ge0,
\end{equation}
where $\displaystyle\gamma(b,x)=\int_0^x y^{b-1} e^{-y}dy$
is the incomplete gamma
function of first kind.
Note that
\begin{equation}\label{e:rexampledecay}
w_0(x)=x^{-1} + O(x^{-b}),\ x\to\infty.
\end{equation}
Let $\rho$ be the unique positive solution to a transcendental equation
\begin{equation}
\label{e:rhomax}
2e \log\rho =\rho1
\end{equation}
given by $r=r(b)$,
where
\begin{equation}
\label{e:rb}
r(b) =\left({b \over 2}\right)^{1/(b-1)}.
\end{equation}
\end{thm}
Note that
$\rho$ is the supremum of the function $r(b)$, and that
for $\displaystyle 2\le b\le {1 \over \log\rho}$,
$r(b)$ is increasing in $b$, with $r(2)=1$ and
$\displaystyle r({1 \over \log\rho})=\rho$.
Theorem~\ref{t:continuousspectrum} proves that
for any $r$ satisfying $10\,.
\end{equation}
Obviously, $R_{1}(f)\in \Omega$.
\begin{thm}
\label{t:scalinglimitexamples}
Let $b>2$ and $r=r(b)$ be as in (\ref{e:rb}).
Define a sequence of functions $f_n$, $n=0,1,2,\cdots$,
recursively by $f_0=f_{b,-}\in\Omega$, where
\begin{equation}
\label{e:sample2}
f_{b,-}(t)=\max\{1-t^{b-1},\ 0\},\ \ t\ge 0,
\end{equation}
and $f_{n+1}=R_1(f_n)$, $n=0,1,2,\cdots$.
Then the following hold.
\begin{enumerate}
\item
For each $t\ge 0$,
$f_n(r^n t)$, $n=0,1,2,\cdots$, is non-decreasing,
hence there exists a function $\tilde{f}:\ [0,\infty)\to [0,1]$
such that
\begin{equation}
\label{e:tildef}
\lim_{n\to\infty} f_n(r^nt)=\tilde{f}(t),\ \ t\ge 0,
\end{equation}
for which the following dichotomy, depending on $b$, holds: Either
\begin{enumerate}
\item
$\tilde{f}(t)=1$, $t\ge 0$, or,
\item
$\tilde{f}(t)$ is integrable:
\begin{equation}
\label{e:tildeintegrability}
Q:= \int_0^{\infty} \tilde{f}(t)\,dt <\infty.
\end{equation}
\end{enumerate}
\item
If in addition $\displaystyle b<{1 \over \log\rho}$\,,
then $\tilde{f}(t)<1$, $t>0$,
namely, the latter in the above dichotomy holds.
\end{enumerate}
\end{thm}
Theorem~\ref{t:scalinglimitexamples}
essentially says that $\{r(b)^n\}$ is the correct scaling sequence
for $\displaystyle 2**{1 \over \log\rho}$.
The sequence $\{f_n\}$ in Theorem~\ref{t:scalinglimitexamples} is related to
the sequence $\{w_n\}$ defined by (\ref{e:e3}) through Laplace transform.
Note that (\ref{e:rexample}) has an expression
\begin{equation}
\label{e:fbminusvsw}
w_0(x)=\int_0^{\infty} e^{-xt}\, f_{b,-}(t)\, dt,\ \ x\ge 0,
\end{equation}
where $f_{b,-}$ is as in (\ref{e:sample2}).
\begin{lem}
\label{l:g}
Let $f_0\in\Omega$ and
\begin{equation}
\label{e:phi0F}
w_0(x)= \int_0^{\infty} e^{-xt} f_0(t)\,dt,\ x\ge0,
\end{equation}
and let $w_n$, $n=0,1,2,\cdots$, be
a sequence defined recursively by (\ref{e:e3}).
Then each $w_n$ has an expression
\begin{equation}
\label{e:phingen}
w_n(x)=
\int_0^{\infty} e^{-xt} f_n(t)\,dt\,,\ \ x\ge0,
\end{equation}
with $f_n\in\Omega$ satisfying
\begin{equation}
\label{e:recF}
f_{n+1}=R_{1}(f_n),\ n=0,1,2,\cdots.
\end{equation}
\end{lem}
We have no analogous results to Theorem~\ref{t:scalinglimitexamples}(ii)
for $\displaystyle b\ge {1 \over \log\rho}$.
Also, possibility of scaling limits with $r\ge \rho$ are not contained in
Theorem~\ref{t:continuousspectrum}.
Concerning these points,
the following extreme case turns out to be of particular interest.
Put
\begin{equation}
\label{e:y0}
w_0(x)={1 \over x}(1-\exp(-x)),\ \ x\ge 0.
\end{equation}
Note that
$w_0(x)-x^{-1}$ is exponentially small at $x\to\infty$.
Note also that
\begin{equation}
\label{e:rodbisection0}
{1 \over x}(1-e^{-x})=\int_0^{\infty} e^{-xt}(1-F_0(t))\,dt
\end{equation}
with
\begin{equation}
\label{e:Ito0}
F_0(x)
=\left\{\begin{array}{ll} 0,& 0\le x<1,\\ 1,& x\ge 1\,.\end{array}\right.
\end{equation}
\begin{thm}
\label{t:rodbisection}
Let $w_n$, $n=0,1,2,\cdots$, be
a sequence defined recursively by (\ref{e:e3}),
with $w_0$ as in (\ref{e:y0}).
If a limit (\ref{e:rho})
exists with $q_n=w_n(0)$, then the scaling limit (\ref{e:scalinglimitdef})
exists with $r=\rho$, and satisfies
(\ref{e:scalinglimitexpansion}) with (\ref{e:scalinglimit}) and
(\ref{e:scalelimitintegraleq}).
\end{thm}
A proof of Theorem~\ref{t:rodbisection}
uses a completely different approach from
those for Theorem~\ref{t:scalinglimitexamples}, and is
based on a probabilistic argument for random bisection of a rod
and binary search trees \cite{Devroye,Finch,Itoh,Mahmoud}.
Theorem~\ref{t:rodbisection} (or Theorem~\ref{t:main}) reduces
the problem of convergence
of a series of functions to that of a series of numbers,
hence necessary numerical checks are simpler.
Numerical calculations suggest that
with the choice (\ref{e:y0}),
$\displaystyle q_{n+1}/q_n$ in fact decreases in $n$,
hence (\ref{e:rho}) is likely to hold.
Thus we conjecutre that the scaling limit exists for
$\{w_n\}$ defined recursively by (\ref{e:e3})
with $w_0$ as in (\ref{e:y0}).
The numerical results further suggests that
(\ref{e:tildeintegrability}) actually fails for this choice.
We note that a result similar to Theorem~\ref{t:rodbisection} holds also for
(\ref{e:rexample}) with $\displaystyle b\ge {1 \over \log\rho}$\,,
as a corollary to Theorem~\ref{t:rodbisection}
and Theorem~\ref{t:continuousspectrum}.
Thus our results suggest that $r=\rho$ is the upper bound of possible $r$.
\section{Scaling limit.}
\label{s:main}
Here we prove Theorem~\ref{t:main}.
(See the full text in our web page!)
\begin{thebibliography}{9}
\bibitem{Biggins1} J.\ D.\ Biggins,
{\it The first and last-birth problems for a multitype age-dependent
branching process},
Adv.\ Appl.\ Probab.\ {\bf 8} (1976) 446--459.
\bibitem{Biggins2} J.\ D.\ Biggins,
{\it Chernoff's theorem in the branching random walk},
J.\ Appl.\ Probab.\ {\bf 14} (1977) 630--636.
\bibitem{Devroye} L.\ Devroye,
{\it A note on the height of binary search trees},
Journ.\ Assoc.\ Computing Machinery {\bf 33} (1986) 489--498.
\bibitem{Feller} W.\ Feller,
{\it An introduction to probability theory and its applications},
John Wiley and Sons, 1966.
\bibitem{Finch}
S.~R.~Finch,
\textit{Mathematical Constants,}
Cambridge Univ.\ Press, 2003.
\bibitem{unsolved} R.\ K.\ Guy ed.,
{\it Unsoloved problems},
American Mathematical Monthly \textbf{93} (1986) 279--281,
ibid., \textbf{94} (1987) 961--970.
\bibitem{Hammersley} J.\ M.\ Hammersley,
{\it Postulates for subadditive processes},
Ann.\ Probab.\ {\bf 2} (1974) 652--680.
\bibitem{Kingman} J.\ F.\ C.\ Kingman,
{\it The first-birth problem for an age-dependent branching process},
Ann.\ Probab.\ {\bf 3} (1975) 790--801.
\bibitem{KN} S.\ Kotz, S.\ Nadarajah,
{\it Extreme value distributions,}
Imperial college press, 2000.
\bibitem{Mahmoud}
H.~M.~Mahmoud,
\textit{Evolution of random search trees,}
John Wiley \& Sons Inc., 1991.
\bibitem{Itoh} M.\ Sibuya, Y.\ Itoh,
{\it Random sequential bisection and its associated binary tree},
Ann.\ Inst.\ Stat.\ Math.\ {\bf 39A} (1987) 69--84.
\end{thebibliography}
\end{document}
**