Nonparametric tests of independence between random vectors

A nonparametric test of the mutual independence between many numerical random vectors is proposed. This test is based on a characterization of mutual independence defined from probabilities of half-spaces in a combinatorial formula of Möbius. As such, it is a natural generalization of tests of independence between univariate random variables using the empirical distribution function. If the number of vectors is p and there are n observations, the test is defined from a collection of processes R_n,A, where A is a subset of {1,…,p} of cardinality |A|>1, which are asymptotically independent and Gaussian. Without the assumption that each vector is one-dimensional with a continuous cumulative distribution function, any test of independence cannot be distribution free. The critical values of the proposed test are thus computed with the bootstrap which is shown to be consistent. Another similar test, with the same asymptotic properties, for the serial independence of a multivariate stationary sequence is also proposed. The proposed test works when some or all of the marginal distributions are singular with respect to Lebesgue measure. Moreover, in singular cases described in Section 4, the test inherits useful invariance properties from the general affine invariance property.     

Independence in topological and <Emphasis Type="Italic">C</Emphasis>*-dynamics

We develop a systematic approach to the study of independence in topological dynamics with an emphasis on combinatorial methods. One of our principal aims is to combinatorialize the local analysis of topological entropy and related mixing properties. We also reframe our theory of dynamical independence in terms of tensor products and thereby expand its scope to C*-dynamics.     

Independence entropy of \mathbb{Z}^{d}-shift spaces

We introduce a concept of independence entropy for symbolic dynamical systems. This notion of entropy measures the extent to which one can freely insert symbols in positions without violating the constraint defined by the shift space. We show that for a certain class of one-dimensional shift spaces X, the independence entropy coincides with the limiting, as d tends to infinity, topological entropy of the dimensional shift defined by imposing the constraints of X in each of the d cardinal directions. This is of interest because for these shift spaces independence entropy is easy to compute. Thus, while in these cases, the topological entropy of the d-dimensional shift (d≥2) is difficult to compute, the limiting topological entropy is easy to compute. In some cases, we also compute the rate of convergence of the sequence of d-dimensional entropies. This work generalizes earlier work on constrained systems with unconstrained positions.     

A new class of order types

Let φ₄ be the class of all order-types ϕ with the properties that every uncountable subtype of ϕ contains an uncountable well-ordering, but ϕ is not the union of countably many well-orderings. It is proved that φ₄ ≠ 0, and a way is found of associating stationary sets with most of the types in φ₄ which is useful for applications. A number of results concerning the structure and embeddability properties of φ₄ are obtained, including some consistency and independence results. One consequence is the independence of Jensen's combinatorial principle □_ω1.     

Entropy numbers and interpolation

This paper settles a long-standing question by showing that in certain circumstances the entropy numbers of a map do not behave well under real interpolation. To do this, lemmas of combinatorial type are established and used to obtain lower bounds for the entropy numbers of a particular diagonal map acting between Lorentz sequence spaces. These lower bounds contradict the estimates from above that would be obtained if the behaviour of entropy numbers under real interpolation was as good as conjectured. The paper also provides sharp two-sided estimates of the entropy number e _n (T) of diagonal operators \({T:l_{p}\rightarrow l_{q}, T(\left( a_{k}\right)_{k=1}^{\infty}) = (( \lambda_{k}a_{k}) _{k=1}^{\infty}) ,}\) where 0 < p < q ≤ ∞ and \({\{\lambda _{i}\}_{i=1}^{\infty}}\) is a non-increasing sequence of non-negative numbers with λ _i  = λ _n for all i ≤ n.     

Coarse-grained entropy in dynamical systems

Let M be the phase space of a physical system. Consider the dynamics, determined by the invertible map T: M → M, preserving the measure µ on M. Let ν be another measure on M, dν = ρdµ. Gibbs introduced the quantity s(ρ) = ?∝ρ log ρdµ as an analog of the thermodynamical entropy. We consider a modification of the Gibbs (fine-grained) entropy the so called coarse-grained entropy. First we obtain a formula for the difference between the coarse-grained and Gibbs entropy. The main term of the difference is expressed by a functional usually referenced to as the Fisher information. Then we consider the behavior of the coarse-grained entropy as a function of time. The dynamics transforms ν in the following way: ν → ν _n , dν _n = ρ ○ T ^?n dµ. Hence, we obtain the sequence of densities ρ _n = ρ ○ T ^?n and the corresponding values of the Gibbs and the coarse-grained entropy. We show that while the Gibbs entropy remains constant, the coarse-grained entropy has a tendency to a growth and this growth is determined by dynamical properties of the map T. Finally, we give numerical calculation of the coarse-grained entropy as a function of time for systems with various dynamical properties: integrable, chaotic and with mixed dynamics and compare these calculation with theoretical statements.     

The combinatorics and extreme value statistics of protein threading

