A complexity measure for families of binary sequences

In earlier papers finite pseudorandom binary sequences were studied, quantitative measures of pseudorandomness of them were introduced and studied, and large families of “good” pseudorandom sequences were constructed. In certain applications (cryptography) it is not enough to know that a family of “good” pseudorandom binary sequences is large, it is a more important property if it has a “rich”, “complex” structure. Correspondingly, the notion of “f-complexity” of a family of binary sequences is introduced. It is shown that the family of “good” pseudorandom binary sequences constructed earlier is also of high f-complexity. Finally, the cardinality of the smallest family achieving a prescibed f-complexity and multiplicity is estimated. This revised version was published online in August 2006 with corrections to the Cover Date.     

A note on nonparametric density estimation for dependent variables using a delta sequence

Summary A general method based on “delta sequences” due to Walter and Blum [12] is extended to sequences of strictly stationary mixing random variables having the same marginal distribution admitting a Lebesgue probability density function. It is proved that, under certain conditions, the rate of mean square convergence obtained in the i.i.d. case by Walter and Blum, continues to hold. University of Petroleum and Minerals     

Hyper-rectangular space partitioning trees: A practical approach

Summary  The process of computation of classification trees can be characterized as involving three basic choices: the type of splits considered in the growing process, the criterion to be optimized at each step of the process, and the way to get right-sized trees. Most implementations are ordinary binary trees, i.e. trees whose successive cuts are made by hyper-planes perpendicular to the axes. L. Devroye, L. Gy?rfy and G. Lugosi (1996) define and consider the remarkable theoretical properties of a binary tree classifier whose prominent feature is the particular type of splits used in its construction: at a given node, partitioning is made by hyper-rectangles rather than hyper-planes. We propose an approximation of the solution for the complex optimization problem involved to allow insights on the practical advantages of those trees. Then we compare the performance of our algorithm with some leading algorithms for ordinary binary trees, namely CART and C4.5 as implemented in the Splus “tree” procedure and in SAS’s Enterprise Miner respectively. Research support from “Projet d’Actions de Recherche Concertées” (No. 98/03-217) and from the “Interuniversity Attraction Pole”, Phase V (No. P5/24) from the Belgian Government are also acknowledged.     

Existence Theorems for Periodic Differential Inclusions in IR^N

We study the periodic problem for differential inclusions in R~N.First we look for extremal periodicsolutions.Using techniques from multivalued analysis and a fixed point argument we establish an existencetheorem under some general hypotheses.We also consider the“nonconvex periodic problem”under lowersemicontinuity hypotheses,and the“convex periodic problem”under general upper semicontinuity hypotheseson the multivalued vector field.For both problems,we prove existence theorems under very general hypotheses.Our approach extends existing results in the literature and appear to be the most general results on the nonconvexperiodic problem.     

Isomorphism of random walks

We show that any two aperiodic, recurrent random walks on the integers whose jump distributions have finite seventh moment, are isomorphic as infinite measure preserving transformations. The method of proof involved uses a notion of equivalence of renewal sequences, and the “relative” isomorphism of Bernoulli shifts respecting a common state lumping with the same conditional entropy. We also prove an analogous result for random walks on the two dimensional integer lattice.     

Symbolic calculus for boundary value problems on manifolds with edges

Boundary value problems for (pseudo-) differential operators on a manifold with edges can be characterised by a hierarchy of symbols. The symbolic structure is responsible for ellipticity and for the nature of parametrices within an algebra of “edge-degenerate” pseudo-differential operators. The edge symbolic component of that hierarchy takes values in boundary value problems on an infinite model cone, with edge variables and covariables as parameters. Edge symbols play a crucial role in this theory, in particular, the contribution with holomorphic operator-valued Mellin symbols. We establish a calculus in a framework of “twisted homogeneity” that refers to strongly continuous groups of isomorphisms on weighted cone Sobolev spaces. We then derive an equivalent representation with a particularly transparent composition behaviour.     

