text:
Advocates for Children in Therapy
Opposing Abusive and Unvalidated Psychotherapy
Attachment Therapy
AT Parenting
RAD vs. AD
Critics of AT Methods
Major Critics
AT Proponents
Evidence-Based Therapy
Major Critics of Attachment Therapy
While Attachment Therapy/Parenting (AT/P) has been around, by one name or another, since the late 1960s and early 1970s, it hasn't been subject to much public or academic scrutiny until the death of Candace Newmaker at the hands of Attachment Therapists in Evergreen, Colorado, in 2000.
Before that time, criticism of AT/P was an ad hoc affair. Prosecutors would sporatically go after parents when their AT/P abuse came to notice. From time to time, family courts would have a case where the outcome would be influenced negatively by the existence of AT/P in a family's affairs. Otherwise, very little was said — and even less was done — about the growing practice of AT/P. For whatever reasons, very few critics had come forward to point out systematically the theoretical, practical, legal, and ethical problems with AT/P.
AT/P's profile has been raised of late, and the nature and magnitude of the problem has prompted many more professionals than before to voice criticism. While many are clinicians in private practice, others are academicians and leaders who have access to professional forums. (See the bibliography below for details.)
Earliest Critics
As late as the 1990s, only two people are known to have addressed the abuses of AT/P in the professional literature: Beverly James, who founded the James Institute in Hawaii, and Samantha Wilson of Truman State University in Missouri.
In 1994, Beverly James published her Handbook for Treatment of Attachment-Trauma Problems in Children. At that time she attacked coercive therapy, as "terroristic and abusive as well as dangerous." She singled out the bogus claim made by AT/P practitioners that they "contract" with their patients or otherwise making a "therapeutic alliance" with their child victims. She approvingly quoted a terrorism expert from the 1970s: "Coercion, having obscured its brutal origins, is then at its most triumphant when the victims are compelled to experience submission as a voluntary decision. This is rape of the mind."
Ms James's critique was the only widely published criticism for a significant period of time and has published no other commentary since, though in 1998, she gave CBS News' 48 Hours program an interview about the problems. Unfortunately, by 2000 she was endorsing the practices of one Attachment Therapist, who obscures the brutal nature of his own techniques.
In 1999, Samantha Wilson's review of attachment disorders (not published until 2001), pointed out how the evidence "provides little validation for the use of such a controversial intervention." She also made the important point that claims to reduce aggressive or delinquent behaviors (even if the evidence supported them) did little or nothing to answer the question, "Are children who receive this intervention able to form more stable attachments during adolescence or adulthood?"
Dr Wilson's ultimate pronouncement on AT/P, while gently stated, was right on target, scientifically and ethically: "Until such time as holding techniques can be empirically validated to improve the condition of RAD without excessive stress to the child, parents may be well advised to consider other options in the treatment of a child with RAD." This relatively early assessment continues to hold, four years on from when it was written. (There have been a few meta-analyses establishing the effectiveness for children of sundry conventional therapeutic approaches. For one, see Weisz et al.)
Though sharing many fundamental ideas, even Freudian psychoanalysts are appalled by Attachment Therapy. The prominent Swiss psychoanalyst, Alice Miller, taking off from principles elucidated in her books, For Your Own Good: Hidden Cruelty in Child-Rearing and the Roots of Violence and Breaking Down the Walls of Silence, attacked AT in personal correspondence. She told Canadian Jan Hunt, MS, Director of the Natural Child Project, that: "Force, the therapy implies, is used for the child's own good, and the child will be rewarded and loved for his tolerance in letting it happen. He will come to believe that force contributes to his well-being and is ultimately beneficial. A more perfect deception and distortion of someone#&146;s perceptions is barely imaginable."
Ms Hunt published Dr Miller's concerns in an essay of her own in the Project's web-based newsletter in September 2000. She added this assessment of AT/P: "Whether by a parent, therapist or stranger, physically overpowering a helpless child is wrong. Justifying it by calling it 'love' or 'therapy' is a violation of the child's trust and understanding of life as he has come to know it. … How sad that something as lovely as having a child in our arms — when the desire is mutual — has been perverted into such a heartless practice."
Jean Mercer
Leading the renewed discussion against AT/P has been the President of ACT's Professional Board of Advisors, Jean Mercer, PhD. Dr Mercer is professor emerita of psychology at Richard Stockton College in Pomona, New Jersey, where she long taught child development. She also served as President of the New Jersey Infant Mental Health Association. In addition to a book on the Candace Newmaker case, Attachment Therapy on Trial, and an encyclopedia article about AT/P, she has also has had numerous pieces published about AT/P in the professional literature.
Alerting clinicians and others to AT/P's existence and danger, Mercer has shown that AT/P has all the marked characteristics of an unvalidated therapy, including significant questions about safety and effectiveness. The use or recommendation of unvalidated therapies, she points out, should be avoided by ethical professionals, and similarly should be discouraged to patients and families.
Mercer's opinions have been based in part on the realization that AT/P advocates are not frequently not candid about their use of coercive restraint. Their self-descriptions of their practices frequently obscure the inherently violent nature of what they do. Their characterization of "holding" as a a nurturing and safe environment is but one example of how they deliberately blur the lines. Similarly, Prof Mercer has repeatedly shown the utter absence of empirical evidence for the effectiveness and safety of AT/P, yet promoters continually talk to the public and to potential clients as if there was such evidence.
Mercer points out that attachment is a dynamic relationship, and it is that relationship that needs to be addressed in therapy. Thus, there are at least two actors (child and parent) who each have to work on the problems they are having. AT/P, however, assumes that the problem rests entirely with the child and has to be overcome entirely by treating the child. Furthermore, by selecting the child for treatment, AT therapists have focused on the person in the relationship least able to comprehend and deliberately change. As one of the APSAC authors below has pointed out, "Most children and adolescents are overwhelmed and confused by discussions of their early experiences of maltreatment."
Most telling of all, Mercer has repeatedly exposed the contradictions between the approaches and techniques used in AT/P and what has been discovered through valid and lengthy academic work and clinical research about child mental and emotional development, about parent-child attachments, and about how the human mind reacts to trauma. Put simply, if AT/P approaches are valid, then nearly everything and everyone who has published research in the area over the last half-century or so is necessarily wrong.
Mercer has addressed the shortcomings of AT/P's largest organization — Association for Treatment and Training in the Attachment of Children (ATTACh). In addition to promoting AT/P, ATTACh has been trying to establish itself as a legitimate, freestanding professional organization. As Mercer pointed out in an Open Letter to ATTACh's president, the group' efforts are marked by not having done all the things expected of such an organization.)
APSAC
Mercer's concerns about AT/P may have been the first to re-open the debate over its practices, but her concerns received independent confirmation when an influential watchdog group, the American Professional Society on the Abuse of Children (APSAC), also took on the issue of AT/P in 2002. William Friedrich, a psychiatrist at the Mayo Medical School and Clinic, guest edited two issues of the APSAC Advisor which presented separate articles, by professors Matthew Speltz of the University of Washington Medical School, Rochelle Hanson of the Medical University of South Carolina, Alan Sroufe of the University of Minnesota, and Martha Erickson, taking AT/P to task. (Joining them were clinicians Lucy Berliner and Rosie Oreskovitch, both of Washington State, the latter with the Department of Human Services there.) These articles surveyed the range of problems with AT/P, from theory to practice.
Calling it an "uninformed therapy," the APSAC authors start by unequivocally showing that AT/P has no basis in the highly regarded Attachment Theory developed by John Bowlby and refined by Mary Ainsworth. Though AT/P proponents actively cite and reference Bowlby and Ainsworth as the starting point for what they believe, most of what they say is contrary to what Attachment Theory actually holds to be true.
In truth, AT/P is shown to be derived from the discredited "hydraulic view" of negative emotions, where therapists seek to release "bottled up" emotions in a client, so they experience a catharsis and so improve their behavior. As Samantha Wilson had earlier observed, there is no theoretical necessity that the improved behavior will manifest as better attachment.
The foundational (theoretical) differences lead AT/P practitioners into error. It starts with diagnosis, where practitioners find attachment problems to be the root problem for children displaying a wide range of behavioral problems. Often they clinically equate these problems as symptoms or signs of Reactive Attachment Disorder (RAD), as found in the fourth edition of the Diagnostic and Statistical Manual (DSM-IV) of the American Psychiatric Association. However, the list of such symptoms and signs goes well beyond the criteria laid out for a diagnosis of RAD. The equation additionally ignores other required elements of a RAD diagnosis, particularly the requirement to differentiate it from other conditions, such as PTSD, ADHD, ODD, and a range of others falling under the umbrella of conduct disorders. Practitioners routinely ignore or dismiss other, better-understood diagnoses that might suggest different, potentially more effective treatment plans.
Next, AT/P practitioners engage in interventions that other professionals would not use. First, many of these approaches are contra-indicated for the diagnoses that other professionals would make. Second, these approaches are inconsistent both with mainstream attachment theory and scientific research. Third, AT/P treatment goals invariably seek to change the child, rather than the relationship through the parent (as has also been pointed out by Mercer — see above).
Then there is the risky nature of AT/P. There are significant physical risks, as indeed there have been abuses and even deaths associated with AT/P practices. AT/P procedures also carry a high risk of psychological damage to a child. Weighed against the negligible (or at least unobservable) benefits of AT/P, there is little basis for an ethical professional to offer AT as the treatment of choice for any child. There is even less basis, considering that there are empirically-supported alternatives available for effective treatment of the AT/P-targetted population. (See Weisz et al. meta-analysis.)
Finally, parents and others need to know that there are acceptable alternatives to AT/P. While AT/P purports to change a child's basic temperament or personality, in fact there is no known way to do this. Yet there are effective means of treating many of the conditions that children mistakenly diagnosed with RAD may actually have. And more, there are also empirically validated "effective technologies for stabilizing, managing, and containing children's antisocial and violent behavior, reducing family conflict, improving children's social skills and their ability to regulate emotion, improving school adjustment and achievement and peer relationships, and reducing anxiety and fear in children who have been traumatized by early experiences.
The APSAC articles prompted some response from the AT/P community which were notable in at least one respect: practitioners denied that they were actually doing what they were accused in these articles of doing, particularly the use of coercive restraint. (In reply, the APSAC authors cited their sources and stood by their prior statements.) This is similar to the public protests made by proponents of AT/P when legislative bodies consider outlawing the use of coercive restraint in therapy: they deny that this is what they do. Yet, the wonder is why they are concerned about the restrictions if they are not doing what is proposed to be restricted.
Original text material copyright 2003-2020 Advocates for Children in Therapy, Inc. WRITE US


text:
\section{Introduction}

A perpetuity is a random variable $X$ in $\ensuremath{\mathbb{R}}$
that satisfies the stochastic fixed-point equation
\begin{equation}
  \label{eq:fixedpoint}
  X\ensuremath{\stackrel{d}{=}} AX+b,
\end{equation}
where the symbol $\ensuremath{\stackrel{d}{=}}$ denotes that left and right
hand side in \eqref{eq:fixedpoint} are identically
distributed and where $(A,b)$  is a vector of
random variables being independent of $X$, whereas
dependence between $A$ and $b$ is allowed.

Perpetuities arise in various different contexts: In discrete
mathematics, perpetuities come up as the limit distributions of certain
count statistics of decomposable combinatorial structures such as random
permutations or random integers. In these areas, perpetuities often
arise via relationships to the GEM and Poisson-Dirichlet distributions;
see \citet*{ArBaTa03} for perpetuities, GEM and Poisson-Dirichlet
distribution in the context of combinatorial structures; see
\citet{DonGrim93} for occurrences in probabilistic number theory.  In
the probabilistic analysis of algorithms, perpetuities arise as limit
distributions of certain cost measures of recursive algorithms such as
the selection algorithm Quickselect, see e.g.~\citet{HwTsai02} or
\citet*{MaMoSmy95}.  In insurance and financial mathematics, a perpetuity
represents the value of a commitment to make regular payments, where $b$
represents the payment and $A$ a discount factor both being subject to
random fluctuation; see, e.g.~\citet{GolMal00} or \citet*[Section
8.4]{EmKlMi97}.

As perpetuities are given implicitly by their fixed-point
characterization \eqref{eq:fixedpoint}, properties of their
distributions are not directly amenable. Nevertheless, various questions
about perpetuities have already been settled.  Necessary and sufficient
conditions on $(A,b)$ for the fixed-point equation \eqref{eq:fixedpoint}
to uniquely determine a probability distribution are discussed in
\citet{Ver79} and \citet{GolMal00}. The types of distributions possible
for perpetuities have been identified in \citet*{AIR07}.  Tail behavior
of perpetuities has been studied for certain cases in \citet{GolGru96}.

In the present article, we are interested in the central
region of the distributions. The aim is to algorithmically approximate
perpetuities, in particular their distribution functions and their
Lebesgue densities (if they exist).

