Printer Friendly

A note on the approximation of perpetuities.

We propose and analyze an algorithm to approximate distribution functions and densities of perpetuities. Our algorithm refines an earlier approach based on iterating discretized versions of the fixed point equation that defines the perpetuity. We significantly reduce the complexity of the earlier algorithm. Also one particular perpetuity arising in the analysis of the selection algorithm Quickselect is studied in more detail. Our approach works well for distribution functions. For densities we have weaker error bounds although computer experiments indicate that densities can also be well approximated.

Contents
1 Introduction 115
2 The general approach and organization of the paper 116
3 Discrete approximation 118
4 Convergence of the discrete approximations 118
5 Algorithm and Complexity 120
6 A simple class of perpetuities 122
7 Example: Number of key exchanges in Quickselect 123


1 Introduction

A perpetuity is a random variable X in R that satisfies the stochastic fixed-point equation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1)

where the symbol [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] denotes that left and right hand side in (1) 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.

The term perpetuity originated in the context of insurance and financial mathematics, where X represents the value of a commitment to make regular payments, b representing the payment and A a discount factor both being subject to random fluctuation; see, e.g. Goldie and Maller (2000) or Embrechts, Kluppelberg, and Mikosch (1997, Section 8.4). However, perpetuities arise in various different contexts: In discrete mathematics, they 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 Arratia, Barbour, and Tavare (2003) for perpetuities, GEM and Poisson-Dirichlet distribution in the context of combinatorial structures; see Donnelly and Grimmett (1993) 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. Hwang and Tsai (2002) or Mahmoud, Modarres, and Smythe (1995).

As perpetuities are given implicitly by their fixed-point characterization (1), 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 (1) to uniquely determine a probability distribution are discussed in Vervaat (1979) and Goldie and Maller (2000). The types of distributions possible for perpetuities have been identified in Alsmeyer, Iksanov, and Rdsler (2007). Tail behavior of perpetuities has been studied for certain cases in Goldie and Grubel (1996).

In the present extended abstract, 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 an approach proposed in Devroye and Neininger (2002) that was originally designed for random variables X satisfying distributional fixed-point equations of the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (2)

where [X.sup.(1)], ..., [X.sup.(K)], ([A.sub.1],, ..., [A.sub.K], b) are independent with [X.sup.(r)] being identically distributed as X for r = 1, ..., K and random coefficients [A.sub.1], ..., [A.sub.K], b, and K [greater than or equal to] 2.

The case of perpetuities, i. e. K = 1, structurally differs from the cases K [greater than or equal to] 2: The presence of more than one independent copy of X on the right hand side in (2) often has a smoothing effect so that under mild additional assumptions on ([A.sub.1], ..., [A.sub.K], b) the existence of smooth Lebesgue densities of X follows, see Fill and Janson (2000) and Devroye and Neininger (2002). On the other hand, the case K = 1 often leads to distributions L(X) that have no smooth Lebesgue density; an example is discussed in Section 7.

2 The general approach and organization of the paper

A random variable X satisfies the distributional identity (1) if and only if its distribution is a fixed-point of the map T on the space .M of probability distributions, given by

T : M [right arrow] M, [micro] [right arrow] L(AY + b), (3)

where Y is independent of (A, b), and L(Y) = [micro]. Under the conditions [[parallel] A [parallel].sub.p] < 1 and [[parallel] b [parallel].sub.p] < [infinity] for some p [greater than or equal to] 1, which we assume throughout the paper, this map is a contraction on certain complete metric subspaces of M. Hence, L(X) can be obtained as limit of iterations of T, starting with some distribution [[micro].sub.0].

However, it is not generally possible to algorithmically compute the iterations of T exactly. We therefore use discrete approximations ([A.sup.(n)], [b.sup.(n)]) of (A, b), which become more accurate for increasing n, to approximate T by a mapping [T.sup.(n)], defined by