In protein threading, one is given a protein sequence, together with a database of protein core structures that may contain the natural structure of the sequence. The object of protein threading is to correctly identify the structure(s) corresponding to the sequence. Since the core structures are already associated with specific biological functions, threading has the potential to provide biologists with useful insights about the function of a newly discovered protein sequence. Statistical tests for threading results based on the theory of extreme values suggest several combinatorial problems. For example, what is the number of waysm′=# _t {L _i >x _i } _i ⁼⁰ⁿ of choosing a sequence {X _i } _i ⁼¹ⁿ from the set {1, 2, ...,t}, subject to the difference constraints {L _i =X _i+1?X _i >x _i } _i ⁼⁰ⁿ , whereX ₀=0,X _n+1=t+1, and {x _i } _i ⁼⁰ⁿ is an arbitrary sequence of integers? The quantitym′ has many attractive combinatorial interpretations and reduces in special continuous limits to a probabilistic formula discovered by the Finetti. Just as many important probabilities can be derived from de Finetti's formula, many interesting combinatorial quantities can be derived fromm′. Empirical results presented here show that the combinatorial approach to threading statistics appears promising, but that structural periodicities in proteins and energetically unimportant structure elements probably introduce statistical correlations that must be better understood.     

The Density of States Measure of the Weakly Coupled Fibonacci Hamiltonian

We consider the density of states measure of the Fibonacci Hamiltonian and show that, for small values of the coupling constant V, this measure is exact-dimensional and the almost everywhere value d _V of the local scaling exponent is a smooth function of V, is strictly smaller than the Hausdorff dimension of the spectrum, and converges to one as V tends to zero. The proof relies on a new connection between the density of states measure of the Fibonacci Hamiltonian and the measure of maximal entropy for the Fibonacci trace map on the non-wandering set in the V-dependent invariant surface. This allows us to make a connection between the spectral problem at hand and the dimension theory of dynamical systems.     

On marginal distributions and isomorphisms of stationary processes

LetT be an invertible ergodic aperiodic measure preserving transformation of a Lebesgue space, letA be a finite alphabet, and let π be a probability measure onA ⁿ which admits a mixing shift-invariant measureμ _π onΩ=A ^? such that the marginals of anyn successive coordinates are π and the entropyh(T) ofT is smaller than the entropy of the shift in (Ω,μ _π). Then there exists a shift invariant measure ν_π in Ω which also has marginals π and for whichT is isomorphic to the shift in (Ω, ν_π). This contains Krieger's finite generator theorem and strengthens the measure theoretic part of his approximation theorem for shift-invariant measures by showing that the preassigned marginal π can not only be achieved up to an ε>0 but exactly. Our result also contains an as yet unpublished theorem of Krieger, which says thatT can be embedded in an arbitrary mixing subshift of finite type, as long as the entropy of the subshift under the measure with maximal entropy exceeds that ofT. In the final section we show that the method can be extended to yield also exact marginals for the generator in the Jewett-Krieger theorem, i.e.T is shown to be isomorphic to a shift in (Ω, ν_π) where ν_π has exact marginals π and the shift is uniquely ergodic on the support of ν_π.     

Some Combinatorics of the Hypergeometric Series

Symmetry formulas for the classical hypergeometric series ₂F₁ are proved combinatorially. The idea of the proofs is to find weighted combinatorial structures which form models for each side of the formula and to show how to go from the first to the second model by a ‘weak isomorphism’ (i.e. a sequence of isomorphisms, regroupings and degroupings of structures). This is then applied to the four ₂F₁-families (Meixner, Krawtchouk, Meixner-Pollaczek and Jacobi) of hypergeometric orthogonal polynomials. We give three ‘weakly isomorphic’ models for each family and prove in a completely combinatorial way the 3-terms recurrences for these polynomials.     

Restrictions of continuous functions

Let α = {α₁, ...,α_k} be a finite multiset of non-negative real numbers. Consider the sequence of all positive integer multiples of all α _i ’s, and note the multiplicity of each term in this sequence. This sequence of multiplicities is the resonance sequence generated by {α ₁, ...,α_k}. Two multisets are combinatiorially equivalent if they generate the same resonance sequence. The paper is devoted to the classification of multisets up to combinatorial equivalence. We show that the problem of combinatorial equivalence of multisets is closely related to the problem of classification of systems of second order ordinary differential equations up to focal equivalence.     

Some quasinilpotent generators of the hyperfinite II1 factor

For each sequence n{cn} in l₁(N) we define an operator A in the hyperfinite II₁-factor R. We prove that these operators are quasinilpotent and they generate the whole hyperfinite II₁-factor. We show that they have non-trivial, closed, invariant subspaces affiliated to the von Neumann algebra and we provide enough evidence to suggest that these operators are interesting for the hyperinvariant subspace problem. We also present some of their properties. In particular, we show that the real and imaginary part of A are equally distributed, and we find a combinatorial formula as well as an analytical way to compute their moments. We present a combinatorial way of computing the moments of A^∗A.     

