The Pointwise Densities of the Cantor Measure

Let be the classical middle-third Cantor set and let μ be the Cantor measure. Set s = log 2/log 3. We will determine by an explicit formula for every point x the upper and lower s-densities Θ*^s(μ , x), Θ*^s(μ , x) of the Cantor measure at the point x, in terms of the 3-adic expansion of x. We show that there exists a countable set F such that 9(Θ*^s(μ , x))^{− 1/s} + (Θ*^s(μ , x))^{− 1/s} = 16 holds for x \F. Furthermore, for μ_C almost all x, Θ*^s(μ , X) − 2 · 4^{− s} and Θ*^s(μ , x) = 4^{− s}. As an application, we will show that the s-dimensional packing measure of the middle-third Cantor set is 4^s.     

On the approximate behavior of the posterior distribution for an extreme multivariate observation

The behavior of the posterior for a large observation is considered. Two basic situations are discussed; location vectors and natural parameters.Let X = (X₁, X₂, …, X_n) be an observation from a multivariate exponential distribution with that natural parameter Θ = (Θ₁, Θ₂, …, Θ_n). Let θ_x^* be the posterior mode. Sufficient conditions are presented for the distribution of Θ − θ_x^* given X = x to converge to a multivariate normal with mean vector 0 as |x| tends to infinity. These same conditions imply that E(Θ | X = x) − θ_x^* converges to the zero vector as |x| tends to infinity.The posterior for an observation X = (X₁, X₂, …, X_n is considered for a location vector Θ = (Θ₁, Θ₂, …, Θ_n) as x gets large along a path, γ, in Rⁿ. Sufficient conditions are given for the distribution of γ(t) − Θ given X = γ(t) to converge in law as t → ∞. Slightly stronger conditions ensure that γ(t) − E(Θ | X = γ(t)) converges to the mean of the limiting distribution.These basic results about the posterior mean are extended to cover other estimators. Loss functions which are convex functions of absolute error are considered. Let δ be a Bayes estimator for a loss function of this type. Generally, if the distribution of Θ − E(Θ | X = γ(t)) given X = γ(t) converges in law to a symmetric distribution as t → ∞, it is shown that δ(γ(t)) − E(Θ | X = γ(t)) → 0 as t → ∞.     

Stochastic convergence of weighted sums in normed linear spaces

Let X be a (real) separable Banach space, let {V_k} be a sequence of random elements in X, and let {a_nk} be a double array of real numbers such that lim_n→∞ a_nk = 0 for all k and Σ^∞_k=1 |a_nk| ≤ 1 for all n. Define S_n = Σⁿ_k=1 a_nk(V_k − EV_k). The convergence of {S_n} to zero in probability is proved under conditions on the coordinates of a Schauder basis or on the dual space of X and conditions on the distributions of {V_k}. Convergence with probability one for {S_n} is proved for separable normed linear spaces which satisfy Beck's convexity condition with additional restrictions on {a_nk} but without distribution conditions for the random elements {V_k}. Finally, examples of arrays {a_nk}, spaces, and applications of these results are considered.     

Tests for the mean direction of the Langevin distribution with large concentration parameter

In this paper we study the asymptotic behaviors of the likelihood ratio criterion (T_L^(s)), Watson statistic (T_W^(s)) and Rao statistic (T_R^(s)) for testing H_0s: μ (a given subspace) against H_1s: μ , based on a sample of size n from a p-variate Langevin distribution M_p(μ, κ) when κ is large. For the case when κ is known, asymptotic expansions of the null and nonnull distributions of these statistics are obtained. It is shown that the powers of these statistics are coincident up to the order κ⁻¹. For the case when κ is unknown, it is shown that T_R^(s) T_L^(s) T_W^(s) in their powers up to the order κ⁻¹.     

Onk-sets in arrangements of curves and surfaces

We extend the notion ofk-sets and (≤k)-sets (see [3], [12], and [19]) to arrangements of curves and surfaces. In the case of curves in the plane, we assume that each curve is simple and separates the plane. Ak-point is an intersection point of a pair of the curves which is covered by exactlyk interiors of (or half-planes bounded by) other curves; thek-set is the set of allk-points in such an arrangement, and the (≤k)-set is the union of allj-sets, forj≤k. Adapting the probabilistic analysis technique of Clarkson and Shor [13], we obtain bounds that relate the maximum size of the (≤k)-set to the maximum size of a 0-set of a sample of the curves. Using known bounds on the size of such 0-sets we obtain asympotically tight bounds for the maximum size of the (≤k)-set in the following special cases: (i) If each pair of curves intersect at most twice, the maximum size is Θ(nkα(nk)). (ii) If the curves are unbounded arcs and each pair of them intersect at most three times, then the maximum size is Θ(nkα(n/k)). (iii) If the curves arex-monotone arcs and each pair of them intersect in at most some fixed numbers of points, then the maximum size of the (≤k)-set is Θ(k ²λ _s (nk)), where λ _s (m) is the maximum length of (m,s)-Davenport-Schinzel sequences. We also obtain generalizations of these results to certain classes of surfaces in three and higher dimensions. Finally, we present various applications of these results to arrangements of segments and curves, high-order Voronoi diagrams, partial stabbing of disjoint convex sets in the plane, and more. An interesting application yields andO(n logn) bound on the expected number of vertically visible features in an arrangement ofn horizontal discs when they are stacked on top of each other in random order. This in turn leads to an efficient randomized preprocessing ofn discs in the plane so as to allow fast stabbing queries, in which we want to report all discs containing a query point. Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the NCRD—the Israeli National Council for Research and Development-and the Fund for Basic Research in Electronics, Computers and Communication, administered by the Israeli Academy of Sciences.     

Triply-Logarithmic Parallel Upper and Lower Bounds for Minimum and Range Minima over Small Domains

We consider the problem of computing the minimum ofnvalues, and several well-known generalizations [prefix minima, range minima, and all nearest smaller values (ANSV)] for input elements drawn from the integer domain [1···s], wheres ≥ n. In this article we give simple and efficient algorithms for all of the preceding problems. These algorithms all takeO(log log log s) time using an optimal number of processors andO(ns^ε) space (for constant ε < 1) on the COMMON CRCW PRAM. The best known upper bounds for the range minima and ANSV problems were previouslyO(log log n) (using algorithms for unbounded domains). For the prefix minima and for the minimum problems, the improvement is with regard to the model of computation. We also prove a lower bound of Ω(log log n) for domain sizes = 2^{Ω(log n log log n)}. Since, forsat the lower end of this range, log log n = Ω(log log log s), this demonstrates that any algorithm running ino(log log log s) time must restrict the range ofson which it works.     

Permutation graphs, fast forward permutations, and sampling the cycle structure of a permutation

PS_N is a fast forward permutation if for each m the computational complexity of evaluating P^m(x) is small independently of m and x. Naor and Reingold constructed fast forward pseudorandom cycluses and involutions. By studying the evolution of permutation graphs, we prove that the number of queries needed to distinguish a random cyclus from a random permutation in S_N is Θ(N) if one does not use queries of the form P^m(x), but is only Θ(1) if one is allowed to make such queries. We construct fast forward permutations which are indistinguishable from random permutations even when queries of the form P^m(x) are allowed. This is done by introducing an efficient method to sample the cycle structure of a random permutation, which in turn solves an open problem of Naor and Reingold.     

Character sets of strings

Given a string S over a finite alphabet Σ, the character set (also called the fingerprint) of a substring S^′ of S is the subset CΣ of the symbols occurring in S^′. The study of the character sets of all the substrings of a given string (or a given collection of strings) appears in several domains such as rule induction for natural language processing or comparative genomics. Several computational problems concerning the character sets of a string arise from these applications, especially:

(1) Output all the maximal locations of substrings having a given character set.

(2) Output for each character set C occurring in a given string (or a given collection of strings) all the maximal locations of C.

Denoting by n the total length of the considered string or collection of strings, we solve the first problem in Θ(n) time using Θ(n) space. We present two algorithms solving the second problem. The first one runs in Θ(n²) time using Θ(n) space. The second algorithm has Θ(n|Σ|log|Σ|) time and Θ(n) space complexity and is an adaptation of an algorithm by Amir et al. [A. Amir, A. Apostolico, G.M. Landau, G. Satta, Efficient text fingerprinting via Parikh mapping, J. Discrete Algorithms 26 (2003) 1–13].     

On-line algorithms for networks of temporal constraints

We consider a semi-dynamic setting for the Temporal Constraint Satisfaction Problem (TCSP), where we are requested to maintain the path-consistency of a network under a sequence of insertions of new (further) constraints between pairs of variables. We show how to maintain the path-consistency in O(nR³) amortized time on a sequence of Θ(n²) insertions, where n is the number of vertices of the network and R is its range, defined as the maximum size of the minimum interval containing all the intervals of a single constraint.Furthermore we extend our algorithms to deal with more general temporal networks where variables can be points and/or intervals and constraints can also be defined on pairs of different kinds of variables. For such cases our algorithms maintain their performance. Finally, we adapt our algorithms to also maintain the arc-consistency of such generalized networks in O(R) amortized time for Θ(n²) insertions.     

Algebraic Approaches to Periodic Arithmetical Maps

A residue class a + n with weight λ is denoted by λ, a, n. For a finite system = {λ_s, a_s, n_s}^k_{s = 1} of such triples, the periodic map w (x) = ∑_{ns|x − as} λ_s is called the covering map of . Some interesting identities for those with a fixed covering map have been known; in this paper we mainly determine all those functions f : Ω → such that ∑^k_{s = 1} λ_sf(a_s + n_s ) depends only on w where Ω denotes the family of all residue classes. We also study algebraic structures related to such maps f, and periods of arithmetical functions ψ(x) = ∑^k_{s = 1} λ_se^2πia_sx/n_s and ω(x) = |{1 ≤ s ≤ k : (x + a_s, n_s) = 1}|.     

On the evaluation of the Eigenvalues of a banded toeplitz block matrix

Let A = (a_ij) be an n × n Toeplitz matrix with bandwidth k + 1, K = r + s, that is, a_ij = a_j−i, i, J = 1,… ,n, a_i = 0 if i > s and if i < -r. We compute p(λ)= det(A - λI), as well as p(λ)/p′(λ), where p′(λ) is the first derivative of p(λ), by using O(k log k log n) arithmetic operations. Moreover, if a_i are m × m matrices, so that A is a banded Toeplitz block matrix, then we compute p(λ), as well as p(λ)/p′(λ), by using O(m³k(log² k + log n) + m²k log k log n) arithmetic operations. The algorithms can be extended to the computation of det(A − λB) and of its first derivative, where both A and B are banded Toeplitz matrices. The algorithms may be used as a basis for iterative solution of the eigenvalue problem for the matrix A and of the generalized eigenvalue problem for A and B.     

Orlicz capacities and Hausdorff measures on metric spaces

In the setting of doubling metric measure spaces with a 1-Poincaré inequality, we show that sets of Orlicz Φ-capacity zero have generalized Hausdorff h-measure zero provided thatwhere Θ⁻¹ is the inverse of the function Θ(t)=Φ(t)/t, and s is the “upper dimension” of the metric measure space. This condition is a generalization of a well known condition in Rⁿ. For spaces satisfying the weaker q-Poincaré inequality, we obtain a similar but slightly more restrictive condition. Several examples are also provided.     

On piecewise-polynomial approximation of functions with a bounded fractional derivative in an Lp-norm

We study the error in approximating functions with a bounded (r + α)th derivative in an L_p-norm. Here r is a nonnegative integer, α ε [0, 1), and ƒ^{(r + α)} is the classical fractional derivative, i.e., ƒ^{(r + α)}(y) = ∝₀¹, ^α d(ƒ^(r)(t)). We prove that, for any such function ƒ, there exists a piecewise-polynomial of degree s that interpolates ƒ at n equally spaced points and that approximates ƒ with an error (in sup-norm) ƒ^{(r + α)}_p O(n^{−(r+α−1/p}). We also prove that no algorithm based on n function and/or derivative values of ƒ has the error equal ƒ^{(r + α)}_p O(n^{−(r+α−1/p}) for any ƒ. This implies the optimality of piecewise-polynomial interpolation. These two results generalize well-known results on approximating functions with bounded rth derivative (α = 0). We stress that the piecewise-polynomial approximation does not depend on α nor on p. It does not depend on the exact value of r as well; what matters is an upper bound s on r, s r. Hence, even without knowing the actual regularity (r, α, and p) of ƒ, we can approximate the function ƒ with an error equal (modulo a constant) to the minimal worst case error when the regularity were known.     

Sur l'approximation de fonctions intégrables sur [0, 1] par des polynômes de Bernstein modifies

We study here a new kind of modified Bernstein polynomial operators on L¹(0, 1) introduced by J. L. Durrmeyer in [4]. We define for f integrable on [0, 1] the modified Bernstein polynomial M_n f: M_nf(x) = (n + 1) ∑ⁿ_{k = o}P_nk(x)∝¹₀ P_nk(t) f(t) dt. If the derivative d^r f/dx^r with r 0 is continuous on [0, 1], d^r/dx^rM_n f converge uniformly on [0,1] and sup_xε[0,1] ¦M_n f(x) − f(x)¦ 2ω_f(1/trn) if ω_f is the modulus of continuity of f. If f is in Sobolev space W_l,p(0, 1) with l 0, p 1, M_n f converge to f in w^l,p(0, 1).     

An Error Expansion for some Gauss–Turán Quadratures and <Emphasis Type="Italic">L</Emphasis><Superscript>1</Superscript>-Estimates of the Remainder Term

Our aim in this paper is to obtain error expansions in the Gauss–Turán quadrature formula ∫₋₁¹f(t)w(t) dt=∑_ν=1ⁿ∑_i=0^2sA_i,νf⁽ⁱ⁾(τ_ν)+R_n,s(f), in the case when f is an analytic function in some region of the complex plane containing the interval [−1,1] in its interior. Using a representation of the remainder term R_n,s(f) in the form of contour integral over confocal ellipses, we obtain R_n,1(f) for the four Chebyshev weights and R_n,2(f) for the Chebyshev weight of the first kind. Also, we get a few new L¹-estimates of the remainder term, which are stronger than the previous ones. Some numerical results, illustrations and comparisons are also given. AMS subject classification (2000) 41A55, 65D30, 65D32.Received January 2004. Accepted October 2004. Communicated by Lothar Reichel.M. M. Spalević: This work was supported in part by the Serbian Ministry of Science and Environmental Protection (Project: Applied Orthogonal Systems, Constructive Approximation and Numerical Methods, grant number 2002).     

Best Approximation with Linear Constraints: A Model Example

We consider best approximation in L_p( ), 1 ≤ p ≤ ∞, by means of entire functions y of exponential type subject to additional constraints Γ_j(y) = 0, j = 1, ..., K. Here Γ_j are (unbounded) linear functionals of the form Γ_j(y) = Dⁿy(s_j) − ∑ a_kD^ky(s_j) where s_j are fixed points.     

Comonotone Jackson's Inequality

Let 2s points y_i=−πy_2s<…<y₁<π be given. Using these points, we define the points y_i for all integer indices i by the equality y_i=y_i+2s+2π. We shall write fΔ⁽¹⁾(Y) if f is a 2π-periodic continuous function and f does not decrease on [y_i, y_i−1], if i is odd; and f does not increase on [y_i, y_i−1], if i is even. In this article the following Theorem 1—the comonotone analogue of Jackson's inequality—is proved. 1. If fΔ⁽¹⁾(Y), then for each nonnegative integer n there is a trigonometric polynomial τ_n(x) of order n such that τ_nΔ⁽¹⁾(Y), and |f(x)−π_n(x)|c(s) ω(f; 1/(n+1)), x , where ω(f; t) is the modulus of continuity of f, c(s)=const. Depending only on s.     

Solutions in Sobolev spaces of vector refinement equations with a general dilation matrix

In this paper, we present a necessary and sufficient condition for the existence of solutions in a Sobolev space W_p^k(ℝ^s) (1≤p≤∞) to a vector refinement equation with a general dilation matrix. The criterion is constructive and can be implemented. Rate of convergence of vector cascade algorithms in a Sobolev space W_p^k(ℝ^s) will be investigated. When the dilation matrix is isotropic, a characterization will be given for the L_p (1≤p≤∞) critical smoothness exponent of a refinable function vector without the assumption of stability on the refinable function vector. As a consequence, we show that if a compactly supported function vector φ∈L_p(ℝ^s) (φ∈C(ℝ^s) when p=∞) satisfies a refinement equation with a finitely supported matrix mask, then all the components of φ must belong to a Lipschitz space Lip(ν,L_p(ℝ^s)) for some ν>0. This paper generalizes the results in R.Q. Jia, K.S. Lau and D.X. Zhou (J. Fourier Anal. Appl. 7 (2001) 143–167) in the univariate setting to the multivariate setting. Dedicated to Professor Charles A. Micchelli on the occasion of his 60th birthday Mathematics subject classifications (2000) 42C20, 41A25, 39B12. Research was supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC Canada) under Grant G121210654.     

Continuity envelopes of spaces of generalised smoothness, entropy and approximation numbers

We study continuity envelopes in spaces of generalised smoothness B_pq^(s,Ψ) and F_pq^(s,Ψ) and give some new characterisations for spaces B_pq^(s,Ψ). The results are applied to obtain sharp asymptotic estimates for approximation numbers of compact embeddings of type id:B_pq^(s₁,Ψ)(U)→B_∞∞^s₂(U), where and U stands for the unit ball in . In case of entropy numbers we can prove two-sided estimates.     

On Strassen's version of the law of the iterated logarithm for the two-parameter Gaussian process

Strassen's version of the law of the iterated logarithm is extended to the two-parameter Gaussian process {X(s, t); ε(s, t) [0, ∞)²} with the covariance function R((s₁,t₁),(s₂,t₂)) = min(s₁,s₂)min(t₁,t₂).