For this, we apply and refine a method proposed in \citet{DevNein02}
that was originally designed for random variables $X$ satisfying
distributional fixed-point equations of the form
\begin{equation}\label{glnn1}
X\ensuremath{\stackrel{d}{=}} \sum_{r=1}^K A_r X^{(r)}+b,
\end{equation}
where $X^{(1)},\ldots,X^{(K)},(A_1,\ldots,A_K,b)$ are independent with
$X^{(r)}$ being identically distributed as $X$ for $r=1,\ldots, K$ and
random coefficients $A_1,\ldots,A_K$, $b$, and $K\ge 2$.

The case of perpetuities, i.e., $K=1$, structurally differs from the
cases $K\ge 2$: The presence of more than one independent copy of $X$ on
the right hand side in \eqref{glnn1} often has a smoothing effect so
that under mild additional assumptions on $(A_1,\ldots,A_K,b)$ the
existence of smooth Lebesgue densities of $X$ follows, see
\citet{FilJans00} and \citet{DevNein02}. On the other hand, the case
$K=1$ often leads to distributions ${\cal L}(X)$ that have no smooth
Lebesgue density; an example is discussed in Section \ref{sec:keyEx}.

Our basic approach to approximate perpetuities is as follows:
A random variable $X$ satisfies the distributional identity
\eqref{eq:fixedpoint} if and only if its distribution is a fixed-point
of the map $T$ on the space $\mathcal{M}$ of probability distributions,
given by
\begin{equation}
  T: \mathcal{M}\rightarrow\mathcal{M},\ \mu\mapsto\ensuremath{\mathcal{L}}(AY+b),
\end{equation}
where $Y$ is independent of $(A,b)$, and $\ensuremath{\mathcal{L}}(Y)=\mu$. Under the
conditions $\|A\|_p<1$ and $\|b\|_p<\infty$ for some $p\ge 1$, which we
assume throughout the paper, this map is a contraction on certain
complete metric subspaces of $\mathcal{M}$. Hence, $\ensuremath{\mathcal{L}}(X)$ can be
obtained as limit of iterations of $T$, starting with some distribution
$\mu_{0}$.

However, it is not generally possible to algorithmically compute the
iterations of $T$ exactly.  We therefore use discrete approximations
$(A^{(n)},b^{(n)})$ of $(A,b)$, which become more accurate for
increasing $n$, to approximate $T$ by a mapping $\tilde T^{(n)}$,
defined by
\begin{equation*}
  \tilde T^{(n)}: \mathcal{M}\rightarrow\mathcal{M},\
  \mu\mapsto\ensuremath{\mathcal{L}}\!\left(A^{(n)}Y+b^{(n)}\right),
\end{equation*}
where again $Y$ is independent of
$(A^{(n)},b^{(n)})$ and $\ensuremath{\mathcal{L}}(Y)=\mu$.

To allow for an efficient computation of the approximation, we impose
a further discretisation step $\discrete{\cdot}$, introduced in
Section~\ref{sec:convRates}, defining
\begin{equation*}
  T^{(n)}:\mathcal{M}\rightarrow\mathcal{M},\
  \mu\mapsto\ensuremath{\mathcal{L}}\!\left(\discrete{A^{(n)}Y+b^{(n)}}\right),
\end{equation*}
where $Y$ is independent of $(A^{(n)},b^{(n)})$ and $\ensuremath{\mathcal{L}}(Y)=\mu$.

In Section~\ref{sec:convRates}, we give conditions
for $T^{(n)}\circ T^{(n-1)}\circ\dots\circ
T^{(1)}(\mu_{0})$ to converge to the perpetuity given as the solution of
\eqref{eq:fixedpoint}. To this aim, we derive a
rate of convergence in the minimal $L_{p}$ metric
$\minl[p]$, defined on the space $\mathcal{M}_{p}$
of probability measures on $\ensuremath{\mathbb{R}}$ with finite absolute
$p$th moment by
\begin{equation}\label{eq:defminl}
  \minl(\nu,\mu)\ensuremath{\mathop{:}\!\!=}
  \inf\left\{
    \norm[p]{V-W\bigr.}:\ \ensuremath{\mathcal{L}}(V)=\nu,\ensuremath{\mathcal{L}}(W)=\mu
  \right\}, \quad\text{ for }\nu,\mu\in\mathcal{M}_{p},
\end{equation}
where $\norm[p]{\cdot}$ denotes the $L_{p}$-norm of random variables.  To
get an explicit error bound for the distribution function, we then
convert this into a rate of convergence in the Kolmogorov metric $\ensuremath{\rho}$,
defined by
\begin{equation*}
  \ensuremath{\rho}(\nu,\mu)\ensuremath{\mathop{:}\!\!=}
   \sup_{x\in\ensuremath{\mathbb{R}}}\abs{F_{\nu}(x)-F_{\mu}(x)\big.},
\end{equation*}
where $F_{\nu},F_{\mu}$ denote the distribution functions of
$\nu,\mu\in\mathcal{M}_{p}$.  This implies explicit rates of convergence for
distribution function and density, depending on the corresponding moduli
of continuity of the fixed-point.

For these moduli of continuity we find global bounds for perpetuities
with \mbox{$b\equiv1$} in Section~\ref{sec:ax1}. For cases with random
$b$, we have to derive these moduli of continuity individually. One
example, connected to the selection algorithm Quickselect, is worked out
in detail in Section~\ref{sec:keyEx}.

We analyze the complexity of our approach in Section \ref{sec:complex}.
As a measure for the complexity of the approximations for distribution
function and density, we use the number of steps needed to obtain an
approximation that has distance, in supremum norm, of at most $1/n$ to
the true function. Although we generally follow the approach in
\citet{DevNein02}, we can improve the complexity significantly by using
different discretisations.  For the approximation of the distribution
function to an accuracy of $1/n$ in a typical case, we obtain a
complexity of $O(n^{1+\epsilon})$ for any $\epsilon>0$. In comparison,
the algorithm described in \citet{DevNein02}, which originally was
designed for fixed-point equations of type \eqref{glnn1} with $K\ge 2$,
would lead to a complexity of $O(n^{4+\epsilon})$, if applied to our
cases. For the approximation of the density to an accuracy of $1/n$, we
obtain a complexity of $O(n^{1+1/\alpha+\epsilon})$ for any $\epsilon>0$
in the case of $\alpha$-H\"older continuous densities, cf.
Corollary~\ref{cor:complex}.

An extended abstract of this article appeared in \citet{KnN07}.

\section{Discrete approximation and convergence}
\label{sec:convRates}

Recall that our basic assumption in equation \eqref{eq:fixedpoint} is
that $\norm[p]{A}<1$ and $\norm[p]{b}<\infty$ for some $p\geq1$.
To obtain an algorithmically computable approximation of the solution of
the fixed-point equation \eqref{eq:fixedpoint}, we use an approximation
of the sequence defined as follows: We replace $(A,b)$ by a sequence of
independent discrete approximations $(\An,\bn)$, converging to $(A,b)$
in $p$th mean for $n\rightarrow\infty$. To reduce the complexity, we
introduce a further discretisation step $\discrete{\cdot}$, which
reduces the number of values attained by $X_{n}$:
 \begin{align}
   \label{eq:defXtn}
   \Xn[0]\ensuremath{\mathop{:}\!\!=}\discretet[0]{\ensuremath{\mathbb{E}} X},\quad
   \Xtn\ensuremath{\mathop{:}\!\!=} \An\Xn[n-1]+\bn,\quad
   \Xn\ensuremath{\mathop{:}\!\!=}\discretet{\Xtn},\quad
   n\geq1.
 \end{align}
 We assume that the discretisations $\An$, $\bn$ and $\discrete{\cdot}$
 satisfy
\begin{align}
  \label{eq:approxR}
  \norm[p]{\An-A}\leq \RAn, \quad
  \norm[p]{\bn-b}\leq \Rbn, \quad
  \norm[p]{\discretet{\Xtn}-\Xtn}\leq \RXn,
\end{align}
for some error functions $R_{A}$, $R_{b}$ and $R_{X}$, which we specify
later.

Furthermore, we assume that there exists some $\ximax<1$, such that for
all $n\ge 1$,
\begin{equation}
  \label{eq:xiA}
  \norm[p]{\An}\!\leq \ximax,
\end{equation}
which in applications is easy to obtain, since $\|A\|_p<1$.

By arguments similar to those used in \citet{FilJans02} and
\citet{DevNein02} we obtain the following convergence rates for the
approximations $\Xn$ to converge to the corresponding characteristics of the
fixed-point $X$. We use the shorthand notation
$\minl[p](X,Y)\ensuremath{\mathop{:}\!\!=}\minl[p](\ensuremath{\mathcal{L}}(X),\ensuremath{\mathcal{L}}(Y))$.

\begin{lm}\label{lm:lpR}
  Let $\left(\Xn\right)_{n\in\ensuremath{\mathbb{N}}_{0}}$ be defined by \eqref{eq:defXtn} and
  $\ximax$ as in \eqref{eq:xiA}.  Then
  \begin{equation}\label{eq:lpR}
    \minl(\Xn,X)
      \leq \ximax^{n}\,\norm[p]{X-X_{0}}
      + \sum_{i=0}^{n-1}\ximax^{i}\,\Rlpn[n-i],
  \end{equation}
  where $\Rlpn\ensuremath{\mathop{:}\!\!=}\RXn + \RAn\norm[p]{X} + \Rbn$ for the error
  functions in \eqref{eq:approxR}.
  \begin{proof}
    We have
    \begin{align}\label{eq:minlXnX}
      \minl(\Xn,X)&\leq \minl(\Xn,\Xtn)+\minl(\Xtn,X)\nonumber\\
      &\leq \norm[p]{\discretet{\Xtn}-\Xtn}+\minl(\Xtn,X).
    \end{align}
    The first summand is bounded by \eqref{eq:approxR} and for the
    second summand we have
    \begin{align*}
      \minl(\Xtn,X)
      &\leq \norm[p]{\Xtn-X} =\norm[p]{\An \Xn[n-1]+\bn- AX-b}\\
      &\leq \norm[p]{\An\Xn[n-1]-AX} + \norm[p]{\bn-b}\\
      &= \norm[p]{\An(\Xn[n-1]-X) - (A-\An)X} + \norm[p]{\bn-b}\\
      &\leq \norm[p]{\An}\norm[p]{\Xn[n-1]-X} +
            \norm[p]{A-\An}\norm[p]{X} +
            \norm[p]{\bn-b},
    \end{align*}
    where in the last step we use that $\An$ and $(\Xn[n-1]-X)$ as
    well as $(A-\An)$ and $X$ are independent by assumption.

    Now we use that the infimum in the definition of $\ell_{p}$ in
    \eqref{eq:defminl} is attained and assume additionally, that
    $\Xn[n-1]$ and $X$ are chosen with
    $\norm[p]{\Xn[n-1]-X}=\minl(\Xn[n-1],X)$.  Combining this with
    \eqref{eq:minlXnX} and using the bounds given in
    \eqref{eq:approxR} and \eqref{eq:xiA}, we obtain
    \begin{equation*}
      \minl(\Xn,X)\leq \RXn +
      \ximax\;\minl(\Xn[n-1],X) + \RAn\norm[p]{X} + \Rbn,
    \end{equation*}
    and the claim then follows by induction.
  \end{proof}
\end{lm}

To make these estimates explicit we have to specify bounds for
$\RAn$, $\Rbn$, and $\RXn$. We do so in two different ways, one
representing a polynomial discretisation of the corresponding random
variables and one representing an exponential discretisation. Better
asymptotic results are obtained by the latter one.

\begin{cor}
  \label{cor:lpR}
  Let $\Xn, n\in\ensuremath{\mathbb{N}}_{0}$ be defined by \eqref{eq:defXtn} and
   $\ximax$ as in \eqref{eq:xiA}, and assume
  \begin{equation*}
    \RAn\leq \CA\,\dfrac{1}{n^{r}},\qquad
    \Rbn\leq \Cb\,\dfrac{1}{n^{r}}, \qquad
    \RXn\leq \CX\,\dfrac{1}{n^{r}},
  \end{equation*}
  for some $r\geq1$. Then, we have
  \begin{equation*}
    \minl(\Xn,X)\leq C_{r}\,\frac{1}{n^{r}},
  \end{equation*}
  where
  \begin{equation}
    \label{eq:defCr}
    C_{r}:=
      \frac{r^{r}\,\norm[p]{X-\Xn[0]}}{\Bigl(e\,\ln\!\left(1/\ximax\right)\Bigr)^{r}} +
      \frac{r!\left(\CX + \Cb + \CA\,\norm[p]{X}\right)}%
           {\left(1-\ximax\right)^{r+1}}.
  \end{equation}
  \begin{proof}
    Using Lemma~\ref{lm:lpR} we get
    \begin{equation}\label{eq:lpr}
      \minl(\Xn,X)
      \leq \ximax^{n}\norm[p]{X-\Xn[0]}+
      (\CX+\CA\norm[p]{X}+\Cb)
      \sum_{i=0}^{n-1}\frac{\ximax^{i}}{\left(n-i\right)^{r}}.
    \end{equation}
    For the first summand, we use that the function $x\mapsto
    x^{r}\ximax^{x}$ has its maximum at $x=r/\ln(1/\ximax)$.

    To see that the second summand is of order $n^{-r}$, note that
    $1/(n-i)\leq (i+1)/n$ for all $n\geq1$ and $0\leq i\leq n-1$.
    This implies that for $\ximax<1$,
    \begin{align*}
      \sum_{i=0}^{n-1}\frac{\ximax^{i}}{\left(n-i\right)^{r}} &\leq
      \frac{1}{n^{r}}\sum_{i=0}^{n-1}\left(i+1\right)^{r}\ximax^{i}\\&
      \leq
      \frac{1}{n^{r}}\sum_{i=0}^{\infty}(i+r)(i+r-1)\dotsm(i+1)\ximax^{i}\\
      &= \frac{r!}{\left(1-\ximax\right)^{r+1}}\,\frac1{n^{r}},
    \end{align*}
    where the last equality is obtained by differentiating the geometric
    series $r$ times.
  \end{proof}