A criterion for algebraic dependence of transcendental numbers

We obtain a theorem concerning the algebraic dependence of the p+1 numbersθ,θ ₁ ...θ _p subject to the condition that the numbersθ ₁ , ...,θ _p are algebraically independent and possess a “sufficiently good” estimate of measure of algebraic independence.     

Edge distribution and density in the characteristic sequence

The characteristic sequence of hypergraphs 〈P_n:n<ω〉 associated to a formula φ(x;y), introduced in Malliaris (2010) [5], is defined by P_n(y₁,…,y_n)=(∃x)?_i≤nφ(x;y_i). We continue the study of characteristic sequences, showing that graph-theoretic techniques, notably Szemerédi’s celebrated regularity lemma, can be naturally applied to the study of model-theoretic complexity via the characteristic sequence. Specifically, we relate classification-theoretic properties of φ and of the P_n (considered as formulas) to density between components in Szemerédi-regular decompositions of graphs in the characteristic sequence. In addition, we use Szemerédi regularity to calibrate model-theoretic notions of independence by describing the depth of independence of a constellation of sets and showing that certain failures of depth imply Shelah’s strong order property SOP₃; this sheds light on the interplay of independence and order in unstable theories.     

Stability of Riemann solutions with large oscillation for the relativistic Euler equations

We are concerned with entropy solutions of the 2×2 relativistic Euler equations for perfect fluids in special relativity. We establish the uniqueness of Riemann solutions in the class of entropy solutions in L^∞∩BV_loc with arbitrarily large oscillation. Our proof for solutions with large oscillation is based on a detailed analysis of global behavior of shock curves in the phase space and on special features of centered rarefaction waves in the physical plane for this system. The uniqueness result does not require specific reference to any particular method for constructing the entropy solutions. Then the uniqueness of Riemann solutions yields their inviscid large-time stability under arbitrarily largeL¹∩L^∞∩BV_loc perturbation of the Riemann initial data, as long as the corresponding solutions are in L^∞ and have local bounded total variation that allows the linear growth in time. We also extend our approach to deal with the uniqueness and stability of Riemann solutions containing vacuum in the class of entropy solutions in L^∞ with arbitrarily large oscillation.     

A special class of polynomials orthogonal on the unit circle including the associated polynomials

Let (P _ν) be a sequence of monic polynomials orthogonal on the unit circle with respect to a nonnegative weight function, let (Ω_υ) the monic associated polynomials of (P _v), and letA andB be self-reciprocal polynomials. We show that the sequence of polynomials (AP_υλ+BΩ_υλ)/A^λ, λ stuitably determined, is a sequence of orthogonal polynomials having, up to a multiplicative complex constant, the same recurrence coefficients as theP _ν's from a certain index value onward, and determine the orthogonality measure explicity. Conversely, it is also shown that every sequence of orthogonal polynomials on the unit circle having the same recurrence coefficients from a certain index value onward is of the above form. With the help of these results an explicit representation of the associated polynomials of arbitrary order ofP _ν and of the corresponding orthogonality measure and Szegö function is obtained. The asymptotic behavior of the associated polynomials is also studied. Finally necessary and suficient conditions are given such that the measure to which the above introduced polynomials are orthogonal is positive.     

On the measure with maximal entropy for the Teichmüller flow on the moduli space of Abelian differentials

The Teichmüller flow g _t on the moduli space of Abelian differentials with zeros of given orders on a Riemann surface of a given genus is considered. This flow is known to preserve a finite absolutely continuous measure and is ergodic on every connected component ? of the moduli space. The main result of the paper is that µ/µ(?) is the unique measure with maximal entropy for the restriction of g _t to ?. The proof is based on the symbolic representation of g _t .     

Solving the car sequencing problem via Branch & Bound

In a mixed-model assembly line, varying models of the same basic product are to be produced in a facultative sequence. This results to a short-term planning problem where a sequence of models is sought which minimizes station overloads. In practice – e.g. the final assembly of cars – special sequencing rules are enforced which restrict the number of models possessing a certain optional feature k to r_k within a subsequence of s_k successive models. This problem is known as car sequencing. So far, employed solution techniques stem mainly from the field of Logic and Constraint Logic Programming. In this work, a special Branch & Bound algorithm is developed, which exploits the problem structure in order to reduce combinatorial complexity.     

Modified linear dependence and the capacity of a cyclic graph

In 1956 Shannon raised a problem in information theory, which amounts to this geometric question: How many n-dimensional cubes of width 2 can be packed in the n-dimensional torus described by the nth power of the cyclic group C_m? The present paper examines this question in the special circumstance that the set of centers of the cubes form a subgroup—that is, a lattice packing. In this case, the machinery of vector spaces is available when m is a prime. This approach introduces a modified definition of linear independence, obtains some known results with its aid, and suggests a promising direction for future computation and theory. The paper concludes by showing that, in return, combinatorial information can yield results about finite vector spaces.