Asymptotic behavior of the ratio of tail probabilities of sum and maximum of independent random variables

For a fixed integer n ≥ 2, let X ₁ ,…, X _n be independent random variables (r.v.s) with distributions F ₁,…,F _n , respectively. Let Y be another random variable with distribution G belonging to the intersection of the longtailed distribution class and the O-subexponential distribution class. When each tail of F _i , i = 1,…,n, is asymptotically less than or equal to the tail of G, we derive asymptotic lower and upper bounds for the ratio of the tail probabilities of the sum X ₁ + ⋯ + X _n and Y. By taking different G’s, we obtain general forms of some existing results.     

Sparse Dynamic Programming for Longest Common Subsequence from Fragments

Sparse Dynamic Programming has emerged as an essential tool for the design of efficient algorithms for optimization problems coming from such diverse areas as computer science, computational biology, and speech recognition. We provide a new sparse dynamic programming technique that extends the Hunt–Szymanski paradigm for the computation of the longest common subsequence (LCS) and apply it to solve the LCS from Fragments problem: given a pair of strings X and Y (of length n and m, respectively) and a set M of matching substrings of X and Y, find the longest common subsequence based only on the symbol correspondences induced by the substrings. This problem arises in an application to analysis of software systems. Our algorithm solves the problem in O(|M| log |M|) time using balanced trees, or O(|M| log log min(|M|, nm/|M|)) time using Johnson's version of Flat Trees. These bounds apply for two cost measures. The algorithm can also be adapted to finding the usual LCS in O((m + n) log |Σ| + |M| log |M|) time using balanced trees or O((m + n) log |Σ| + |M| log log min (|M|, nm/|M|)) time using Johnson's version of Flat Trees, where M is the set of maximal matches between substrings of X and Y and Σ is the alphabet. These bounds improve on those of the original Hunt–Szymanski algorithm while retaining the overall approach.     

The structure of LC-continuous functions

A function f is LC-continuous if the inverse image of any open set is a locally closed set; i.e., an intersection of an open set and a closed set. The aim of this paper is to prove the following theorem: Let f: X→Y be an LC-continuous function onto a separable metric space Y. Then X can be covered by countably many subsets T _n ⊂X such that each restriction f∣T _n is continuous at all points of T _n .     

Extremes of independent Gaussian processes

For every n ∈ ℕ, let X _1n ,..., X _nn be independent copies of a zero-mean Gaussian process X _n  = {X _n (t), t ∈ T}. We describe all processes which can be obtained as limits, as n→ ∞, of the process a _n (M _n  − b _n ), where M _n (t) =  max _{i = 1,...,n} X _in (t), and a _n , b _n are normalizing constants. We also provide an analogous characterization for the limits of the process a _n L _n , where L _n (t) =  min _{i = 1,...,n} |X _in (t)|.     

Independent sequences in Banach spaces

In every ∞-dimensional separable Banach spaceX there is a fundamental sequence such that no subsequence of it, which is fundamental inX, is independent (“{x _n} is fundamental inX” meansX=span {x _n}).     

Some properties and applications of weakly equicompact sets

Let X and Y be Banach spaces. A set (the space of all weakly compact operators from X into Y) is weakly equicompact if, for every bounded sequence (x _n) in X, there exists a subsequence (x _k(n)) so that (Tx_k(n)) is uniformly weakly convergent for T ∈ M. In this paper, the notion of weakly equicompact set is used to obtain characterizations of spaces X such that X ↩̸ ℓ₁, of spaces X such that B _X* is weak* sequentially compact and also to obtain several results concerning to the weak operator and the strong operator topologies. As another application of weak equicompactness, we conclude a characterization of relatively compact sets in when this space is endowed with the topology of uniform convergence on the class of all weakly null sequences. Finally, we show that similar arguments can be applied to the study of uniformly completely continuous sets. Received: 5 July 2006     

Nonsmoothable involutions on spin 4-manifolds

Let X be a closed, simply-connected, smooth, spin 4-manifold whose intersection form is isomorphic to n( − E ₈) ⊕ mH, where H is the hyperbolic form. In this paper, we prove that for n such that n ≡ 2  mod  4, there exists a locally linear pseudofree ℤ₂-action on X which is nonsmoothable with respect to any possible smooth structure on X.     

Cantor set and interpolation

In 1998, Y. Benyamini published interesting results concerning interpolation of sequences using continuous functions ℝ → ℝ. In particular, he proved that there exists a continuous function ℝ → ℝ which in some sense “interpolates” all sequences (x _n ) _n∈ℤ ∈ [0, 1]^ℤ “simultaneously.” In 2005, M.R. Naulin and C. Uzcátegui unified and generalized Benyamini’s results. In this paper, the case of topological spaces X and Y with an Abelian group acting on X is considered. A similar problem of “simultaneous interpolation” of all “generalized sequences” using continuous mappings X → Y is posed. Further generalizations of Naulin-Uncátegui theorems, in particular, multidimensional analogues of Benyamini’s results are obtained.     

On the First Hitting Time of a One-dimensional Diffusion and a Compound Poisson Process

It is studied the first-passage time (FPT) of a time homogeneous one-dimensional diffusion, driven by the stochastic differential equation dX(t) = μ(X(t))dt + σ(X(t)) dB _t , X(0) = x ₀, through b + Y(t), where b > x ₀ and Y(t) is a compound Poisson process with rate λ > 0 starting at 0, which is independent of the Brownian motion B _t . In particular, the FPT density is investigated, generalizing a previous result, already known in the case when X(t) = μt + B _t , for which the FPT density is the solution of a certain integral equation. A numerical method is shown to calculate approximately the FPT density; some examples and numerical results are also reported.     

Modulus of Strong Proximinality and Continuity of Metric Projection

In this paper we initiate a quantitative study of strong proximinality. We define a quantity ϵ(x, t) which we call as modulus of strong proximinality and show that the metric projection onto a strongly proximinal subspace Y of a Banach space X is continuous at x if and only if ϵ(x, t) is continuous at x whenever t > 0. The best possible estimate of ϵ(x, t) characterizes spaces with 1 \frac121 \frac{1}{2} ball property. Estimates of ϵ(x, t) are obtained for subspaces of uniformly convex spaces and of strongly proximinal subspaces of finite codimension in C(K).     

A Large Deviation Principle for Stochastic Integrals

Assuming that {(X _n ,Y _n )} satisfies the large deviation principle with good rate function I ^♯ , conditions are given under which the sequence of triples {(X _n ,Y _n ,X _n ⋅Y _n )} satisfies the large deviation principle. An ε-approximation to the stochastic integral is proven to be almost compact. As is well known from the contraction principle, we can derive the large deviation principle when applying continuous functions to sequences that satisfy the large deviation principle; the method showed here skips the contraction principle, uses almost compactness and can be used to derive a generalization of the work of Dembo and Zeitouni on exponential approximations. An application of the main result to stochastic differential equations is given, namely, a Freidlin-Wentzell theorem is obtained for a sequence of solutions of SDE’s.     

Order of magnitude bounds for expectations of Δ2-functions of generalized random bilinear forms

Let Φ be a symmetric function, nondecreasing on [0,∞) and satisfying a Δ₂ growth condition, (X ₁,Y ₁), (X ₂,Y ₂),…,(X _n ,Y _n ) be arbitrary independent random vectors such that for any given i either Y _i =X _i or Y _i is independent of all the other variates. The purpose of this paper is to develop an approximation of

The Geometry of Relations

The classical way to study a finite poset (X, ≤ ) using topology is by means of the simplicial complex Δ _X of its nonempty chains. There is also an alternative approach, regarding X as a finite topological space. In this article we introduce new constructions for studying X topologically: inspired by a classical paper of Dowker (Ann Math 56:84–95, 1952), we define the simplicial complexes K _X and L _X associated to the relation ≤. In many cases these polyhedra have the same homotopy type as the order complex Δ _X . We give a complete characterization of the simplicial complexes that are the K or L-complexes of some finite poset and prove that K _X and L _X are topologically equivalent to the smaller complexes K′ _X , L′ _X induced by the relation <. More precisely, we prove that K _X (resp. L _X ) simplicially collapses to K′ _X (resp. L′ _X ). The paper concludes with a result that relates the K-complexes of two posets X, Y with closed relations R ⊂ X × Y.     

On genera of polyhedra

We consider the stable homotopy category S of polyhedra (finite cell complexes). We say that two polyhedra X,Y are in the same genus and write X ∼ Y if X _p ≅ Y _p for all prime p, where X _p denotes the image of Xin the localized category S _p . We prove that it is equivalent to the stable isomorphism X∨B ₀ ≅Y∨B ₀, where B ₀ is the wedge of all spheres S ⁿ such that π _n ^S (X) is infinite. We also prove that a stable isomorphism X ∨ X ≅ Y ∨ X implies a stable isomorphism X ≅ Y.     

Inference concerning the population correlation coefficient from bivariate normal samples based on minimal observations

Summary Let (X, Y) be bivariate normally distributed with means (μ ₁,μ ₂), variances (σ ₁ ² ,σ ₂ ² ) and correlation betweenX andY equal to ρ. Let (X _i ,Y _i ) be independent observations on (X,Y) fori=1,2,...,n. Because of practical considerations onlyZ _i =min (X _i ,Y _i) is observed. In this paper, as in certain routine applications, assuming the means and the variances to be known in advance, an unbiased consistent estimator of the unknown distribution parameter ρ is proposed. A comparison between the traditional maximum likelihood estimator and the unbiased estimator is made. Finally, the problem is extended to multivariate normal populations with common mean, common variance and common non-negative correlation coefficient.     

Limit theorems for a recursive maximum process with location-dependent periodic intensity-parameter

We investigate the recursive sequence Z _n : =  max {Z _n − 1,λ(Z _n − 1)X _n } where X _n is a sequence of iid random variables with exponential distributions and λ is a periodic positive bounded measurable function. We prove that the Césaro mean of the sequence λ(Z _n ) converges toward the essential minimum of λ. Subsequently we apply this result and obtain a limit theorem for the distributions of the sequence Z _n . The resulting limit is a Gumbel distribution.     

The ratio of the extreme to the sum in a random sequence

For X ₁ , X ₂ , ..., X _n a sequence of non-negative independent random variables with common distribution function F(t), X _(n) denotes the maximum and S _n denotes the sum. The ratio variate R _n  = X _(n) / S _n is a quantity arising in the analysis of process speedup and the performance of scheduling. O’Brien (J. Appl. Prob. 17:539–545, 1980) showed that as n → ∞, R _n →0 almost surely iff is finite. Here we show that, provided either (1) is finite, or (2) 1 − F (t) is a regularly varying function with index ρ < − 1, then . An integral representation for the expected ratio is derived, and lower and upper asymptotic bounds are developed to obtain the result. Since is often known or estimated asymptotically, this result quantifies the rate of convergence of the ratio’s expected value. The result is applied to the performance of multiprocessor scheduling.      

Joint continuity of <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">h</Emphasis></Subscript><Emphasis Type="Italic">C</Emphasis>-functions with values in moore spaces

We introduce the notion of categorical cliquish mapping and show that, for each K _h C-mapping f: X × Y → Z, where X is a topological space, Y is a space with the first axiom of countability, and Z is a Moore space, with categorical-cliquish horizontal y-sections f _y , the sets C _y (f) are residual G _δ-type sets in X for every y ∈ Y. Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 60, No. 11, pp. 1539–1547, November, 2008.     

The nearness problems for symmetric centrosymmetric with a special submatrix constraint

We say that X=[x_ij]_i,j=1ⁿX=[x_{ij}]_{i,j=1}^n is symmetric centrosymmetric if x _ij  = x _ji and x _{n − j + 1,n − i + 1}, 1 ≤ i,j ≤ n. In this paper we present an efficient algorithm for minimizing ||AXA ^T  − B|| where ||·|| is the Frobenius norm, A ∈ ℝ ^m×n , B ∈ ℝ ^m×m and X ∈ ℝ ^n×n is symmetric centrosymmetric with a specified central submatrix [x _ij ] _{p ≤ i,j ≤ n − p} . Our algorithm produces a suitable X such that AXA ^T  = B in finitely many steps, if such an X exists. We show that the algorithm is stable any case, and we give results of numerical experiments that support this claim.     

The Johnson–Lindenstrauss Lemma Almost Characterizes Hilbert Space, But Not Quite

Let X be a normed space that satisfies the Johnson–Lindenstrauss lemma (J–L lemma, in short) in the sense that for any integer n and any x ₁,…,x _n ∈X, there exists a linear mapping L:X→F, where F⊆X is a linear subspace of dimension O(log n), such that ‖x _i −x _j ‖≤‖L(x _i )−L(x _j )‖≤O(1)⋅‖x _i −x _j ‖ for all i,j∈{1,…,n}. We show that this implies that X is almost Euclidean in the following sense: Every n-dimensional subspace of X embeds into Hilbert space with distortion 2^2O(log*n)2^{2^{O(\log^{*}n)}} . On the other hand, we show that there exists a normed space Y which satisfies the J–L lemma, but for every n, there exists an n-dimensional subspace E _n ⊆Y whose Euclidean distortion is at least 2^Ω(α(n)), where α is the inverse Ackermann function.