[T.sup.(n)] : M [right arrow] M, [micro] [right arrow] L([A.sup.(n) Y + [b.sup.(n)]),

where again Y is independent of ([A.sup.(n)], [b.sup.(n)]) and L(Y) = [micro].

To allow for an efficient computation of the approximation, we impose a further discretization step [<*>.sub.n], explained in more detail below, defining

[T.sup.(n)] : M [right arrow] M, [micro] [right arrow] L([<[A.sup.(n)] Y + [b.sup.(n)]>.sub.n]),

where Y is independent of ([A.sup.(n)], [b.sup.(n)]) and L(Y) = [micro].

In Section 3, we give conditions for [T.sup.(n)] o [T.sup.(n-1)] o ... o [T.sup.(1)] ([[micro].sub.0]) to converge to the perpetuity given as the solution of (1). To this aim, we derive a rate of convergence in the minimal [L.sub.p] metric [l.sub.p], defined on the space [M.sub.p] of probability measures on R with finite absolute p-th moment by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (4)

where [[parallel]*[parallel].sub.p] denotes the [L.sub.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 [rho], defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where [F.sub.v], [F.sub.[micro]] denote the distribution functions of v, [micro] [member of] [M.sub.p]. This implies explicit rates of convergence for distribution function and density, depending on the corresponding moduli of continuity of the fixedpoint.

For these moduli of continuity we find global bounds for perpetuities with b [equivalent to] 1 in Section 6. For cases with random b, these moduli of continuity have to be derived individually. One example, related to the selection algorithm Quickselect, is worked out in detail in Section 7.

We analyze the complexity of our approach in Section 5. As a measure for the complexity of the approximation, we use the number of steps needed to obtain an accuracy of order O(1/n). Although we generally follow the approach in Devroye and Neininger (2002), we can improve the complexity significantly by using different discretizations. For the approximation of the distribution function to an accuracy of O(1/n) in a typical case, we obtain a complexity of O([n.sup.1 + [epsilon]]) for any [epsilon] > 0. In comparison, the algorithm described in Devroye and Neininger (2002), which originally was designed for fixed-point equations of type (2) with K [greater than or equal to] 2, would lead to a complexity of O([n.sup.4 + [epsilon]]), if applied to our cases. For the approximation of the density to an accuracy of order O(1/n), we obtain a complexity of O([n.sup.1 + 1/[alpha] + [epsilon]]) for any [epsilon] > 0 in the case of a-Hdlder continuous densities, cf. Corollary 5.2.

Proofs are omitted throughout this extended abstract and can be found in Knape (2006).

3 Discrete approximation

Recall that our basic assumption in equation (1) is that [[parallel] A [parallel]].sub.p] < 1 and [[parallel] b [parallel]].sub.p] < [infinity] for some p [greater than or equal to] 1. To obtain an algorithmically computable approximation of the solution of the fixed-point equation (1), we use an approximation of the sequence defined as follows: We replace (A, b) by a sequence of independent discrete approximations ([A.sup.(n)], [b.sup.(n)]), converging to (A, b) in p-th mean for n [right arrow] [infinity]. To reduce the complexity, we introduce a further discretization step [<*>.sub.n], which reduces the number of values attained by [X.sub.n]:

[X.sub.n] := [A.sup.(n)] [X.sub.n - 1] + [b.sup.(n)], [X.sub.n] := [<[X.sub.n]>.sub.n]. (5)

In Section 5, explicit discretizations are given, but here we only assume that the discretizations [A.sup.(n)], [b.sup.(n)] and [<*>.sub.n] satisfy

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

for some error functions [R.sub.A], [R.sub.b] and [R.sub.X], which we specify later.

Furthermore, we assume that there exists some [[xi].sub.p] < 1, such that for all n [greater than or equal to] 1,

[[parallel][A.sup.(n)][parallel]].sub.p] [less than or equal to] [[xi].sub/p] (7)

which in applications is easy to obtain under [[parallel] A [parallel]].sub. p] < 1 and (6).

4 Convergence of the discrete approximations

By arguments similar to those used in Fill and Janson (2002) and Devroye and Neininger (2002) we obtain the following rates for the convergence of the approximations [X.sub.n] towards the fixed-point X. We use the shorthand notation [l.sub.p](X,Y) := [l.sub.p](L(X), L(Y)).

Lemma 4.1 Let ([X.sub.n]) be defined by (5) and [[xi].sub.p] as in (7). Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (8)

where R (n) := [R.sub.X](n) + [R.sub.A] (n) [[parallel] X [parallel]].sub.p] + [R.sub.b](n) for the errorfunctions in (6).

To make these estimates explicit we have to specify functions that bound [R.sub.A](n), Rb(n), and [R.sub.X](n). We do so in two different ways, one representing a polynomial discretization of the corresponding random variables and one representing an exponential discretization. Better asymptotic results are obtained by the latter one.

Corollary 4.2 Let ([X.sub.n]) be defined by (5) and [[xi].sub.p] as in (7), and assume

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

for some r [greater than or equal to] 1. Then, we have

[l.sub.p]([X.sub.n], X) [less than or equal to] [C.sub.r] 1/[n.sub.r],

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (9)