\end{cor}

\begin{bem}
  In Corollary \ref{cor:lpR}, we are merely interested in the order of
  magnitude of $\ell_p(\Xn,X)$ without a sharp estimate of the
  constant $C_r$. When evaluating the error in an explicit example, we
  can evaluate \eqref{eq:lpr} directly to obtain sharper estimates.
\end{bem}

\begin{cor}
  \label{cor:lpRgamman}
  Let $\Xn, n\in\ensuremath{\mathbb{N}}_{0}$ be defined by \eqref{eq:defXtn} and $\ximax$ as in
  \eqref{eq:xiA}, and assume
  \begin{equation*}

    \RAn\leq \CA\,\dfrac{1}{\gamma^{n}},\qquad
    \Rbn\leq \Cb\,\dfrac{1}{\gamma^{n}}, \qquad
    \RXn\leq \CX\,\dfrac{1}{\gamma^{n}},
  \end{equation*}
  for some $1<\gamma<1/\ximax$. Then, we have
  \begin{equation*}
    \minl(\Xn,X)\leq C_{\gamma}\,\frac{1}{\gamma^{n}},
  \end{equation*}
  where
  \begin{equation}
    \label{eq:defCgamma}
    C_{\gamma}:=
      \norm[p]{X-\Xn[0]} +
      \frac{\left(\CX + \Cb + \CA\,\norm[p]{X}\right)}{1-\ximax\gamma}.
  \end{equation}
  \begin{proof}
    Using Lemma~\ref{lm:lpR} we get
    \begin{equation}\label{eq:lprgamman}
      \minl(\Xn,X)
      \leq \ximax^{n}\norm[p]{X-\Xn[0]}+
      (\CX+\CA\norm[p]{X}+\Cb)\gamma^{-n}
      \sum_{i=0}^{n-1}\ximax^{i}\gamma^{i},
    \end{equation}
    and the assumption on $\gamma$ implies that both summands are
    $O(\gamma^{-n})$ with the constant given in the lemma.
  \end{proof}
\end{cor}

\begin{lm}
  \label{lm:kolBound}
  Let $\Xn$ and $C_{r}$ be as in Corollary~\ref{cor:lpR}
  and $X$ have a bounded density $f_{X}$. Then, the distance in the
  Kolmogorov metric can be bounded by
  \begin{equation}\label{eq:kolBoundPoly}
    \ensuremath{\rho}(\Xn,X)\leq
    \left(
      C_{r}\left(p+1\right)^{1/p}\norm[\infty]{f_{X}}
    \right)^{p/(p+1)}
     n^{-rp/(p+1)}.
  \end{equation}
Similarly, for $\Xn$ and $C_{\gamma}$ as in
Corollary~\ref{cor:lpRgamman}, we have
  \begin{equation}\label{eq:kolBoundExp}
    \ensuremath{\rho}(\Xn,X)\leq
    \left(
      C_{r}\left(p+1\right)^{1/p}\norm[\infty]{f_{X}}
    \right)^{p/(p+1)}
    \gamma^{pn/(p+1)}.
  \end{equation}
  \begin{proof}
    We use Lemma~5.1 in \citet{FilJans02}, which states, that for $X$
    with bounded density $f_{X}$ and any $Y$,
    \begin{equation*}
      \ensuremath{\rho}(Y,X)\leq\left(\left(p+1\right)^{1/p}\norm[\infty]{f_{X}}
        \,\minl(Y,X)\right)^{p/(p+1)}\quad\text{for }p\geq1.
    \end{equation*}
    Using Corollaries~\ref{cor:lpR} and \ref{cor:lpRgamman}
    respectively, we get the stated result.
  \end{proof}
\end{lm}

\begin{bem}
  In some cases, we can give a similar bound, although the density of
  $X$ is not bounded or no explicit bound is known. Instead, it is
  sufficient to have a bound for the modulus of continuity of the
  distribution function $F_{X}$ of $X$, cf.~\citet{Kn06}.
\end{bem}

To approximate the density of the fixed-point, we define
\begin{equation}
  \label{eq:approxfn}
  f_{n}(x)=\frac{
    F_{n}(x+\delta_{n})-F_{n}(x-\delta_{n})
  }{2\delta_{n}},
\end{equation}
where $F_{n}$ is the distribution function of $\Xn$. For this
approximation we can give a rate of convergence, depending on the
modulus of continuity of the density of the fixed-point, which is
defined by
\begin{equation*}
  \ensuremath{\Delta}_{f_{X}}(\delta)\ensuremath{\mathop{:}\!\!=}\!\!
  \sup_{\substack{u,v\in\ensuremath{\mathbb{R}}\\ \abs{u-v}\leq\delta}}\!
    \abs{\f[u]-\f[v]\bigr.},\quad \delta\geq0.
\end{equation*}

\begin{lm}\label{lm:difffnf}
  Let $X$ have a density $f_{X}$ and let $\Xn, n\in\ensuremath{\mathbb{N}}_{0}$ be defined by
  \eqref{eq:defXtn}.  Then, for $f_{n}$ defined by \eqref{eq:approxfn}
  and all $\delta_n>0$,
  \begin{equation*}
    \norm[\infty]{f_{n}-f_{X}\bigl.}\leq
    \frac{1}{\delta_n}\;\ensuremath{\rho}(\Xn,X)
    + \ensuremath{\Delta}_{f_{X}}\!\left(\delta_{n}\right).
  \end{equation*}
  \begin{proof}
    For any $x$, we have
    \begin{align*}
      \abs{f_{n}(x)-f_{X}(x)\bigl.}  &\leq \abs{\frac
        {F_{n}(x+\delta_n)-F_{n}(x-\delta_n)} {2\delta_n}-\frac
        {F(x+\delta_n)-F(x-\delta_n)}
        {2\delta_n}}+\\[1ex]
      &\qquad\qquad + \abs{\frac{F(x+\delta_n)-F(x-\delta_n)}
        {2\delta_n}-f_{X}(x)}   \\[2ex]
      &\leq \frac{1}{\delta_n}\;\ensuremath{\rho}(\Xn,X) +\frac{1}{2\delta_n}
      \int_{-\delta_n}^{\delta_n}\!\abs{f_{X}(x+y)-f_{X}(x)\big.}dy\\
      &\leq\frac{1}{\delta_{n}}\ensuremath{\rho}(\Xn,X) +\frac1{\delta_{n}}
      \int_{0}^{\delta_{n}}\!\!\!\ensuremath{\Delta}_{f_{X}}\!(y)\,dy.
    \end{align*}
    The assertion follows since $\ensuremath{\Delta}_{f_{X}}$ is monotonically increasing.
  \end{proof}
\end{lm}

\begin{cor}\label{cor:boundApproxDens}
  Let $X$ have a bounded density $f_{X}$, which is H\"older continuous
  with exponent $\alpha\in(0,1]$. For polynomial discretisation $X_{n}$
  and $C_{r}$ as in Corollary~\ref{cor:lpR} and $f_{n}$ defined by
  \eqref{eq:approxfn} with
  \begin{equation*}
    \delta_{n}\ensuremath{\mathop{:}\!\!=} L\,n^{-rp/\left((\alpha+1)(p+1)\right)}
  \end{equation*}
  with an $L>0$, we have
  \begin{equation*}
    \norm[\infty]{f_{n}-f_{X}}
    \leq
    \left(
      \left(
        C_{r}\left(p+1\right)^{1/p}\norm[\infty]{f_{X}}
      \right)^{p/(p+1)}\!\!\!/L
      + c\,L^{\alpha}
    \right)
    \, n^{-\alpha r p/\left((\alpha+1)(p+1)\right)}.
  \end{equation*}

  For exponential discretisation $X_{n}$ and $C_{\gamma}$ as in
  Corollary~\ref{cor:lpRgamman} and $f_{n}$ defined by
  \eqref{eq:approxfn} with
  \begin{equation*}
    \delta_{n}\ensuremath{\mathop{:}\!\!=} L\,\gamma^{- pn/\left((\alpha+1)(p+1)\right)},
  \end{equation*}
  with an $L>0$, we obtain
  \begin{equation*}
    \norm[\infty]{f_{n}-f_{X}}\leq
    \left(
      \left(
        C_{\gamma}\left(p+1\right)^{1/p}\norm[\infty]{f_{X}}
      \right)^{p/(p+1)}\!\!\!/L
      + c\,L^{\alpha}
    \right)
    \, \gamma^{\alpha pn/\left((\alpha+1)(p+1)\right)}.
  \end{equation*}
\end{cor}

\begin{bem}
  If $X$ is bounded and bounds for the density $f_{X}$ and its modulus
  of continuity are known explicitly, the last result is strong enough
  to construct a perfect simulation algorithm based on von Neumann's
  rejection method. Corollary~\ref{cor:boundApproxDens} can be turned
  into such an algorithm as done in
  \citet{Dev01} for the case of infinitely
  divisible perpetuities with approximation of densities by Fourier
  inversion, \citet*{DevFilNein00} for the case of the Quicksort limit
  distribution and \citet{DevNein02} for more general fixed-point
  equations of type \eqref{glnn1}.
\end{bem}

\newcommand{\ensuremath{s}}{\ensuremath{s}}
\section{Algorithm and Complexity} \label{sec:complex}

In this section, we will give an algorithm for an approximation
satisfying the assumptions in the last section for many important cases.
We assume that the distributions of $A$ and $b$ are given by Skorohod
representations, i.e.~by measurable functions
$\phi,\psi:[0,1]\!\rightarrow\!\ensuremath{\mathbb{R}}$, such that
\begin{equation}
  \label{eq:defPhiPsi}
  A=\phi(U) \quad\text{and}\quad b=\psi(U),
\end{equation} $U$ being uniformly distributed on $[0,1]$.
Furthermore, we assume that $\norm[\infty]\phi\leq1$ and that both
functions are Lipschitz continuous and can be evaluated in constant
time. Now we define the discretisation $\discrete{\cdot}$ by
\begin{align}
  \discrete{Y}:= \flr{\ensuremath{s}(n)\, Y}\!/\ensuremath{s}(n),\label{eq:defU_n}
\end{align}
where $\ensuremath{s}(n)$ can be either polynomial, i.e.~$\ensuremath{s}(n)=n^{r}$ or
exponential, $\ensuremath{s}(n)=\gamma^{n}$.  Defining
\begin{align*}
  \An&\ensuremath{\mathop{:}\!\!=} \phi\!\left(\discrete{U}\right)\quad\text{and}\\
  \bn&\ensuremath{\mathop{:}\!\!=} \psi\!\left(\discrete{U}\right),
\end{align*}
the conditions on $\phi$ and $\psi$ ensure that
Corollary~\ref{cor:lpR} and \ref{cor:lpRgamman} can be applied.

We keep the distribution of $\Xn$ in an array $\mathcal{A}_{n}$, where
\begin{displaymath}
  \mathcal{A}_{n}[k]\ensuremath{\mathop{:}\!\!=}\Ws{X_{n}={k}/{\ensuremath{s}(n)}}
\end{displaymath}
for \mbox{$k\in\ensuremath{\mathbb{Z}}$}.
Note however, that as $A$ and $b$ are bounded, $\mathcal{A}_{n}[k]=0$ at
least for $\abs{k}>\ensuremath{s}(n)Q_{n}$, where $Q_{n}$ can be computed recursively as
$Q_{n}=\ceil{\norm[\infty]{A}Q_{n-1}+\norm[\infty]{b}}$ and
$Q_{0}=\ceil{\norm[\infty]{X_{0}}}\!=\ceil{\ensuremath{\mathbb{E}} X}$.

For simplicity we assume that $s(0)=s(1)=1$ and that $s(n)\in\ensuremath{\mathbb{N}}$ for
all $n$. The core of the implementation
is the following update procedure:
 \begin{algorithmic}
   \Procedure{update}{$\mathcal{A}_{n-1},\mathcal{A}_{n}$}
     \For{$i$}{$0$}{$\ensuremath{s}(n)-1$}
       \For{$j$}{$-\,\ensuremath{s}(n-1)\, Q_{n-1}$}{$\ensuremath{s}(n-1)\, Q_{n-1}$}
       \State \vspace{-3ex}
       \begin{align*}
         &u\quad \gets\quad \frac{i}{\ensuremath{s}(n)} \\[1ex]
         &k\quad \gets\quad \left\lfloor \ensuremath{s}(n)\,\left(
             \phi(u)\,\frac{j}{\ensuremath{s}(n-1)}+\psi(u)
           \right)\right\rfloor\hspace{1em} \\[1ex]
         &\hspace{-0.3ex}\mathcal{A}_n[k]\gets\hspace{0.5ex}
         \mathcal{A}_n[k]+\frac{1}{\ensuremath{s}(n)}\,\mathcal{A}_{n-1}[j]
       \end{align*}
       \EndFor
     \EndFor
   \EndProcedure
 \end{algorithmic}

Furthermore, we use a procedure
$\textsc{initialize}(\mathcal{A}_{n},n)$, which creates $\mathcal{A}_{n}$ as vector
with $2\ensuremath{s}(n)Q_{n}$ components with $\mathcal{A}_{n}[k]=0$ for
$-\ensuremath{s}(n)Q_{n}\leq k \leq\ensuremath{s}(n)Q_{n}$.

The whole algorithm then looks like this:
 \begin{algorithmic}
     \State \textsc{initialize}($\mathcal{A}_{0},0$)
     \vspace{-1em}
     \begin{flalign}\label{eq:algoInit}
     \mathcal{A}_{0}\!\left[\biggr.\flr{\Bigr.\ensuremath{s}(0)\;\ensuremath{\mathbb{E}} X}\right]\gets1&&
     \end{flalign}
     \vspace{-1.5em}
     \For{$n$}{$1$}{$N$}
       \State \textsc{initialize}($\mathcal{A}_{n},n$)
       \State \textsc{update}($\mathcal{A}_{n-1},\mathcal{A}_{n}$)
     \EndFor
     \State\Return $\mathcal{A}_{N}$
 \end{algorithmic}

Note, that \eqref{eq:algoInit} determines that we start the approximation
with $X_{0}$ as defined in \eqref{eq:defXtn}.

The complete code for polynomial discretisation for the example in
 Section~\ref{sec:keyEx}, implemented in C\hspace{-.05em}\raisebox{.4ex}{\tiny\bf +}\hspace{-.05em}\raisebox{.4ex}{\tiny\bf +}, can be found in
 \citet{Kn06}.

To approximate the density as in \eqref{eq:approxfn} with
$\delta_{N}=d/s(N)$ for some $d\in\ensuremath{\mathbb{N}}$, we compute a new array
$\mathcal{D}_{N}$ by setting
\begin{equation*}
  \mathcal{D}_{N}[k]
  =\frac{\ensuremath{s}(N)}{2d}\sum_{j=k-d+1}^{k+d}\!\!\!\!\mathcal{A}_{N}[j].
\end{equation*}

To measure the complexity of our algorithm, we estimate the number of
steps needed to approximate the distribution function and the density up
to an accuracy of $1/n$. For the case that $X$ has a bounded density
$f_{X}$ which is H\"older continuous, we give asymptotic bounds for
polynomial as well as for exponential discretisation. We assume the
general condition \eqref{eq:defPhiPsi}.

\begin{lm}\label{lm:complex}
  Assume that $X$ has a bounded density $f_{X}$, which is H\"older
  continuous with exponent $\alpha\in(0,1]$.  Using polynomial
  discretisation with exponent $r$, cf. Corollary~\ref{cor:lpR}, we can
  calculate for any $n\in\ensuremath{\mathbb{N}}$ approximations $\hat{F}, \hat{f}$ of the
  distribution function $F$ and the density $f$ of $X$ with
  \begin{displaymath}
    \norm[\infty]{\hat{F}-F}\leq\frac{1}{n},\qquad
    \norm[\infty]{\hat{f}-f}\leq\frac{1}{n}
  \end{displaymath}
  in time $T_{F}(n)$ and $T_{f}(n)$ respectively with
  \begin{displaymath}
    T_{F}(n)=O\!\left(n^{(2+2/r)(p+1)/p}\right)  \quad\text{and}\quad
    T_{f}(n)=O\!\left(n^{2\left(1+1/\alpha\right)(r+1)(p+1)/(rp)}\right).
\end{displaymath}

Using exponential discretisation with parameter $\gamma$ as in
Corollary~\ref{cor:lpRgamman}, approximation to the same accuracy
takes time
\begin{displaymath}
  T'_{F}(n)=O\!\left(n^{(p+1)/p}\log{n}\right)
  \quad\text{and}\quad
  T'_{f}(n)=O\!\left(n^{(1+1/\alpha)(p+1)/p}\log{n}\right)
\end{displaymath}
for the distribution
function and the density of $X$ respectively.

 \begin{proof}
    In one execution of {\sc update}($\mathcal{A}_{k-1},\mathcal{A}_{k}$), the
    outer loop is executed $\ensuremath{s}(k)$ times. The assumptions on $A$ and
    $b$ ensure that $Q_{k}=O(k)$, so we have $O(k\,\ensuremath{s}(k))$ runs
    of the inner loop and the whole procedure takes time
    $O\!\left(k\;\ensuremath{s}(k)^{2}\right)$. Hence, for any $N\in\ensuremath{\mathbb{N}}$, finding
    $\mathcal{A}_{N}$ costs time
    \begin{equation}\label{eq:runtimeUpdateN}
      O\!\left(\sum_{k=1}^{N}k\,\ensuremath{s}(k)^{2}\right)
      =O\!\left(N^{2}\,\ensuremath{s}\!\left(N\right)^{2}\right).
    \end{equation}

    For discretisations with $\ensuremath{s}(n)=n^{r}$ we get a running
    time of $O(N^{2r+2})$ to find $\mathcal{A}_{N}$, and \eqref{eq:kolBoundPoly} in
    Lemma~\ref{lm:kolBound} ensures that for the corresponding distribution function
    $F_{N}$ of $X_{N}$,
    \begin{displaymath}
       \norm[\infty]{F_{N}-F}\leq CN^{-rp/(p+1)}.
    \end{displaymath}
    Setting $N=\left(Cn\right)^{(p+1)/(rp)}$ and $\hat{F}\ensuremath{\mathop{:}\!\!=} F_{N}$,
    we get an approximation of the stated accuracy in time
    \begin{displaymath}
      T_{F}(n)=O(N^{2r+2})=O(n^{(2+2/r)(p+1)/p}).
    \end{displaymath}
    For the density of $X$ we use Corollary~\ref{cor:boundApproxDens}
    and $N'=\left(C'n\right)^{(\alpha+1)(p+1)/(\alpha rp)}$
    to obtain the stated bound.

    When using exponential discretisation, $\ensuremath{s}(n)=\gamma^{n}$, we need
    time $O(N^{2}\gamma^{N})$ to find $\mathcal{A}_{N}$. Using the
    corresponding results in Lemma~\ref{lm:kolBound} and
    Corollary~\ref{cor:boundApproxDens} ensures the stated running
    times.
  \end{proof}
\end{lm}

\begin{cor}\label{cor:complex}
  Assume \eqref{eq:defPhiPsi} and that $X$ has a bounded density
  $f_{X}$, which is H\"older continuous with exponent
  $\alpha\in(0,1]$. Then, using exponential discretisation as in
  Corollary~\ref{cor:lpRgamman}, approximation to an accuracy of  $1/n$
  takes time $O(n^{1+\epsilon})$ for the distribution function and time
  $O(n^{1+1/\alpha+\epsilon})$ for the density of $X$ for all
  $\epsilon>0$.
  \begin{proof}
    Note that $\norm[\infty]{\phi}\leq1$ and $\norm[p]{A}<1$ for some
    $p\geq1$ implies that $\norm[p]{A}<1$ for all $p\geq1$. Thus, in
    Lemma~\ref{lm:complex}, $p$ can be chosen arbitrarily large.
  \end{proof}
\end{cor}

