Asymptotic Joint Normality of Counts of Uncorrelated Motifs in Recursive Trees

We study the fringe of random recursive trees, by analyzing the joint distribution of the counts of uncorrelated motifs. Our approach allows for finite and countably infinite collections. To be able to deal with the collection when it is infinitely countable, we use measure-theoretic themes. Each member of a collection of motifs occurs a certain number of times on the fringe. We show that these numbers, under appropriate normalization, have a limiting joint multivariate normal distribution. We give a complete characterization of the asymptotic covariance matrix. The methods of proof include contraction in a metric space of distribution functions to a fixed-point solution (limit distribution). We discuss two examples: the finite collection of all possible motifs of size four, and the infinite collection of rooted stars. We conclude with remarks to compare fringe-analysis with matching motifs everywhere in the tree.     

Waiting times for clumps of patterns and for structured motifs in random sequences

This paper provides exact probability results for waiting times associated with occurrences of two types of motifs in a random sequence. First, we provide an explicit expression for the probability generating function of the interarrival time between two clumps of a pattern. It allows, in particular, to measure the quality of the Poisson approximation which is currently used for evaluation of the distribution of the number of clumps of a pattern. Second, we provide explicit expressions for the probability generating functions of both the waiting time until the first occurrence, and the interarrival time between consecutive occurrences, of a structured motif. Distributional results for structured motifs are of interest in genome analysis because such motifs are promoter candidates. As an application, we determine significant structured motifs in a data set of DNA regulatory sequences.     

On the restricted cores and the bounded core of games on distributive lattices

A game with precedence constraints is a TU game with restricted cooperation, where the set of feasible coalitions is a distributive lattice, hence generated by a partial order on the set of players. Its core may be unbounded, and the bounded core, which is the union of all bounded faces of the core, proves to be a useful solution concept in the framework of games with precedence constraints. Replacing the inequalities that define the core by equations for a collection of coalitions results in a face of the core. A collection of coalitions is called normal if its resulting face is bounded. The bounded core is the union of all faces corresponding to minimal normal collections. We show that two faces corresponding to distinct normal collections may be distinct. Moreover, we prove that for superadditive games and convex games only intersecting and nested minimal collection, respectively, are necessary. Finally, it is shown that the faces corresponding to pairwise distinct nested normal collections may be pairwise distinct, and we provide a means to generate all such collections.     

Stationarity and Regularity of Infinite Collections of Sets

This article investigates extremality, stationarity, and regularity properties of infinite collections of sets in Banach spaces. Our approach strongly relies on the machinery developed for finite collections. When dealing with an infinite collection of sets, we examine the behavior of its finite subcollections. This allows us to establish certain primal-dual relationships between the stationarity/regularity properties some of which can be interpreted as extensions of the Extremal principle. Stationarity criteria developed in the article are applied to proving intersection rules for Fréchet normals to infinite intersections of sets in Asplund spaces.     

An Interactive Icon Index: Images of the Outer Planets

Abstract

We are interested in the exploratory analysis of large collections of complex objects. As an example, we are studying a large collection of digital images that has nearly 30,000 members. We regard each image in the collection as an individual observation. To facilitate our study we construct an index of the images in the collection. The index uses a small copy of each image (an icon or a “thumbnail”) to represent the full-size version. A large number of these thumbnails are laid out in a workstation window. We can interactively arrange and rearrange the thumbnails within the window. For example, we can sort the thumbnails by the values of a function computed from them or by the values of data associated with each of them. By the use of specialized equipment (a single-frame video disk recorder/player), we can instantly access any individual full-size image in the collection as a video image. We regard our software as an early development of statistical exploratory tools for studying collections of images and other complex objects in the same way we routinely study batches of numbers. We expect that the concept of a visual index will extend to other collections of complex objects besides images, for example, time series, functions, and text.     

Occurrence of structured motifs in random sequences: Arbitrary number of boxes

Structured motifs with arbitrary number of boxes are considered. In particular, such motifs are of interest in molecular biology for identifying gene promoters along genomes. Neat closed-form expressions for relevant distributions associated with occurrences of structured motifs are derived. Our methodology is based on developing a suitable semi-Markov embedding of the problem. A numerical example is also provided.     

Avoidance of split overlaps

We generalize Axel Thue’s familiar definition of overlaps in words, and observe that there are no infinite words avoiding split occurrences of these generalized overlaps. We give estimates for the length of the longest finite word that avoids split overlaps. Along the way we prove a useful theorem about repeated disjoint occurrences in words — an interesting natural variation on the classical de Bruijn sequences.     

General methods of elliptic minimization

We provide general methods in the calculus of variations for the anisotropic Plateau problem in arbitrary dimension and codimension. Given a collection of competing “surfaces” that span a given “bounding set” in an ambient metric space, we produce one minimizing an elliptic area functional. The collection of competing surfaces is assumed to satisfy a set of geometrically-defined axioms. These axioms hold for collections defined using any combination of homological, cohomological or linking number spanning conditions. A variety of minimization problems can be solved, including sliding boundaries.     

Applying the cluster method to count occurrences of generalized permutation patterns

We apply ideas from the cluster method to q-count the permutations of a multiset according to the number of occurrences of certain generalized patterns, as defined by Babson and Steingrímsson. In particular, we consider those patterns with three letters and one internal dash, as well as permutation statistics composed of counting the number of occurrences of multisets of such patterns. Counting is done via recurrences which simplify in the case of permutations. A collection of Maple procedures implementing these recurrences accompanies the article.     

Scheduling unit-length jobs with precedence constraints of small height

We consider the problem of scheduling unit-length jobs on identical machines subject to precedence constraints. We show that natural scheduling rules fail when the precedence constraints form a collection of stars or a collection of complete bipartite graphs. We prove that the problem is in fact NP-hard on collections of stars when the input is given in a compact encoding, whereas it can be solved in polynomial time with standard adjacency list encoding. On a subclass of collections of stars and on collections of complete bipartite graphs we show that the problem can be solved in polynomial time even when the input is given in compact encoding, in both cases via non-trivial algorithms.     

Integrals of semiintegrable k-tuples of germs of vector fields in the plane

An ordered collection of vector fields in the plane is called a semiintegrable collection if each succeeding element of the collection lies in the stationary subalgebra (in the algebra of smooth vector fields) of the phase portraits of all the preceding elements of the collection. The orbital equivalence of semiintegrable collections means the possibility of transferring, with the aid of a diffeomorphism of the plane, the phase portraits of the elements of one collection into those of the other one, respectively, with the preservation of the order. A complete classification of finite-modal collections relative to orbital equivalence is obtained. The invariants of the normal forms, namely the generators of the algebra of the first integrals, the invariant measures, the stationary subalgebras of the phase portraits of the collection, are computed in terms of elementary functions. Integer-valued invariants are obtained, like the number of elements in the collection, the dimension of the stationary subalgebra, etc.Translated from Trudy Seminara imeni I. G. Petrovskogo, No. 16, pp. 70–105, 1992.     

Inference for the Number of Topics in the Latent Dirichlet Allocation Model via Bayesian Mixture Modeling

In latent Dirichlet allocation, the number of topics, T, is a hyperparameter of the model that must be specified before one can fit the model. The need to specify T in advance is restrictive. One way of dealing with this problem is to put a prior on T, but unfortunately the distribution on the latent variables of the model is then a mixture of distributions on spaces of different dimensions, and estimating this mixture distribution by Markov chain Monte Carlo is very difficult. We present a variant of the Metropolis–Hastings algorithm that can be used to estimate this mixture distribution, and in particular the posterior distribution of the number of topics. We evaluate our methodology on synthetic data and compare it with procedures that are currently used in the machine learning literature. We also give an illustration on two collections of articles from Wikipedia. Supplemental materials for this article are available online.     

Patterns in random permutations avoiding the pattern 321

We consider a random permutation drawn from the set of 321 ‐avoiding permutations of length n and show that the number of occurrences of another pattern σ has a limit distribution, after scaling by n^{m + ?} where m is the length of σ and ? is the number of blocks in it. The limit is not normal, and can be expressed as a functional of a Brownian excursion.     

Infinitely many meridional essential surfaces of bounded genus in hyperbolic knot exteriors

Geometriae Dedicata - We show the existence of an infinite collection of hyperbolic knots where each of which has in its exterior meridional essential planar surfaces of arbitrarily large number of...     

Adaptive compensation of uncertain Euler–Lagrange systems with multiple time-varying actuator faults

This work proposes the command tracking problem for uncertain Euler–Lagrange (EL) systems with multiple partial loss of effectiveness (PLOE) actuator faults. Compared to existing fault-tolerant controllers for EL systems, the proposed adaptive controller accounts for parametric uncertainties in the system and multiple time-varying actuator fault parameters. The proposed method can also handle an infinite number of fault cases. The closed-loop fault-tolerant system is treated as a switched dynamical system, and a switched system stability is established using multiple Lyapunov functions. It is shown that all signals are bounded in each sub-interval and at the switching instances, and asymptotic tracking can be obtained only for a finite number of fault occurrences, whereas tracking error is bounded for the infinite case. Finally, a simulation example on a robotic manipulator is presented to show the effectiveness of the proposed method.     

Local Convergence of Large Critical Multi-type Galton–Watson Trees and Applications to Random Maps

We show that large critical multi-type Galton–Watson trees, when conditioned to be large, converge locally in distribution to an infinite tree which is analogous to Kesten’s infinite monotype Galton–Watson tree. This is proven when we condition on the number of vertices of one fixed type, and with an extra technical assumption if we count at least two types. We then apply these results to study local limits of random planar maps, showing that large critical Boltzmann-distributed random maps converge in distribution to an infinite map.     

On positive definite quadratic forms in correlatedt variables

Summary In this paper we extend Ruben's [4] result for quadratic forms in normal variables. He represented the distribution function of the quadratic form in normal variables as an infinite mixture of chi-square distribution functions. In the central case, we show that the distribution function of a quadratic form int-variables can be represented as a mixture of beta distribution functions. In the noncentral case, the distribution function presented is an infinite series in beta distribution functions. An application to quadratic discrimination is given.     

The joint distribution of the number of occurrences of two interrelated Poisson processes

The focus of this paper is the distribution for the number of occurrences of two independent but interrelated Poisson processes, to be named the joint imputed Poisson distribution. From its inception, the research was motivated by a problem facing the electric power industry. Power surges, which are observable, represent occurrences of the imputing process. Circuit breaker breakdowns, which cannot be seen taking place, constitute occurrences of the imputed process. Though not observable, at each occurrence of the imputing process, knowledge about the imputed process is obtained. Occurrences of the imputed process are revealed only as the result of periodic inspection, or with far greater cost at the subsequent occurrence of the imputing process. A comprehensive treatment of the joint imputed Poisson distribution for the number of occurrences of the two processes over a fixed time period was presented by Cuffe. Because these probabilistic results had to be derived from first principles, a lengthy, rigorous mathematical exposition is not appropriate in this forum. Rather, we concentrate here on a presentation of results with only highlights of their proofs.     

Limit theorems for queueing systems with infinite number of servers and group arrival of requests

We consider an infinite-server queueing system where customers come by groups of random size at random i.d. intervals of time. The number of requests in a group and intervals between their arrivals can be dependent. We assume that service times have a regularly varying distribution with infinite mean. We obtain limit theorems for the number of customers in the system and prove limit theorems under appropriate normalizations.     

Stationarity and Regularity of Infinite Collections of Sets. Applications to Infinitely Constrained Optimization

This article continues the investigation of stationarity and regularity properties of infinite collections of sets in a Banach space started in Kruger and López (J.?Optim. Theory Appl. 154(2), 2012), and is mainly focused on the application of the stationarity criteria to infinitely constrained optimization problems. We consider several settings of optimization problems which involve (explicitly or implicitly) infinite collections of sets and deduce for them necessary conditions characterizing stationarity in terms of dual space elements??normals and/or subdifferentials.