Remark 4.3 In Corollary 4.2, we are merely interested in the order of magnitude of [l.sub.p]([X.sub.n], X) without a sharp estimate of the constant [C.sub.r], When evaluating the error in an explicit example, we directly use, cf. Lemma 4.1,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (10)

to obtain sharper estimates.

Corollary 4.4 Let ([X.sub.n]) be defined by (5) and [[xi].sub.p] as in (7), and assume

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.],

for some 1 < [gamma] < 1/[[xi].sub.p]. Then, we have

[l.sub.p]([X.sub.n], X] [less than or equal to] [C.sub.[gamma]] 1/[[gamma].sup.n],

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (11)

Lemma 4.5 Let [X.sub.n] and Cr be as in Corollary 4.2 and X have a bounded density [f.sub.X]. Then, the distance in the Kolmogorov metric can be bounded by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Similarly, for [X.sub.n] and [C.sub.[gamma]] as in Corollary 4.4, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Remark 4.6 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 polynomial bound for the modulus of continuity of the distribution function [F.sub.X] of X, cf. Knape (2006).

To approximate the density of the fixed-point, we define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (12)

where [F.sub.n] is the distribution function of [X.sub.n]. 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

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Lemma 4.7 Let X have a density [f.sub.X] with modulus of continuity [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and let ([X.sub.n]) be defined by (5). Then, for [f.sub.n] defined by (12) and all [[delta].sub.n] > 0,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Corollary 4.8 Let X have a bounded density [f.sub.X], which is Holder continuous with exponent [alpha] [member of] (0,1]. For polynomial discretization, i. e. [X.sub.n], and [C.sub.r] as in Corollary 4.2, and [f.sub.n] defined by (12) with

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

with are L > 0, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

For exponential discretization, i. e. [X.sub.n], and [C.sub.[gamma]] as in Corollary 4.4, and [f.sub.n] defined by (12) with

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

with are L > 0, we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Remark 4.9 If X is bounded and bounds for the density fx and its modulus of continuity are known explicitly, the last result is strong enough to allow, in principle, perfect simulation using von Neumann's rejection method; see Devroye (2001) for the case of infinitely divisible perpetuities with approximation of densities by Fourier inversion, Devroye, Fill, and Neininger (2000) for the case of the Quicksort limit distribution and Devroye and Neininger (2002) for more general fixed-point equations of type (2).

5 Algorithm and Complexity

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] [right arrow] R, such that

A = [phi](U) and b = [psi](U), (13)

where U is uniformly distributed on [0, 1]. Furthermore, we assume that [[parallel][phi][parallel]].sub.[infinity]] [less than or equal to] 1 and that both functions are Lipschitz continuous and can be evaluated in constant time. Now we define the discretization [<*>.sub.n] by

[<Y>.sub.n] := [s(n) Y] / s(n), (14)

where s (n) can be either polynomial, i. e. s(n) = [n.sup.r] or exponential, s (n) = [[gamma].sup.n]. Defining

[A.sup.(n)] := [phi]([<U>.sub.n]) and

[b.sup.(n)] := [psi]([<U>.sub.n]),

the conditions on [phi] and [psi] ensure that Corollary 4.2 and 4.4 can be applied.

We keep the distribution of [X.sub.n] in an array [A.sub.n], where [A.sub.n] [k] := P[[X.sub.n] = k/s(n)] for k [member of] Z. Note however, that as A and b are bounded, [A.sub.n] [k] = 0 at least for |k| > [Q.sub.n], where [Q.sub.n] can be computed recursively as [Q.sub.n] = [[parallel]A[parallel]].sub.[infinity]] [Q.sub.n - 1] + [[parallel]b[parallel]].sub.[infinity]] and [Q.sub.0] = [[parallel][X.sub.0][parallel]].sub.[infinity]] = E[X]. The core of the implementation is the following update procedure:

procedure UPDATE ([A.sub.n-1], [A.sub.n])

for i [left arrow] 0 to s(n) - 1 do

for j [left arrow] - s(n - 1) [Q.sub.n - 1] to s(n - 1) [Q.sub.n - 1] - 1 do

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

end for

end for

end procedure

The complete code for polynomial discretization for the example in Section 7, implemented in C++, can be found in Knape (2006).

To approximate the density as in (12) with [[delta].sub.n] = d/s (n) for some d [member of] N, we compute a new array [D.sub.n] by setting

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

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 O(1/n). For the case that X has a bounded density fx which is Hdlder continuous, we give asymptotic bounds for polynomial as well as for exponential discretization. We assume the general condition (13).