A Probabilistic Approach to Carne’s Bound

Carne’s bound is a sharp inequality controlling the transition probabilities for a discrete reversible Markov chain (Section 1). Its ordinary proof uses spectral techniques which look as efficient as miraculous. Here we present a new proof, comparing a “drift” for ways “out” and “back”, to get the gaussian part of the bound (Section 2), and using a conditioning technique to get the flight factor (Section 4). Moreover we show how our proof is more “supple” than Carne’s one and may generalize (Section 3.2).      

Construction of large families of pseudorandom binary sequences

Oon constructed large families of finite binary sequences with strong pseudorandom properties by using Dirichlet characters of large order. In this paper Oon’s construction is generalized and extended. We prove that in our construction the well-distribution and correlation measures are as “small” as in the case of the Legendre symbol.      

Decomposition of binary matroids

We prove results relating to the decomposition of a binary matroid, including its uniqueness when the matroid is cosimple. We extend the idea of “freedom” of an element in a matroid to “freedom” of a set, and show that there is a unique maximal integer polymatroid inducing a given binary matroid.     

The multiplicity of solutions in non-homogeneous boundary value problems

We use a method recently devised by Bolle to establish the existence of an infinite number of solutions for various non-homogeneous boundary value problems. In particular, we consider second order systems, Hamiltonian systems as well as semi-linear partial differential equations. The non-homogeneity can originate in the equation but also from the boundary conditions. The results are more satisfactory than those obtained by the standard “Perturbation from Symmetry” method that was developed – in various forms – in the early eighties by Bahri–Berestycki, Struwe and Rabinowitz. Received: 13 August 1998 / Revised version: 6 July 1999     

On the favorable estimation for fitting heavy tailed data

Assessment of heavy tailed data and its compound sums has many applications in insurance, auditing and operational risk capital assessment among others. In this paper, we compare the classical estimators (maximum likelihood, QQ and moment estimators) with the recently introduced robust estimators of “generalized median”, “trimmed mean” and estimators based on t-score moments. We derive the exact distribution of the likelihood ratio tests of homogeneity and simple hypothesis on the tail index of a two-parameter Pareto model. Such exact tests support the assessment of the performance of estimators. In particular, we discuss some problems that one can encounter when misemploying the log-normal assumption based methods supported by the Basel II framework. Real data and simulated examples illustrate the methods.     

The Polynomial Method for Random Matrices

We define a class of “algebraic” random matrices. These are random matrices for which the Stieltjes transform of the limiting eigenvalue distribution function is algebraic, i.e., it satisfies a (bivariate) polynomial equation. The Wigner and Wishart matrices whose limiting eigenvalue distributions are given by the semicircle law and the Marčenko–Pastur law are special cases. Algebraicity of a random matrix sequence is shown to act as a certificate of the computability of the limiting eigenvalue density function. The limiting moments of algebraic random matrix sequences, when they exist, are shown to satisfy a finite depth linear recursion so that they may often be efficiently enumerated in closed form. In this article, we develop the mathematics of the polynomial method which allows us to describe the class of algebraic matrices by its generators and map the constructive approach we employ when proving algebraicity into a software implementation that is available for download in the form of the RMTool random matrix “calculator” package. Our characterization of the closure of algebraic probability distributions under free additive and multiplicative convolution operations allows us to simultaneously establish a framework for computational (noncommutative) “free probability” theory. We hope that the tools developed allow researchers to finally harness the power of infinite random matrix theory.     

Converging Marriage in Honey-Bees Optimization and Application to Stochastic Dynamic Programming

In this paper, we first refine a recently proposed metaheuristic called “Marriage in Honey-Bees Optimization” (MBO) for solving combinatorial optimization problems with some modifications to formally show that MBO converges to the global optimum value. We then adapt MBO into an algorithm called “Honey-Bees Policy Iteration” (HBPI) for solving infinite horizon-discounted cost stochastic dynamic programming problems and show that HBPI also converges to the optimal value.     

Stability analysis for several second-order Sigma—Delta methods of coarse quantization of bandlimited functions

We investigate the stability and robustness properties of a family of algorithms used to “coarsely quantize” bandlimited functions. The algorithms we will consider are one-bit second-orderΣΔA-quantization schemes and some modified versions of these. We prove that there exists a bounded region that remains positively invariant under the two-dimensional piecewise-affine discrete dynamical system associated with each of these quantizers. Moreover, this bounded region can be constructed so that it is robust under small changes in the quantizer. We also show some interesting properties of the resulting binary sequences.     

Finite groups with planar subgroup lattices

It is natural to ask when a group has a planar Hasse lattice or more generally when its subgroup graph is planar. In this paper, we completely answer this question for finite groups. We analyze abelian groups, p-groups, solvable groups, and nonsolvable groups in turn. We find seven infinite families (four depending on two parameters, one on three, two on four), and three “sporadic” groups. In particular, we show that no nonabelian group whose order has three distinct prime factors can be planar.     

Positive matrix semigroups with binary diagonals

We show that a semigroup of positive matrices (all entries greater than or equal to zero) with binary diagonals (diagonal entries either 0 or 1) is either decomposable (all matrices in the semigroup have a common zero entry) or is similar, via a positive diagonal matrix, to a binary semigroup (all entries 0 or 1). In the case where the idempotents of minimal rank in S{\mathcal{S}} satisfy a “diagonal disjointness” condition, we obtain additional structural information. In the case where the semigroup is not necessarily positive but has binary diagonals we show that either the semigroup is reducible or the minimal rank ideal is a binary semigroup. We also give generalizations of these results to operators acting on the Hilbert space of square-summable sequences.     

On a size-structured two-phase population model with infinite states-at-birth

In this work, we introduce and analyze a linear size-structured population model with infinite states-at-birth. We model the dynamics of a population in which individuals have two distinct life-stages: an “active” phase when individuals grow, reproduce and die and a second “resting” phase when individuals only grow. Transition between these two phases depends on individuals’ size. First we show that the problem is governed by a positive quasicontractive semigroup on the biologically relevant state space. Then, we investigate, in the framework of the spectral theory of linear operators, the asymptotic behavior of solutions of the model. We prove that the associated semigroup has, under biologically plausible assumptions, the property of asynchronous exponential growth.     

Compositions of n as alternating sequences of weakly increasing and strictly decreasing partitions

Compositions and partitions of positive integers are often studied in separate frameworks where partitions are given by q-series generating functions and compositions exhibiting specific patterns are designated by generating functions for these patterns. Here, we view compositions as alternating sequences of weakly increasing and strictly decreasing partitions (i.e. alternating blocks). We obtain generating functions for the number of such partitions in terms of the size of the composition, the number of parts and the total number of “valleys” and “peaks”. From this, we find the total number of “peaks” and “valleys” in the composition of n which have the mentioned pattern. We also obtain the generating function for compositions which split into just two partition blocks. Finally, we obtain the two generating functions for compositions of n that start either with a weakly increasing partition or a strictly decreasing partition.     

Frequentist and Bayesian measures of confidence via multiscale bootstrap for testing three regions

A new computation method of frequentist p values and Bayesian posterior probabilities based on the bootstrap probability is discussed for the multivariate normal model with unknown expectation parameter vector. The null hypothesis is represented as an arbitrary-shaped region of the parameter vector. We introduce new functional forms for the scaling-law of bootstrap probability so that the multiscale bootstrap method, which was designed for a one-sided test, can also compute confidence measures of a two-sided test, extending applicability to a wider class of hypotheses. Parameter estimation for the scaling-law is improved by the two-step multiscale bootstrap and also by including higher order terms. Model selection is important not only as a motivating application of our method, but also as an essential ingredient in the method. A compromise between frequentist and Bayesian is attempted by showing that the Bayesian posterior probability with a noninformative prior is interpreted as a frequentist p value of “zero-sided” test.