\newcommand{\PX}[1][(x)]{\ensuremath{\mathbb{P}}_{X}#1}
\newcommand{\intgf}[3]{\int_{#1}^{#2}\!\!g(x,#3)\f dx}
\newcommand{\intp}[2][t]{\int_{p_{#1}}^{#2}\!\!\!g(x,#2)\f dx}
\newcommand{\intf}[3]{\int_{#1}^{#2}\!\!\!#3\f dx}
\newcommand{\fmax}[1][\gamma_{t}]{f_{\max}(#1)}
\newcommand{\norm[\infty]{\ff}}{\norm[\infty]{f_{X}}}

\section{A simple class of perpetuities} \label{sec:ax1}

In order to make the bounds of Section~\ref{sec:convRates} explicit in
applications, we need to bound the absolute value and modulus of
continuity of the density of the fixed-point. For a simple class of
fixed-point equations, we give universal bounds in this section. For
more complicated cases, bounds have to be derived individually, which we
work out for one example in Section~\ref{sec:keyEx}.

For fixed-point equations of the form
\begin{equation}
  \label{eq:ax+1}
  X\ensuremath{\stackrel{d}{=}} AX+1 \qquad \text{with }A\geq0,
\end{equation}
where $A$ and $X$ are independent, we can bound the
density and modulus of continuity of $X$ using the
corresponding values of $A$.

\begin{lm}
  \label{lm:densAX+1}
  Let $X$ satisfy fixed-point equation \eqref{eq:ax+1} and $A$ have a
  density $f_{A}$.  Then $X$ has a density $f_{X}$ satisfying
  \begin{equation}\label{eq:inteqfX_AX+1}
    f_{X}(u)=\int_{1}^\infty
      \frac{1}{x}\;f_{A}\!\left(\!\frac{u-1}{x}\!\right)f_{X}(x)dx,
    \quad \text{ for }u\geq1,%
  \end{equation}%
  and $f_{X}(u)=0$ otherwise.
  \begin{proof}
    From the fixed-point equation we can see that $X\geq1$ almost
    surely. Now let $\ensuremath{\mathbb{P}}_{X}$ be the distribution of $X$. Conditioning
    on $X$, we get for any Borel set $B$:
    \begin{align*}
      \Ws{X\in B}
      &=\int_{1}^{\infty}\!\!\Ws{Ax+1\in B}d\ensuremath{\mathbb{P}}_{X}(x)\\
      &=\int_{1}^{\infty}\!\!\!\int_{B}f_{xA+1}(u)du\,d\ensuremath{\mathbb{P}}_{X}(x)\\
      &=\int_{1}^{\infty}\!\!\!\int_{B}
          \frac1x\; f_{A}\!\left(\!\frac{u-1}{x}\!\right)du\,d\ensuremath{\mathbb{P}}_{X}(x)\\
      &=\int_{B}\int_{1}^{\infty}
          \frac1x\; f_{A}\!\left(\!\frac{u-1}{x}\!\right)d\ensuremath{\mathbb{P}}_{X}(x)\;du,
    \end{align*}
    where we can use Fubini's theorem in the last step, because the
    integrand is product measurable.
    The claim follows, as this is just the definition of a Lebesgue
    density.
  \end{proof}
\end{lm}

\begin{cor}
  Let $A$ have a bounded density $f_{A}$. Then $X$ has a density
  $f_{X}$ satisfying
  \begin{equation*}
    \norm[\infty]{f_{X}}\leq\norm[\infty]{f_{A}}.
  \end{equation*}
  \begin{proof}
    Using Lemma~\ref{lm:densAX+1} we get
    \begin{equation*}
      \norm[\infty]{f_{X}}\leq \norm[\infty]{f_{A}}\,\Erw{\frac1X},
    \end{equation*}
    but $X\geq1$ implies $\Erw{1/X}\leq1$, so the claim follows.
  \end{proof}
\end{cor}

\begin{cor}\label{cor:modcontXfromContinuousA}
  Let $A$ have a density $f_{A}$, and $\ensuremath{\Delta}_{f_A}$ be its modulus of
  continuity. Then the modulus of  continuity $\ensuremath{\Delta}_{f_{X}}$ of
  $f_{X}$ satisfies
  \begin{equation*}
    \ensuremath{\Delta}_{f_X}(\delta)\leq\ensuremath{\Delta}_{f_A}(\delta),
    \quad\delta>0.
  \end{equation*}
    \begin{proof}
    Using \eqref{eq:inteqfX_AX+1}, we obtain for any $u,v\in\ensuremath{\mathbb{R}}$
    \begin{align}\label{eq:intboundMCAX+1}
      \abs{f_{X}(u)-f_{X}(v)\bigr.}\leq
      \int_{1}^{\infty}\frac1x f_{X}(x)\abs{
        f_{A}\left(\!\frac{u-1}x\right)-f_{A}\left(\!\frac{v-1}x\right)
      }dx.
    \end{align}

    But $x\geq1$ and the modulus of continuity $\ensuremath{\Delta}_{f_A}$ is
    monotonically increasing by definition, so we can bound
    \begin{equation*}
      \abs{f_{A}\left(\!\frac{u-1}x\right)-f_{A}\left(\!\frac{v-1}x\right)}
      \leq\ensuremath{\Delta}_{f_A}\left(\!\frac{\abs{u-v}}x\right)
      \leq\ensuremath{\Delta}_{f_A}(\abs{u-v}),
    \end{equation*}
    and plugging this into inequality \eqref{eq:intboundMCAX+1}, we
    obtain
    \begin{equation*}
      \abs{f_{X}(u)-f_{X}(v)\bigr.}
      \leq \Erw{\frac{1}{X}}\,\ensuremath{\Delta}_{f_A}(\abs{u-v}).
    \end{equation*}
    Now we use that $\Erw{1/X}\leq1$ and take the supremum over
    all suitable $u,v$.
  \end{proof}
\end{cor}

\newcommand{\bar{f}_{A}}{\bar{f}_{A}}

This result is only useful if the density of $A$ is continuous, but
we can extend it to many practical examples, where $f_A$ has
jumps at points in a set $\mathcal{I}_{A}$. We use the jump function
of $f_{A}$, defined by
\begin{equation*}
  \deltaf{A}(s)=f_{A}(s)-\lim_{x\uparrow s}f_{A}(x),\quad s>0
\end{equation*}
and a modification of $f_{A}$ where we remove all jumps,
\begin{displaymath}
  \bar{f}_{A}:=f_{A}
    -\sum_{s\in\mathcal{I}_{A}\setminus\{0\}}\deltaf{A}(s)\ensuremath{\mathbbm{1}}_{[s,\infty)}.
\end{displaymath}
Since $X\geq1$, we now denote by $\Delta_{f_X}$ the modulus of
continuity of the restriction of $f_X$ to $(1,\infty)$.

\begin{lm}
  Let $A$ have a bounded c\`adl\`ag density $f_{A}$.  Then, for all
  $\delta>0$,
  \begin{align*}
    \ensuremath{\Delta}_{f_X}(\delta)\leq
    \ensuremath{\Delta}_{\bar{f}_{A}}(\delta)
    +\norm[\infty]{f_{X}}\!\!
    \sum_{s\in\mathcal{I}_{A}\setminus\{0\}}\!\!\!
      \frac{\abs{\deltaf{A}(s)}\delta}{s}.
  \end{align*}
    \begin{proof}
      We give the proof for the case that $f_{A}$ has only one jump, say
      in $s_{0}>0$. The general case then follows similarly.
      For $1\leq u<v$, we have
    \begin{equation*}
      \abs{f_{X}(u)-f_{X}(v)\bigr.}\leq
      \int_{1}^{\infty}\frac1x f_{X}(x)\abs{
        f_{A}\!\!\left(\!\frac{u-1}x\!\right)
        -f_{A}\!\!\left(\!\frac{v-1}x\!\right)
      }dx.
    \end{equation*}
    We define
    \begin{equation*}
      \alpha\ensuremath{\mathop{:}\!\!=}\frac{u-1}{s_{0}}\vee1,\quad
      \beta\ensuremath{\mathop{:}\!\!=}\frac{v-1}{s_{0}}\vee1
    \end{equation*}
    and divide the range of integration into the three intervals
    $(1,\alpha],[\alpha,\beta],$ and $[\beta,\infty)$. Now, in the first and
    third interval, differences of values of $f_{A}$ and $\bar{f}_{A}$
    coincide. Moreover, for $x\in[\alpha,\beta]$ we have
    \begin{align*}
      \abs{
        f_{A}\!\left(\!\frac{u-1}x\!\!\right)
        -f_{A}\!\left(\!\frac{v-1}x\!\!\right)
      }
      &\leq \abs{
        \bar{f}_{A}\!\!\left(\!\frac{u-1}x\!\right)
        -\bar{f}_{A}\!\!\left(\!\frac{v-1}x\!\right)
      }
      +\abs{\deltaf{A}(s_{0})\bigr.}.
    \end{align*}

    Putting everything together we obtain
    \begin{align*}
      \lefteqn{\abs{f_{X}(v)-f_{X}(u)\big.}\leq}\qquad\quad&\\
      &\leq
      \int_{1}^{\infty}\!\frac1x f_{X}(x)\abs{
       \bar{f}_{A}\!\left(\!\frac{u-1}x\!\right)
        -\bar{f}_{A}\!\left(\!\frac{v-1}x\!\right)
      }dx
      + \int_{\alpha}^{\beta}\frac1x f_{X}(x)
        \abs{\deltaf{A}(s_{0})\big.}dx\\[1ex]
      &\leq
      \int_{1}^{\infty}\!\frac1x f_{X}(x)\abs{
       \bar{f}_{A}\!\left(\!\frac{u-1}x\!\right)
        -\bar{f}_{A}\!\left(\!\frac{v-1}x\!\right)
      }dx
      +\norm[\infty]{f_{X}}\frac{v-u}{s_{0}}\abs{\deltaf{A}(s_{0})\big.}.
    \end{align*}
    We now
    bound the latter integral by $\ensuremath{\Delta}_{\bar{f}_{A}}(v-u)$ as in
    Corollary~\ref{cor:modcontXfromContinuousA},
    and the claim follows by taking the supremum over all
    $v-u\leq\delta$.
  \end{proof}
\end{lm}

\section{Example: Number of key exchanges in Quickselect}
\label{sec:keyEx}

In this section, we apply our algorithm to the fixed-point
equation
\begin{equation}\label{eq:ux+u(1-u)}
  X\ensuremath{\stackrel{d}{=}} UX+U(1-U),
\end{equation}
where $U$ and $X$ are independent and $U$ is uniformly distributed on
$[0,1]$. This equation appears in the analysis of the selection
algorithm Quickselect. The asymptotic distribution of the number of key
exchanges executed by Quickselect when acting on a random equiprobable
permutation of length $n$ and selecting an element of rank $k=o(n)$ can
be characterized by the above fixed-point equation, see
\citet{HwTsai02}.

We use our algorithm to get a discrete approximation of the fixed
point. The plot of a histogram, generated with $80$ iterations of the
algorithms using for the discretisation $s(n)=n^{3}$, can be
found in Figure~\ref{fig:histUX+U(1-U)}.
\begin{figure}[!ht]
  \centering
  \includegraphics*{KeyEx}
  \caption{Histogram of approximation for $X\ensuremath{\stackrel{d}{=}} UX+U(1-U)$.}
  \label{fig:histUX+U(1-U)}
\end{figure}

In the following, we specify how the bounds in
Section~\ref{sec:convRates} can be made explicit for
this example.

\begin{lm}
  \label{lm:momBsp}
  Let $X$ be a solution of \eqref{eq:ux+u(1-u)}. Then, we have $0\leq
  X\leq1$ almost surely, and the moments are recursively given by
  $\Erw{X^{0}}=1$ and
  \begin{equation*}
    \label{eq:expXk}
    \Erw{X^{k}}
    =(k+1)!\,(k-1)!\sum_{j=0}^{k-1}\frac{\Erw{X^{j}}}{j!(2k-j+1)!},
    \quad k\geq1,
  \end{equation*}
  in particular, $\Erw{X}=1/3$.
  \begin{proof}

    Both claims follow directly from the fixed-point equation in
    \eqref{eq:ux+u(1-u)}, using that the solution is unique. To compute the
    moments, note that $\Erw{U^{k}(1-U)^{k-j}}$ is equal to the
    Beta function $\mathrm{B}(k+1,k-j+1)$, so we have
    \begin{align*}
      \Erw{X^{k}}
      &=\frac{1}{1-\Erw{U^{k}}}\,
      \sum_{j=0}^{k-1}\binom{k}{j}\Erw{X^{j}}\mathrm{B}(k+1,k-j+1)\\[1ex]
      &=\frac{k+1}{k}\,\sum_{j=0}^{k-1}\frac{k!}{j!(k-j!)}
      \,\frac{k!(k-j)!}{(2k-j+1)!}\,\Erw{X^{j}}
    \end{align*}
    and the assertion follows.
  \end{proof}
\end{lm}

\begin{lm}\label{lm:Geps}
  Let $X$ be a solution of \eqref{eq:ux+u(1-u)}.
  Then, for all $\kappa\in\ensuremath{\mathbb{N}}$ and $\epsilon>0$,
  \begin{equation*}
    \Ws{X\geq1-\epsilon}
    \leq2^{(\kappa^{2}-\kappa)/4}\,\epsilon^{\kappa/2}.
  \end{equation*}
  \begin{proof}
    Using that $X$ is supported by $[0,1]$, it is easy to
    show that for all $\epsilon>0$,
    \begin{align*}
      \Ws{X\geq1-\epsilon}
      &=\Ws{UX+U(1-U)\geq1-\epsilon}\\
      &\leq\Ws{X\geq1-2\epsilon}\,\Ws{U\geq1-\sqrt{\epsilon}},
    \end{align*}
    and this inequality can be translated into
    \begin{equation}
      \label{eq:GepsFirst}
      \Ws{X\geq1-2\epsilon}\geq\frac{\Ws{X\geq1-\epsilon}}{\sqrt{\epsilon}}.
    \end{equation}

    Applying
    \eqref{eq:GepsFirst} $\kappa$ times, we get
    \begin{align*}
      1\geq
      \Ws{X\geq1-2^{\kappa}\epsilon}
      \geq \frac{
        \Ws{X\geq1-\epsilon}}{2^{\kappa(\kappa-1)/4}
        \,\epsilon^{\kappa/2}}.
    \end{align*}
    This implies the assertion.
  \end{proof}
\end{lm}

\renewcommand{\f}[1][x]{f(#1)}
\renewcommand{f_{X}}{f}

\begin{lm}
  \label{lm:intEqfX}
  Let $X$ be a solution of \eqref{eq:ux+u(1-u)}. Then $X$ has a
  Lebesgue density $f_{X}$ satisfying $\f[t]=0$ for $t<0$ or $t>1$ and
  \begin{equation}
    \label{eq:intf}
    \f[t]=
    2\int_{p_{t}}^{t}\!\!\!g(x,t)\f dx
    + \int_{t}^{1}\!\!\!g(x,t)\f dx
    \qquad\text{ for }t\in[0,1],
  \end{equation}
  where
  \begin{equation*}
    \label{eq:pt+gxt}
    p_{t}\ensuremath{\mathop{:}\!\!=} 2\sqrt{t}-1,
    \qquad g(x,t)\ensuremath{\mathop{:}\!\!=}\frac{1}{\sqrt{(1+x)^{2}-4t}}.
  \end{equation*}
  \begin{proof}
    Let $\PX[]$ be the distribution of $X$. Then we get for any Borel
    set $B$ by conditioning on $X$ as in the proof of
    Lemma~\ref{lm:densAX+1},
    \begin{align*}
      \Ws{X\in B}
      &=\Ws{\bigl.UX+U(1-U)\in B}\\
      &=\int_{0}^{1}\!\!\Ws{\bigl.Ux+U(1-U)\in B}d\PX\\
      &=\int_{0}^{1}\!\!\int_{B}\!\phi_{x}(t)dt\;d\PX\\
      &=\int_{B}\int_{0}^{1}\!\!\phi_{x}(t)d\PX\;dt
    \end{align*}
    where $\phi_{x}$ is a Lebesgue density of $(1+x)U-U^{2}$. The last
    step is valid by Fubini's theorem as $(x,t)\mapsto \phi_{x}(t)$ is
    product measurable, cf. \eqref{eq:defphi}.

    Hence, $X$ has a Lebesgue-density $\f$ satisfying
    \begin{equation}
      \label{eq:intfphi}
      \f[t]=\int_{0}^{1}\!\!\phi_{x}(t)\f dx.
    \end{equation}

    To find $\phi_{x}$, we observe that $(1+x)U-U^{2}\leq (1+x)^{2}/4$
    and get
    \begin{align*}
      \lefteqn{\Ws{(1+x)U-U^{2}\leq t}=}\qquad&\\
      &=\Ws{U\leq\frac{1+x-\sqrt{(1+x)^{2}-4t}}2\quad
        \text{or}\quad U\geq \frac{1+x+\sqrt{(1+x)^{2}-4t}}2}\\[1ex]
      &=\begin{cases}
        0 & \text{for } t<0,\\[2ex]
        \dfrac{1+x-\sqrt{(1+x)^{2}-4t}}2& \text{for }0\leq t < x,\\[2ex]
        1-\sqrt{(1+x)^{2}-4t}& \text{for }x\leq t\leq(1+x)^{2}/4,\\[2ex]
        1 & \text{otherwise.}
      \end{cases}
    \end{align*}

    To get a density, we differentiate with respect to $t$ and
    rewrite as a function of $x$ yielding
    \begin{equation}
      \label{eq:defphi}
      \phi_{x}(t)=
      \begin{cases}
        \dfrac2{\sqrt{(1+x)^{2}-4t}}& \text{for }2\sqrt{t}-1< x\leq t,\\[3ex]
        \dfrac1{\sqrt{(1+x)^{2}-4t}}& \text{for }t<x\leq1,\\[3ex]
        0 & \text{otherwise.}
      \end{cases}
    \end{equation}
    Plugging this into \eqref{eq:intfphi} we get the stated integral
    equation.
  \end{proof}
\end{lm}

\begin{bem}
  \label{bem:antiderivOfg}
  The integral of $g(x,t)$ with respect to $x$ can explicitly be
  evaluated:
  \begin{equation}
    \label{eq:antiderivOfg}
    \int\!g(x,t)\,dx = \ln\left(1+x+\sqrt{(1+x)^{2}-4t}\right).
  \end{equation}
\end{bem}

\begin{bem}\label{bem:f0keyEx}
  We will see in Lemma~\ref{lm:fHoelder} that $\f$ has a version that is
  continuous on $[0,1]$. For this version we have
  \begin{equation*}
    f(0)=\Erw{\frac1{1+X}}=0.759947956\dots
  \end{equation*}
  \begin{proof}
    Using integral equation \eqref{eq:intf} we have
    \begin{align*}
      f(0)=\int_{0}^{1}\frac{1}{1+x}\f dx,
    \end{align*}
    and by expanding the geometric series we obtain
    \begin{equation*}
      \Erw{\frac1{1+X}}=\sum_{k=0}^{\infty}(-1)^{k}\,\Erw{X^{k}},
    \end{equation*}
    which we can calculate to any accuracy using for the $k$th moments
    the formula given in Lemma~\ref{lm:momBsp}.
  \end{proof}
\end{bem}

In order to use Lemma~\ref{lm:kolBound} to bound
the deviation of our approximation, we need an
explicit bound for the density of $X$. We derive a
rather rough bound here and  see later, that we can
use the resulting bound from our approximation to
improve it.

\begin{lm}\label{lm:boundf}
  Let $f_{X}$ be the density of $X$ as in Lemma~\ref{lm:intEqfX}. Then
  \begin{equation*}
    \label{eq:boundf}
    \norm[\infty]{f_{X}}\leq 18.
  \end{equation*}
  \begin{proof}
    To get an explicit bound for $t\in[0,1]$ we simplify the integral
    equation and obtain
    \begin{align}
      \label{eq:fleq2intg}
      \f[t]&\leq2\intf{p_{t}}{1}{g(x,t)}.
    \end{align}

    We know $\f[t]$ for $t<0$, and we can bound
    $g(x,t)$, if $x$ is bounded away from $p_{t}$. Hence we split
    the integral into a left part for which we already have a bound
    for $f_{X}$ and a right part, in which we can bound $g$. For any
    $\gamma\in (p_{t},1]$, we have
    \begin{align}
      \label{eq:fXt}
      \f[t]
      &\leq 2 \int_{p_{t}}^{\gamma}\!\!\!g(x,t)dx
      + 2\int_{\gamma}^{1}\!\!g(x,t)\f dx,
    \end{align}
    where in the second integral, we can use that $g$ is decreasing in
    $x$ for any fixed $t$ and bound $g(x,t)\leq g(\gamma,t)$.

    For $t<1/4$, we can use that $p_{t}$ is negative, and set
    $\gamma=0$. So the first integral vanishes and only the
    second remains and we obtain
    \begin{align}
      \f[t]&\leq2\intf{0}{1}{g(x,t)}
      \leq 2 \;g(0,t)\!\intf{0}{1}{}
      = \frac{1}{\sqrt{\tfrac14-t}}.\label{eq:fmaxleq14}
    \end{align}

    To go on, we set $\gamma=\gamma_{t}:=(p_{t}+t)/2$ and get with
    \eqref{eq:fXt}
    \begin{align*}
      \f[t]
      &\leq 2\;\mu_{t}\int_{p_{t}}^{\gamma_{t}}\!\!\!\!g(x,t)dx
      + 2\; g(\gamma_{t},t)\int_{\gamma_{t}}^{1}\!\!\!\f dx,
    \end{align*}
    where $\mu_{t}\ensuremath{\mathop{:}\!\!=}\sup\{\f[\tau]:\;\tau\in(p_{t},\gamma_{t})\}$.

    We can calculate the first integral using the integral of
    $g$ given in \eqref{eq:antiderivOfg},
    \begin{equation}
      \label{eq:defht}
      \int_{p_{t}}^{\gamma_{t}}\!\!\!\!g(x,t)dx
      =\ln\left(
        1+\frac{(1-\sqrt{t})^{2}+(1-\sqrt{t})\sqrt{1+6\sqrt{t}+t}}
        {4\sqrt{t}}
      \right)\ensuremath{=\!\!\mathop{:}} h(t),
    \end{equation}
    and for the second integral,
    we obtain
    \begin{equation*}
      \int_{\gamma_{t}}^{1}\f dx
      \leq \int_{p_{t}}^{1}\f dx
      = \Ws{X\geq1-2\!\left(1-\sqrt{t}\right)}.
    \end{equation*}

    Putting everything together we get
    \begin{align}
      \f[t]&\leq
      2\,\mu_{t}\,h(t)
      +4\;\frac{\Ws{X\geq1-2(1-\sqrt{t})}}
           {(1-\sqrt{t})\sqrt{1+6\sqrt{t}+t}}.
      \label{eq:fleqptgamma}
    \end{align}

    For $t=1/4$ we have $\gamma_{1/4}=1/8$,
    and $\mu_{1/4}\leq2\sqrt{2}$ by \eqref{eq:fmaxleq14}, so
    \begin{align}
      \f[1/4]
      \leq 4\sqrt{2}\;\ln\!\left(1+\frac{1+\sqrt{17}}{8}\right)
      +\frac{16}{\sqrt{17}}
      \leq7.\label{eq:f14leq}
    \end{align}
    From the integral equation we get for $0\leq s<t\leq1/4$
    \begin{align*}
      \f[t]-\f[s]
      =&\int_{0}^{1}\bigl(g(x,t)-g(x,s)\bigr)\f dx+\\
      &+\int_{0}^{s}\bigl(g(x,t)-g(x,s)\bigr)\f dx
      +\int_{s}^{t}g(x,t)\f dx\\
      >&\ 0,
    \end{align*}
    so $f$ is strictly increasing on $[0,1/4]$. Therefore, the
    bound for $t=1/4$ extends to all
    $t\in\left[0,1/4\right]\ensuremath{=\!\!\mathop{:}} I_{0}$.
    To go on, we recursively define $b_{0}\coleq0$ and
    \begin{displaymath}
      b_{i}\ensuremath{\mathop{:}\!\!=}\left(\frac{1+b_{i-1}}{2}\right)^{2},\quad i\geq1,
    \end{displaymath}
    and
    \begin{equation*}
      I_{2k-1}\ensuremath{\mathop{:}\!\!=}\left(b_{k},\frac{b_{k}+b_{k+1}}{2}\right],\quad
      I_{2k}\ensuremath{\mathop{:}\!\!=}\left(\frac{b_{k}+b_{k+1}}{2},b_{k+1}\right],\quad k\geq1.
    \end{equation*}
    For each interval $I_{n}$ we find a corresponding bound $M_{n}$
    for $f_{X}$, using that $p_{b_{i}}=b_{i-1}$ and therefore
    $(p_{t},\gamma_{t})\subset I_{n-1}\cup I_{n-2}\text{ for }t\in I_{n}$.

    Furthermore we get for $1/4\leq t\leq1$ by differentiating the
    function $h$ defined in \eqref{eq:defht}
    \begin{align*}
      h'(t)&= c_{t}\, \Biggl(
      \frac{d}{dt}\,\frac{(1-\sqrt{t})^{2}}{4\sqrt{t}}
      +\frac{d}{dt}\,\frac{(1-\sqrt{t})\sqrt{1+6\sqrt{t}+t}}{4\sqrt{t}}
      \Biggr) ,
    \end{align*}
    where $c_{t}\geq1$. But the first summand is negative and for the
    second observe that
    \begin{align*}
        \frac{d}{dt}\,
          (1-\sqrt{t})\sqrt{1+6\sqrt{t}+t}
      &=\frac{
        \left(1-\sqrt{t}\right)\left(3+\sqrt{t}\right)
        -\left(1+6\sqrt{t}+t\right)
      }{2\,\sqrt{t}\sqrt{1+6\sqrt{t}+t}}\\[1ex]
      &=\frac{1-4\sqrt{t}-t}{\sqrt{t}\sqrt{1+6\sqrt{t}+t}}\\
      &<0,
    \end{align*}
    hence $h(t)$ is decreasing.

    The second summand in \eqref{eq:fleqptgamma} can be bounded using
    Lemma~\ref{lm:Geps} with $\kappa=2$ yielding
    \begin{equation}
      4\;\frac{\Ws{X\geq1-2(1-\sqrt{t})}}{(1-\sqrt{t})
        \sqrt{1+6\sqrt{t}+t}}
      \leq 4\;\frac{\Ws{X\geq1-2\,(1-\sqrt{t})}}{2\,(1-\sqrt{t})}
      \leq 4\sqrt{2}.
    \end{equation}

    So for $t\in I_{n}=(\alpha_{n},\beta_{n}]$ we have
    \begin{equation}
      \label{eq:I1}
      f(t)\leq M_{n}:=
      \left\lceil
        2\,h(\alpha_{n})\,\max\{M_{n-1},M_{n-2}\}+4\sqrt{2}
      \right\rceil.
    \end{equation}
    Evaluating this we obtain
    \begin{align*}
      M_{0}=7,\
      M_{1}=13,\
      M_{2}=17,\
      M_{3}=18,\
      M_{4}=17.
    \end{align*}
    But for $t>b_{3}$ we have $h(t)<2/7$ so the sequence
    $\left(M_{n}\right)_{n\geq0}$ is decreasing for $n\geq4$.
  \end{proof}
\end{lm}

\begin{lm}\label{lm:fHoelder}
  Let $f_{X}$ be the density of $X$ as in Lemma~\ref{lm:intEqfX}. Then
  $f_{X}$ is H\"older continuous on $[0,1]$ with H\"older exponent
  $1/2$:
  \begin{equation}
    \label{eq:modcont}
    \abs{f_{X}(t)-f_{X}(s)\bigr.}\leq 9\norm[\infty]{\ff}\sqrt{t-s},
    \qquad\text{ for }0\leq s<t\leq1.
  \end{equation}
  \begin{proof}
    Using the integral equation given in Lemma~\ref{lm:intEqfX}, we
    have
    \begin{align}
      \abs{\f[t]-\f[s]\bigr.}
      &\leq 2\abs{\int_{p_{t}}^{t}\!\!g(x,t)\f dx
        - \int_{p_{s}}^{s}\!\!g(x,s)\f dx\,} +\nonumber \\[1ex]
      &\qquad\qquad + \abs{\int_{t}^{1}\!\!g(x,t)\f
        -\int_{s}^{1}\!\!g(x,s)\f dx}.
       \label{eq:modCont}
    \end{align}

    With explicit calculations we find
    \begin{displaymath}
      \abs{\intgf{p_{t}}{t}{t} - \intgf{p_{s}}{s}{s}}\leq 4\norm[\infty]{\ff}\sqrt{t-s}
    \end{displaymath}
    and
    \begin{displaymath}
       \abs{\intgf{t}1t -\intgf{s}1s}
       \leq \norm[\infty]{\ff}\sqrt{t-s}.
    \end{displaymath}
    For details see \citet{Kn06}.
  \end{proof}
\end{lm}

\begin{bem}\label{bem:notLipschitz}
  The latter lemma cannot be substantially improved, as in $t=1/4$, the
  density $\f[t]$ is not H\"older continuous with H\"older exponent
  $1/2+\epsilon$ for any $\epsilon>0$, see \citet{Kn06}.
\end{bem}

\section{Explicit error bounds for $\mathbf{X\ensuremath{\stackrel{d}{=}} UX+U(1-U)}$}

We can now combine the bounds for the density and
its modulus of continuity with
Lemma~\ref{lm:kolBound} and Lemma~\ref{lm:difffnf}
to bound the deviation of an approximation  from
the solution of the fixed-point equation.

To approximate the density $f_{X}$ we  set
\begin{equation*}
  f_{n}(x)\ensuremath{\mathop{:}\!\!=}
  \begin{cases}
    \f[0] & \text{for } 0\leq x\leq\delta_{n},\\[1ex]
    \dfrac{F_{n}(x+\delta_{n})-F_{n}(x-\delta_{n})}{2\delta_{n}}
    &\text{for } \delta_{n}<x\leq1,\\
        0 & \text{otherwise,}
  \end{cases}
\end{equation*}
where $\f[0]$ is given in Remark~\ref{bem:f0keyEx} and $F_{n}$ denotes
the distribution function of $X_{n}$.

For the values used for the plot in Figure~\ref{fig:histUX+U(1-U)},
i.e.~ $s(n)=n^{3}$ and $N=80$, we can apply Corollary \ref{cor:lpR} and
obtain:
\begin{cor}
  We have $\ensuremath{\rho}(\Xn[80],X)\leq1.162\cdot 10^{-4}$, and
  \mbox{$\norm[\infty]{f_{80}-f_{X}}\!\leq0.931$}. Furthermore, we can
  improve the bound of Lemma~\ref{lm:boundf} and bound
  $\norm[\infty]{f_{X}}\!\leq3.561$.
  \begin{proof}
    We have $C_{A}=C_{b}=C_{X}=1$, hence combining
    Lemma~\ref{lm:boundf} and Lemma~\ref{lm:kolBound}, we obtain
    \begin{align*}
      \ensuremath{\rho}(\Xn,X)&\leq \left(\!  \biggl(
        \ximax^{n}\norm[p]{X}
        +\left(2+\norm[p]{X}\right)\sum_{i=0}^{n-1}
        \frac{\ximax^{i}}{\left(n-i\right)^{r}} \biggr) \,
        \left(p+1\right)^{1/p}\, \norm[\infty]{f_{X}}
      \right)^{p/(p+1)}\hspace{-6.5ex}.
    \end{align*}
    The moments of $X$ can be computed using
    Lemma~\ref{lm:momBsp} and we set
    $[U]_{n}\ensuremath{\mathop{:}\!\!=}\flr{n^{3}U}/n^{3}$, hence
    \begin{equation*}
      \ximax = \norm[p]{U}=\left(\dfrac1{p+1}\right)^{1/p}.
    \end{equation*}

    Optimizing over $p$ for $n=80$, $r=3$, and
    $\norm[\infty]{f_{X}}\leq18$ yields
    \begin{equation}\label{eq:boundkol}
      \ensuremath{\rho}(\Xn[80],X)\leq5.1842\cdot10^{-4}
    \end{equation}
    for $p=12$.

    Using for $\f[0]$ the value given in Remark~\ref{bem:f0keyEx}, we
    obtain for the density
        \begin{align*}
      \norm[\infty]{f_{n}-f_{X}} &\leq \frac1{\delta_{n}}\ensuremath{\rho}(\Xn,X) +
      9\norm[\infty]{\ff}\sqrt{\delta_{n}},
    \end{align*}
    and optimizing over $\delta_{n}$, using for the Kolmogorov metric
    the bound in \eqref{eq:boundkol}, yields
    \begin{equation*}
      \norm[\infty]{f_{80}-f_{X}}\leq4.512
    \end{equation*}
    for $\delta_{80}=3.44\cdot10^{-4}$ (averaging $352$ values).

    We can now use this to improve our bound for $\norm[\infty]{f_{X}}$:
    Reading off the maximal value of our approximation %
    ($\norm[\infty]{f_{80}}\!\leq2.630$), we can now bound
    \begin{equation*}
      \norm[\infty]{f_{X}}
      \leq\norm[\infty]{f_{80}}+\norm[\infty]{f_{80}-f_{X}}
      \leq7.142,
    \end{equation*}
    and this in turn enables us to improve our bounds for the
    approximation, leading to
    \mbox{$\ensuremath{\rho}(X_{80},X)\leq2.2085\cdot10^{-4}$} and
    $\norm[\infty]{f_{80}-f_{X}}\leq1.8331$ for $\delta_{80}=3.6\cdot10^{-4}$.
    Repeating this strategy a few times, we get the stated values for
    $p=13$ and $\delta_{80}=3.7\cdot10^{-4}$ (averaging $378$ values).
  \end{proof}
\end{cor}

\begin{bem}
  Using the realistic (but yet unproven) bound of $\norm[\infty]{\ff}\leq2.7$ would
  give $\ensuremath{\rho}(\Xn[80],X)\leq8.9809\cdot10^{-5}$ ($p=13$) and
  $\norm[\infty]{f_{80}-f_{X}}\leq0.7101$. Hence, our approach works
  well for the distribution function. However, we cannot show
  strong error bounds for the approximation of densities
  with our arguments.
\end{bem}

However, in the next section we see that for another example the
algorithm approximates the densities much better than the error bounds
indicate.

In Table~\ref{tab:err}, the resulting error bounds for several
possible discretisations with similar running time can be found.

\begin{table}[!htb]
  \centering
  \begin{tabular}{|c|c||c|c||c|}
    \hline
    Discret.&$N$ &$\ensuremath{\rho}(\Xn[N],X)$&opt. $p$ &$\ensuremath{s}(N)$\\
    \hline\hline
    $n$& 22000& 0.00178& 14& 22000\\
    \hline
    $n^{2}$& 430 & 0.00025  & 16& 184900\\
    \hline
    $n^{3}$& 80 & 0.00012 & 13 & 512000\\
    \hline
    $n^{4}$& 30 & 0.00050 & 3 & 810000\\
    \hline\hline
    $1.5^{n}$ & 35 & 0.00070 & 3 & 1456110\\
    \hline
    $1.7^{n}$ & 27 & 0.00187 & 2 & 1667712\\
    \hline
  \end{tabular}
  \caption{Bounds for $\ensuremath{\rho}(\Xn,X)$ for comparable total running times
    (about 20h on a laptop computer each).
    The discretisations are  according to Corollaries \ref{cor:lpR} and
    \ref{cor:lpRgamman}. By $s(N)$ the number of atoms of the discrete
    approximation is denoted, cf.~Section~\ref{sec:complex}.}
  \label{tab:err}
\end{table}

\section{An experimental view on error bounds}
\label{sec:IntSplit}

We now apply our algorithm to another fixed-point equation for which the
solution is explicitly known. We can then compare the approximation of our
algorithm with the true density and distribution function and evaluate
the actual error to get an idea of the quality of the error bounds
proven in Section~\ref{sec:convRates}. Further examples can be found in
\citet{Kn06}. It appears that the error bounds in
Section~\ref{sec:convRates} are rather loose and that the
approximation is much better than indicated by our bounds.

In the analysis of certain random interval splitting procedures the
following fixed-point equation characterizes the distribution of a point
to which a random sequence of nested intervals shrinks:
\begin{equation*}
  X\ensuremath{\stackrel{d}{=}} \frac{1+U}2\,X + G\frac{1-U}2,
\end{equation*}
where $G$, $U$, and $X$ are independent, $G$ is $\DBern{1/2}$ distributed
and $U$ is uniformly distributed on $[0,1]$, see \citet*{ChenGooZam84},
\citet*{ChenLinZam81}, \citet*{DevLetSes86}, and \citet{Nein01} for
details of the interval splitting context.

To approximate the fixed-point, we use a symmetric discretisation for
$(A,b)$ instead of \eqref{eq:defU_n}, setting
\begin{equation
  \discrete{U}\ensuremath{\mathop{:}\!\!=}(2\flr{\ensuremath{s}(n) U}+1)/2\ensuremath{s}(n)
\end{equation}
and $\ensuremath{s}(n)=n^{3}$.

To compute the bounds as given in Section~\ref{sec:convRates}, we
can set $C_{A}=C_{b}=1/4$, $\ximax=\norm[p]{A}$, and
$A$ is uniformly distributed on $[1/2,1]$, so
\begin{align*}
    \norm[p]{A}^{p}=\frac{2^{p+1}-1}{2^{p}\,(p+1)}
    \quad \text{ for } p\in\ensuremath{\mathbb{N}}.
\end{align*}
It is known that $X$ is $\Dbeta{2}{2}$ distributed, so we have
the moments:
\begin{align*}
  \norm[p]{X}^{p}=\prod_{s=0}^{p-1}\frac{2+s}{4+s},
  \qquad p\in\ensuremath{\mathbb{N}}.
\end{align*}
Furthermore, $X$ has the density $\f=6\,x(1-x)$, so
$\norm[\infty]{f_{X}}\!=1.5$.  We can now use Lemma~\ref{lm:kolBound}
and Corollary~\ref{cor:lpR} to obtain \vspace{-1ex}
\begin{align*}
  \ensuremath{\rho}(\Xn[N],X) &\leq
  \left(
    1.5\,\left(p+1\right)^{1/p}
    \biggl(
      \norm[p]{A}^{N}\norm[p]{X}
      +\frac{5+\norm[p]{X}}{4}
        \sum_{i=0}^{N-1}\frac{\norm[p]{A}^{i}}{\left(N-i\right)^{3}}
    \biggr)
  \right)^{\tfrac{p}{p+1}}.
\end{align*}
For $N=50$ we minimize over $p$ and get
$p_{\min}=5$ and
\begin{equation}\label{eq:kolIntr1bound}
  \ensuremath{\rho}(\Xn[50],X)\leq0.001043.
\end{equation}

As we know the limit distribution, we can read off the true error from
the output of our simulation and find
\begin{displaymath}
  \ensuremath{\rho}(\Xn[50],X)\approx0.000012.
\end{displaymath}

It is quite exactly of the order expected for a discretisation
of step size $1/n^{3}$. Note that when approximating a differentiable
function by a step function, step size and derivative impose an
unavoidable error. Comparing our approximation to a direct
discretisation by a step function of the same step size, the deviation
is at most $1.5\cdot 10^{-8}$.

Now we look at the density.
The modulus of continuity of the density
of the $\Dbeta{2}{2}$ distribution can be bounded by
$\ensuremath{\Delta}_{f}(\epsilon)\leq6\,\epsilon$ for all positive $\epsilon$.
So for the function $f_{N}$, which we get by averaging over
$2\delta_{N}$ as in \eqref{eq:approxfn}, we get with
Lemma~\ref{lm:difffnf}
\begin{equation*
    \norm[\infty]{f_{N}-f_{X}\big.}
  \leq \frac1{\delta_{N}}\ensuremath{\rho}(\Xn[N],X) + 6\, \delta_{N}.
\end{equation*}
We evaluate for $N=50$, use the bound in
\eqref{eq:kolIntr1bound}, and minimizing over $\delta_{50}$ we obtain
\begin{equation*}
  \norm[\infty]{f_{50}-f_{X}\big.}\leq0.1583
\end{equation*}
for $\delta_{50}=0.01318$, so we take the average over $3\,296$ values.

Reading off the true error from the simulation we obtain
\begin{displaymath}
  \norm[\infty]{(f_{n}-f)\ensuremath{\mathbbm{1}}_{[0.015;0.985]}}\approx0.0003
\end{displaymath}
and $\abs{f_{n}(x)-f(x)}\leq0.02$ for $x<0.015$ or
$x>0.985$. The larger errors at the boundary are caused by the
averaging procedure used to obtain $f_{n}$.

{\bf Acknowledgements:} We thank the referee for careful reading,
pointing out some inacurracies and helping improve the presentation of
the paper.

redpajama_set_name: RedPajamaArXiv


Statehood quarter set of 200 BU and proofs. 50 silver proof quarters included.
The item "1999-2008 PDS & Silver Statehood Quarter set 200 Coins in 2 Littleton albums" is in sale since Wednesday, November 28, 2018. This item is in the category "Coins & Paper Money\Coins\ US\Quarters\State Quarters (1999-2008)". The seller is "bjstamps" and is located in Glendale, Arizona. This item can be shipped to United States, Canada, United Kingdom, Denmark, Romania, Slovakia, Bulgaria, Czech republic, Finland, Hungary, Latvia, Lithuania, Malta, Estonia, Australia, Greece, Portugal, Cyprus, Slovenia, Japan, Sweden, Indonesia, Thailand, Belgium, France, Hong Kong, Ireland, Netherlands, Poland, Spain, Italy, Germany, Austria, Bahamas, Singapore, Switzerland, Norway, Saudi arabia, United arab emirates, Qatar, Kuwait, Bahrain, Croatia, Malaysia, Brazil, Chile, Colombia, Viet nam, Uruguay, Taiwan, South africa, Israel, Mexico, New Zealand, Philippines, Ukraine, Bolivia, Ecuador, Egypt, Gibraltar, Cayman islands, Sri lanka, Peru, Pakistan, Paraguay.


When is good news also bad news?
Starting July 21, it will be easier for consumers to get a free credit score. Because of a new law, you may just get, in the mail, with no strings attached, your very own credit score. That's the good news.
But the bad news is that if you get that free credit score in the mail, it's because you've recently applied for credit and you've either been denied outright, or you didn't qualify for the terms you applied for.
But, hey, if it happens, at least you're better off than someone who tried to get a loan yesterday. Before that date, if you applied for, say, a low-interest credit card and were denied, or you attempted to get a loan at a bank, you may have been told that your credit wasn't good enough, but you were never given any solid, actionable information that might help you get what you wanted in the future.
However, because of the ever-helpful 2010 Dodd-Frank Wall Street Reform and Consumer Protection Act, that will change. You'll be able to see what your credit score was the moment you were considered for the loan or line of credit.
Then, if you choose, you can take steps to improve your credit and down the road, try again. Or you can drown your sorrows in a root beer, or possibly something stronger.
And actually, it's not just credit cards and banks that have to send consumers their free credit score. In some cases, enterprises like electric companies and insurance companies, if they turn down someone who wants to become a customer, they will also have to furnish it. And in some cases, they won't have to.
"The final rules are pretty complicated," says consumer credit guru John Ulzheimer.. "The easiest way to think about it is that any entity, whether a bank or insurance company, it doesn't matter, if they use a credit score to underwrite loans, the rules apply."
So while you have the right to know why you were turned down for a perk-filled rewards credit card, the same rules may not apply if you're turned down by another entity that requires regular payments.
It's more common than you might know, according to Ulzheimer, who says that a lot of utilities and insurance companies in particular have their own scoring models, and so if you do apply to rent an apartment or to get a major cable TV package and you're turned down, don't automatically assume you'll get a free credit score in the mail or that you'll fully understand why you were rejected.
But if you do, you won't just receive your credit score in what's called a risk-based pricing notice, you'll also receive information on what damaged your score, up to four or five reasons, in fact, as well as the date the score was created and which credit bureau issued the score. All of this may not keep you from opening the fridge and gulping down two or three root beer floats, but it's certainly helpful information.
Provided, adds Ulzheimer, that "you open the letters you get in the mail, which unfortunately is not something everyone does."
Darn. There's always a catch. Still, it's a helpful law, particularly with credit cards and for those consumers who want to always make sure they have the best credit card deals. If your credit card issuer, for instance, raises your interest rate due to your credit score dropping, they have to send you your credit score and let you know the reasons it plunged.
One has to think that will help a lot of consumers get back on track with their finances, and as more consumers apply for credit cards and take out loans, well, that should make the banking industry happy, too.


How I deal with a curious.
Today I want to talk about my middle child Luke. He just had a birthday on the 9th where he turned 7. This little boy has stolen my heart in so many ways. He keeps surprising me with just how smart he is and how much he loves to learn. He is so curious about the world around him. Heck, for his birthday I bought him a book. That's right, I bought my 7 year old a book for his birthday.
This is where Amazon has come to this mama's rescue. Because, honestly, can you tell me what the rings of Saturn are made of? We have been using Echo Dot Kids Edition from Amazon for the past couple of months and it has been such a blessing in our house. From dancing and storytelling for Ryan (my 4-year-old) to answering such questions that I know I do not have the answer too.
I love how the Echo Dot Kids Edition isn't just some random piece of technology in our house but something that I can use to help my children learn and have fun doing it.
I absolutely love it when I'm in my room and I hear one of the kids yelling "hey Alexa" from across my house. It brings a smile to my face every single time.
When you buy an Echo Dot Kids Edition it automatically comes with a whole year of FreeTime Unlimited, already has a kid-friendly case and has a 2 year worry free guarantee.
For those of you worried about not being able to control electronics, the Echo Dot Kids Edition also comes with a world-class parental control. This will let you be able to select which services and skills kids can use. You can turn off all voice purchasing, set a bedtime where your kids cannot sue the device at certain times and block all explicit song lyrics that Amazon Music can have.
FreeTime Unlimited on Alexa is also available on Echo devices, including Echo, Echo Plus and Echo Spot starting at $2.99 per month. And, families that already subscribe to FreeTime Unlimited on Fire tablets or Android devices can enjoy FreeTime Unlimited on Alexa content at no additional cost.
Now that all that fun is over, I have one more fun thing for you. Below is a giveaway where 10 winners will win 1 of 10 Echo Dot Kids Edition. I hope you all enjoy the Echo Dot Kids Edition just as much as I do and will continue. If you would rather not wait you can always buy your through this link HERE.


LOKMANYATILAK T LTT to PUNE JUNCTION PUNE train timings, routes, stops, and complete info.
As of now, 75 trains run between from LOKMANYATILAK T (PNVL) to PUNE JUNCTION (PUNE).
The fastest train from LOKMANYATILAK T (PNVL) to PUNE JUNCTION (PUNE) is INDRAYANI EXPRESS (22105) that departs at 06:35 and arrives to at 09:05. It takes approximately 02:30 hours.


Guy Locker (L), of SouthWest Water Company (SWWC), presents the SWWC scholarship to Aaron Wilkes (R), Pelham High School. Aaron will study chemical engineering at the University of Alabama.
The scholarship recipients are high school seniors who have been accepted to attend an accredited four-year college or university degree program with the intent to major in environmental science, environmental engineering or general engineering curriculum.
The recipients have demonstrated academic achievements during their high school careers and also have achieved an exemplary record of community service and participation in school extracurricular activities.
SouthWest Water Company Managing Director Craig Sorensen said that SouthWest Water Company feels the need to help upcoming leaders in this important field.
Craig Sorensen (L), Managing Director of SouthWest Water Company, presents the SWWC scholarship to Andrew Wallace (R), Briarwood Christian School. Andrew will study general engineering at the University of Alabama at Birmingham.
"As a company that is charged with protecting the world's most valuable resource, we feel responsible for encouraging the next generation of leaders in our field," Mr. Sorensen said.
The scholarship recipients, each of whom will receive a $1,000 cash scholarship, are Daniel Stanton, of Birmingham and Oak Mountain High School, who will study general engineering at the University of Michigan; Dorothy Plante, of Birmingham and Spain Park High School, who will study civil engineering at the University of Alabama at Birmingham; Andrew Wallace, of Hoover and Briarwood Christian School, who will study general engineering at the University of Alabama at Birmingham; and Aaron Wilkes of Pelham and Pelham High School, who will study chemical engineering at the University of Alabama.
SouthWest Water Company owns and operates water treatment and reclamation facilities throughout Shelby County.
Note: Dorothy Plante, of Spain Park High School, was not available for a photograph. Dorothy will study civil engineering at the University of Alabama at Birmingham.
Harry Chandler (L), of SouthWest Water Company (SWWC), presents the SWWC scholarship to Daniel Stanton (R), Oak Mountain High School. Daniel will study general engineering at the University of Michigan.


text:
from lino_xl.lib.tickets.models import *
from lino.api import _

Ticket.hide_elements('closed')

# class Ticket(Ticket):
#     class Meta(Ticket.Meta):
#         app_label = 'tickets'
#         abstract = dd.is_abstract_model(__name__, 'Ticket')

#     client = dd.ForeignKey('avanti.Client', blank=True, null=True)

dd.update_field(
    'tickets.Ticket', 'upgrade_notes', verbose_name=_("Solution"))

# dd.update_field(
#     'tickets.Ticket', 'state', default=TicketStates.todo.as_callable)

class TicketDetail(TicketDetail):
    main = "general #history_tab more"

    general = dd.Panel("""
    summary:40 end_user
    id:6 user:12
    workflow_buttons
    description
    """, label=_("General"))

    # history_tab = dd.Panel("""
    # changes.ChangesByMaster:50 #stars.StarsByController:20
    # """, label=_("History"), required_roles=dd.login_required(Triager))

    more = dd.Panel("""
    more1:60
    upgrade_notes:20
    """, label=_("More"), required_roles=dd.login_required(Triager))

    more1 = """
    created modified ticket_type:10
    deadline site
    state priority project
    # standby feedback closed
    """

Tickets.detail_layout = TicketDetail()

redpajama_set_name: RedPajamaGithub


text:
Q: Issue loading missing assemblies in Xamarin.Forms project I'm building a Xamarin.Forms project and I had no problems starting up the project but all of a sudden when trying building the project I get the following Exception:
Exception while loading assemblies: System.IO.FileNotFoundException:
Could not load assembly 'Windows.Foundation.FoundationContract,
Version=3.0.0.0, Culture=neutral, PublicKeyToken='. Perhaps it doesn't exist
in the Mono for Android profile Filename: 'Windows.Foundation.FoundationContract.dll'

I have looked for where in my project the Windows.Foundation namespace is used but I can only find references to it in the AppDelegate.cs and Main.cs of the iOS-project.

A: Apparantly the exception was a bit confusing because it was related to another assembly that was referenced. After I deleted that assembly, Windows.Foundation.FoundationUniversalContract, all worked fine.
When an how this reference was added is beyond me.

redpajama_set_name: RedPajamaStackExchange


text:
The Truman Show (Version française)
The film that made critics sit up and take notice of Jim Carrey's dramatic chops, the legendary funnyman is Truman Burbank in "The Truman Show," director Peter Weir's satirical look at a man raised from infancy to adulthood in front of television cameras. Unbeknownst to him, Carrey lives in a bubble where actors have played his family and cameras have followed his every move since the day he was born. When the seams in this make-believe world begin to split and he realizes his whole life is a lie, it leads to a breakdown - and a famous breakout. The 1998 film - Oscar-nominated for Best Screenplay, Director and Supporting Actor -co-stars Laura Linney and Ed Harris. . ...
Jim Carrey [Truman Burbank], Laura Linney [Meryl], Ed Harris [Christof ], Noah Emmerich [Marlon], Natascha McElhone [Lauren/Sylvia], Holland Taylor [Truman's Mother], Brian Delate [Truman's Father], Una Damon [Chloe], Paul Giamatti [Control Room Director], Philip Baker Hall [Network Executive]
Comédie, Drame

redpajama_set_name: RedPajamaCommonCrawl


text:
New 'Frozen 2' trailer: Anna and Elsa embark on journey into the enchanted forest
A new heart-stopping trailer for "Frozen 2" premiered this morning on "GMA."
ByAngeline Jane Bernabevia
1st look at the new 'Frozen 2' trailer
The new trailer shows Anna, Elsa and the rest of the gang going on a new adventure in the sequel.
"The kingdom is not safe."
A new heart-stopping trailer for "Frozen 2" premiered Monday morning on "Good Morning America," giving fans a new glimpse at what happens when a mystical force threatens the kingdom of Arendelle.
The new trailer, clocking in at 1 minute and 13 seconds, opens with young Anna and Elsa being told a story by their father about an enchanted forest where no one can go after something bad happened years ago.
ABCNews.com
VIDEO: 1st look at the new 'Frozen 2' trailer
Flash forward to life in Arendelle where things left off from the first film. Elsa is seen grappling with something and turns to her sister for comfort in a sweet moment in the trailer's opening montage. But things take a turn when Elsa mentions something about a voice calling her and the kingdom is seen being taken over by unexplainable forces of nature.
While many storylines are still a mystery, fans get a glimpse of adventure, mystery and an exciting look at Elsa's powers. They even get to see the whole "Frozen" crew embark on a journey to the enchanted forest.
Starbucks introduces a new fall drink. Will it be more popular than the Pumpkin Spice Latte?
How to achieve the ultimate K-beauty look in 7 simple steps
(MORE: The 'Frozen 2' teaser trailer is here and Twitter is losing its mind)
Will Anna, Elsa, Kristof, Sven and Olaf be safe on this new journey? And does the enchanted forest hold the key to restoring order in Arendelle?
The Academy Award-winning team of directors Jennifer Lee and Chris Buck are back for the sequel, and the animated film will feature the voices of Idina Menzel, Kristen Bell, Jonathan Groff and Josh Gad, all returning from the original.
The trailer introduced the a few new characters and voice cast members as well.
King Agnarr, the son of King Runeard, is Anna and Elsa's father, voiced by Alfred Molina.
Yelena, voiced by Martha Plimpton, is the fiercely protective leader of the nomadic Northuldra.
The poster for "Frozen 2."
Honeymaren, a brave member of the Northuldra, voiced by Rachel Matthews, is the free spirit of the bunch who wants to bring peace to the enchanted forest.
Honeymaren's brother Ryder, voiced by Jason Ritter, has never left the Enchanted Forest and longs to venture outside.
(MORE: 'Frozen' musical is about 'empowered women')
Bruni, a cute and curious salamander, lives in the Enchanted Forest and is drawn to Elsa's icy magic.
The sequel to the 2013 classic opens in theaters on Nov. 22.
Disney is the parent company of ABC News and "Good Morning America."


Our classic soap with coco butter. Super clean, soft and smooth. With out any scent, so moisturizing, Just Plain.
Leaves you clean and soft with out any itchy chemicals or scents.
A combination of olive oil, coconut oil, palm oil, sodium hydroxid (lye, neccesary for soap making.) coco butter and Vitamin E. No other additives A generous 4 oz. bar.


The Declaration of Independence doesn't mince words when it states that "all men are created equal." And yet the country's other foundational document – The Constitution – protected the most unequal of institutions in slavery. Harvard Law professor Annette Gordon-Reed joins us to talk about how America has struggled since its founding to reconcile these conflicting ideas. Her essay "America's Original Sin" appears in Foreign Affairs magazine.