Lemma 5.1 Assume that X has a bounded density [f.sub.X], which is Holder continuous with exponent [alpha] [member of] (0, 1]. Using polynomial discretization with exponent r, cf. Corollary 4.2, we can approximate the distribution function of X to are accuracy of O(1/n) in time O([n.sup.(2 + 2/r)(p + 1)/p]) and the density [f.sub.X] to the same accuracy in time O([n.sup.2(1 + 1/a)(r + 1)(p + 1)/(rp)]).

Using exponential discretization with parameter [gamma] as in Corollary 4.4, approximation to the same accuracy takes time O([n.sup.(p + 1)/p] log n) for the distribution function of X. The density can be approximated to the same accuracy in time O([n.sup.(1 + 1/[alpha])(p + 1)/p log n).

Corollary 5.2 Assume that X has a bounded density [f.sub.X], which is Holder continuous with exponent [alpha] [member of] (0,1]. Then, using exponential discretization as in Corollary 4.4, approximation to an accuracy of O(1/n) takes time O([n.sup.1 + [epsilon]]) for the distribution function and time O([n.sup.1 + 1/[alpha] + [epsilon]]) for the density of X for all [epsilon] > 0.

6 A simple class of perpetuities

In order to make the bounds of Section 4 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 7.

For fixed-point equations of the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (15)

where A and X are independent, we can bound the density and modulus of continuity of X using the corresponding values of A.

Lemma 6.1 Let X satisfy fixed-point equation (15) and A have a density [f.sub.A]. Then X has a density [f.sub.X] satisfying

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (16)

and [f.sub.X] (u) = 0 otherwise.

Corollary 6.2 Let A have a bounded density [f.sub.A]. Then X has a density [f.sub.X] satisfying

[[parallel][f.sub.X][parallel]].sub.[infinity]] [less than or equal to] [[parallel][f.sub.A][parallel]].sub.[infinity]].

Corollary 6.3 Let A have a density [f.sub.A], and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] be its modulus of continuity. Then the modulus of continuity [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] of [f.sub.X] satisfies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

This result is only useful if the density of A is continuous, but we can extend it to many practical examples, where [f.sub.A] has jumps at points in a countable set [I.sub.A]. We use the jump function of [f.sub.A], defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and a modification of [f.sub.A] where we remove all jumps,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Since X [greater than or equal to] 1, we now denote by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] the modulus of continuity of the restriction of [f.sub.X] to (1, [infinity]).

Lemma 6.4 Let A have a bounded cadlag density [f.sub.A]. Then, for all [delta] > 0,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

7 Example: Number of key exchanges in Quickselect

In this section, we apply our algorithm to the fixed-point equation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (17)

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 ex changes executed by Quickselect when acting on a random equiprobable permutation of length n and selecting an element of rank 1 = o(n) can be characterized by the above fixed-point equation, see Hwang and Tsai (2002).

We use our algorithm to get a discrete approximation of the fixed point. The plot of a histogram, generated with n = 80, r = 3, can be found in Figure 1.

[FIGURE 1 OMITTED]

In the following, we specify how the bounds in Section 4 can be made explicit for this example. Lemma 7.1 Let X be a solution of (17). Then, we have 0 [less than or eqaul to] X [less than or equal to] 1 almost surely, and the moments are recursively given by E [[X.sup.0]] = 1 and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

in particular, E[X] = 1/3.

Lemma 7.2 Let X be a solution of (17). Then, for all [kappa] [member of] N and [epsilon] > 0,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Lemma 7.3 Let X be a solution of (17). Then X has a Lebesgue density f satisfying f (t) = 0 for t < 0 or t > 1 and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (18)

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Remark 7.4 For t = 0, equation (18) implies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

In order to use Lemma 4.5 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 will see later, that we can use the resulting bound for our approximation to improve it.

Lemma 7.5 Let f be the density of X as in Lemma 7.3. Then

[[parallel] f [parallel]].sub.[infinity]] [less than or equal to] 18.

Lemma 7.6 Let f be the density of X as in Lemma 7.3. Then f is Holder continuous on [0,1] with Holder exponent 1/2:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (19)

Remark 7.7 The latter Lemma cannot be substantially improved, as in t = 1/4, the density f (t) is not Holder continuous with Holder exponent 1/2 + [member of] for any [member of] > 0.

Explicit error bounds

We can now combine the bounds for the density and its modulus of continuity with Lemma 4.5 and Lemma 4.7 to bound the deviation of an approximation from the solution of the fixed-point equation.

To approximate the density f we set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

otherwise,

where [F.sub.n] is the distribution function of [X.sub.n] and f (0) is given in Remark 7.4.

With r = 3, cf. Corollary 4.2, and n = 80 we obtain:

Corollary 7.8 We have [rho]([X.sub.80], X) [less than or equal to] 1.162 * [1.sup.-4], and < 0.931. Furthermore, we can improve the bound of Lemma 7.5 and get [[parallel]f[parallel]].sub.infinity] < 3.561.

Remark 7.9 Using the realistic (but yet unproven) bound of [[parallel]f[parallel]].sub.infinity] < 2.7 we would obtain [rho]([X.sub.80], X) [less than or equal to] 8.9809 * [10.sup.-5] (p = 13) and [[parallel][f.sub.80] - f[parallel]].sub.infinity] [less than or eqaul to] 0.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.

In Table 1, the resulting error bounds for several possible discretizations with similar running time can be found.

In Knape (2006, Section 4), the algorithm is applied to several other fixed-point equations for which the solutions are more or less explicitly known and the actual error can be evaluated. It appears that the error bounds in Section 4 are rather loose and that the approximation is much better than indicated by our bounds.

received 17th February 2007, revised 23rd January 2008, accepted.

References

G. Alsmeyer, A. Iksanov, and U. Rdsler. On distributional properties of perpetuities. Preprint, 2007.

R. Arratia, A. D. Barbour, and S. Tavar6. Logarithmic combinatorial structures: a probabilistic approach. EMS Monographs in Mathematics. European Mathematical Society (EMS), Zurich, 2003.

L. Devroye. Simulating perpetuities. Methodol.Comp. Appl. Probab., 3:97-115, 2001.

L. Devroye and R. Neininger. Density approximation and exact simulation of random variables that are solutions of fixed-point equations. Adv. Appl. Prob., 34:441-468, 2002.

L. Devroye, J. A. Fill, and R. Neininger. Perfect simulation from the Quicksort limit distribution. Elect. Comm. in Probab., 5:95-99, 2000.

P. Donnelly and G. Grimmett. On the asymptotic distribution of large prime factors. J. London Math. Soc., 47:395-404, 1993.

P. Embrechts, C. K16ppelberg, and T. Mikosch. Modelling extremal events. For insurance and finance. Number 33 in Applications of Mathematics (New York), 33. Springer-Verlag, Berlin, 1997.

J. A. Fill and S. Janson. Smoothness and decay properties of the limiting Quicksort density function. In Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities (Versailles, 2000), pages 53-64. Birkhduser Verlag, 2000.

J. A. Fill and S. Janson. Quicksort asymptotics. J. Algorithms, 44:4-28, 2002.

C. Goldie and R. Grubel. Perpetuities with thin tails. Adv. Appl. Probab., 28:463-480, 1996.

C. Goldie and R. Maller. Stability of perpetuities. Ann. Probab., 28:1195-1218, 2000.

H.-K. Hwang and T.-H. Tsai. Quickselect and the Dickman function. Comb. Probab. Comput., 11:353371,2002.

M. Knape. Approximating perpetuities. Diploma thesis, J.W. Goethe-Universitat Frankfurt a.M., 2006. URL http://publikationen.ub.uni-frankfurt.de/volltexte/2007/3859/.

H. Mahmoud, R. Modarres, and R. Smythe. Analysis of QUICKSELECT: an algorithm for order statistics. RAIRO Inform. Theor Appl., 29:255-276,1995.

W. Vervaat. On a stochastic difference equation and a representation of non-negative infinitely divisible random variables. Adv. Appl. Prob., 11:750-783, 1979.

([dagger]) Supported by an Emmy Noether Fellowship of the Deutsche Forschungsgemeinschaft.

Margarete Knape and Ralph Neininger ([dagger])

Department for Mathematics and Computer Science, J.W. Goethe-University Frankfurt, 60054 Frankfurt a. M., Germany
Tab. 1: Bounds for [rho]([X.sub.n], X) for comparable total running
times. The discretizations are according to Corollaries 4.2 and 4.4,
and s(N) denotes the number of atoms of the discrete approximation.

Discret. N [rho][(X.sub.N], X) opt. p s(N)

n 22000 0.00178 14 22000
[n.sup.2] 430 0.00025 16 184900
[n.sup.3] 80 0.00012 13 512000
[n.sup.4] 30 0.00050 3 810000

[1.5.sup.n] 35 0.00070 3 1456110
[1.7.sup.n] 27 0.00187 2 1667712
COPYRIGHT 2007 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2007 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Knape, Margarete; Neininger, Ralph
Publication:DMTCS Proceedings
Date:Jan 1, 2007
Words:4487
Previous Article:Expected number of locally maximal solutions for random Boolean CSPs.
Next Article:HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm.

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters