VC dimension and inner product space induced by Bayesian networks

Bayesian networks are graphical tools used to represent a high-dimensional probability distribution. They are used frequently in machine learning and many applications such as medical science. This paper studies whether the concept classes induced by a Bayesian network can be embedded into a low-dimensional inner product space. We focus on two-label classification tasks over the Boolean domain. For full Bayesian networks and almost full Bayesian networks with n variables, we show that VC dimension and the minimum dimension of the inner product space induced by them are 2ⁿ-1. Also, for each Bayesian network we show that if the network constructed from by removing X_n satisfies either (i) is a full Bayesian network with n-1 variables, i is the number of parents of X_n, and i<n-1 or (ii) is an almost full Bayesian network, the set of all parents of X_n PA_n={X₁,X₂,X_n3,…,X_ni} and 2i<n-1. Our results in the paper are useful in evaluating the VC dimension and the minimum dimension of the inner product space of concept classes induced by other Bayesian networks.     

Precise asymptotics in the self-normalized law of the iterated logarithm

Let X,X₁,X₂,… be i.i.d. nondegenerate random variables with zero means, and . We investigate the precise asymptotics in the law of the iterated logarithm for self-normalized sums, S_n/V_n, also for the maximum of self-normalized sums, max_1kn|S_k|/V_n, when X belongs to the domain of attraction of the normal law.     

An Erdo&#x030B;s–Ko–Rado Theorem for Direct Products

Letn_i, k_ibe positive integers,i=1, ..., d,satisfyingn_i≥2k_i.LetX₁, ..., X_dbe pairwise disjoint sets with |X_i| =n_i.Letbe the family of those (k₁+···+k_d)-element sets which have exactlyk_ielements inX_i, i=1,..., d.It is shown that if⊂is an intersecting family then ||/||≤max_ik_i/n_i,and this is best possible. The proof is algebraic, although in thed=2 case a combinatorial argument is presented as well.     

Varieties of modules for

Let k be an algebraically closed field of characteristic 2. We prove that the restricted nilpotent commuting variety , that is the set of pairs of (n×n)-matrices (A,B) such that A²=B²=[A,B]=0, is equidimensional. can be identified with the ‘variety of n-dimensional modules’ for , or equivalently, for k[X,Y]/(X²,Y²). On the other hand, we provide an example showing that the restricted nilpotent commuting variety is not equidimensional for fields of characteristic >2. We also prove that if e²=0 then the set of elements of the centralizer of e whose square is zero is equidimensional. Finally, we express each irreducible component of as a direct sum of indecomposable components of varieties of -modules.     

Problems arising from jackknifing the estimate of a Kaplan-Meier integral

Stute and Wang (1994) considered the problem of estimating the integral S^θ = ∫ θ dF, based on a possibly censored sample from a distribution F, where θ is an F-integrable function. They proposed a Kaplan-Meier integral to approximate S^θ and derived an explicit formula for the delete-1 jackknife estimate . differs from only when the largest observation, X_(n), is not censored (δ_(n) = 1 and next-to-the-largest observation, X_(n-1), is censored (δ_(n-1) = 0). In this note, it will pointed out that when X_(n) is censored is based on a defective distribution, and therefore can badly underestimate . We derive an explicit formula for the delete-2 jackknife estimate . However, on comparing the expressions of and , their difference is negligible. To improve the performance of and , we propose a modified estimator according to Efron (1980). Simulation results demonstrate that is much less biased than and and .     

Numerical boundaries for some classical Banach spaces

Globevnik gave the definition of boundary for a subspace . This is a subset of Ω that is a norming set for . We introduce the concept of numerical boundary. For a Banach space X, a subset BΠ(X) is a numerical boundary for a subspace if the numerical radius of f is the supremum of the modulus of all the evaluations of f at B, for every f in . We give examples of numerical boundaries for the complex spaces X=c₀, and d_*(w,1), the predual of the Lorentz sequence space d(w,1). In all these cases (if K is infinite) we show that there are closed and disjoint numerical boundaries for the space of the functions from B_X to X which are uniformly continuous and holomorphic on the open unit ball and there is no minimal closed numerical boundary. In the case of c₀, we characterize the numerical boundaries for that space of holomorphic functions.     

Norms of some operators on the Bergman and the Hardy space in the unit polydisk and the unit ball

Let H(X) be the class of all holomorphic functions on the set and uH(X). We calculate operator norms of the multiplication operators M_u(f)=uf, on the weighted Bergman space , as well as on the Hardy space H^p(X), where X is the unit polydisk or the unit ball in . We also calculate the norm of the weighted composition operator from the weighted Bergman space , and the Hardy space , to a weighted-type space on the unit polydisk.     

Quadratic and cubic invariants of unipotent affine automorphisms

Let K be an arbitrary field of characteristic zero, P_n:=K[x₁,…,x_n] be a polynomial algebra, and , for n2. Let σ^′Aut_K(P_n) be given by

It is proved that the algebra of invariants, , is a polynomial algebra in n−1 variables which is generated by quadratic and cubic (free) generators that are given explicitly.Let σAut_K(P_n) be given by

It is well known that the algebra of invariants, , is finitely generated (theorem of Weitzenböck [R. Weitzenböck, Über die invarianten Gruppen, Acta Math. 58 (1932) 453–494]), has transcendence degree n−1, and that one can give an explicit transcendence basis in which the elements have degrees 1,2,3,…,n−1. However, it is an old open problem to find explicit generators for F_n. We find an explicit vector space basis for the quadratic invariants, and prove that the algebra of invariants is a polynomial algebra over in n−2 variables which is generated by quadratic and cubic (free) generators that are given explicitly.The coefficients of these quadratic and cubic invariants throw light on the ‘unpredictable combinatorics’ of invariants of affine automorphisms and of SL₂-invariants.     

Erdős–Ko–Rado theorems for permutations and set partitions

Let Sym([n]) denote the collection of all permutations of [n]={1,…,n}. Suppose is a family of permutations such that any two of its elements (when written in its cycle decomposition) have at least t cycles in common. We prove that for sufficiently large n, with equality if and only if is the stabilizer of t fixed points. Similarly, let denote the collection of all set partitions of [n] and suppose is a family of set partitions such that any two of its elements have at least t blocks in common. It is proved that, for sufficiently large n, with equality if and only if consists of all set partitions with t fixed singletons, where B_n is the nth Bell number.     

A supplement to the Davis–Gut law

Let {X,X_n;n1} be a sequence of i.i.d. real-valued random variables and set , n1. Let h() be a positive nondecreasing function such that . Define Lt=log_emax{e,t} for t0. In this note we prove that

if and only if E(X)=0 and E(X²)=1, where , t1. When h(t)≡1, this result yields what is called the Davis–Gut law. Specializing our result to h(t)=(Lt)^r, 0<r1, we obtain an analog of the Davis–Gut law.     

Interpolation and approximation in

Assume a standard Brownian motion W=(W_t)_t[0,1], a Borel function such that f(W₁)L₂, and the standard Gaussian measure γ on the real line. We characterize that f belongs to the Besov space , obtained via the real interpolation method, by the behavior of , where is a deterministic time net and the orthogonal projection onto a subspace of ‘discrete’ stochastic integrals with X being the Brownian motion or the geometric Brownian motion. By using Hermite polynomial expansions the problem is reduced to a deterministic one. The approximation numbers a_X(f(X₁);τ) can be used to describe the L₂-error in discrete time simulations of the martingale generated by f(W₁) and (in stochastic finance) to describe the minimal quadratic hedging error of certain discretely adjusted portfolios.     

Sparse inertially arbitrary patterns

An n-by-n sign pattern is a matrix with entries in {+,-,0}. An n-by-n nonzero pattern is a matrix with entries in {*,0} where * represents a nonzero entry. A pattern is inertially arbitrary if for every set of nonnegative integers n₁,n₂,n₃ with n₁+n₂+n₃=n there is a real matrix with pattern having inertia (n₁,n₂,n₃). We explore how the inertia of a matrix relates to the signs of the coefficients of its characteristic polynomial and describe the inertias allowed by certain sets of polynomials. This information is useful for describing the inertia of a pattern and can help show a pattern is inertially arbitrary. Britz et al. [T. Britz, J.J. McDonald, D.D. Olesky, P. van den Driessche, Minimal spectrally arbitrary sign patterns, SIAM J. Matrix Anal. Appl. 26 (2004) 257–271] conjectured that irreducible spectrally arbitrary patterns must have at least 2n nonzero entries; we demonstrate that irreducible inertially arbitrary patterns can have less than 2n nonzero entries.     

Transcendence of Binomial and Lucas' Formal Power Series

The formal power series[formula]is transcendental over (X) whentis an integer ≥ 2. This is due to Stanley forteven, and independently to Flajolet and to Woodcock and Sharif for the general case. While Stanley and Flajolet used analytic methods and studied the asymptotics of the coefficients of this series, Woodcock and Sharif gave a purely algebraic proof. Their basic idea is to reduce this series modulo prime numbersp, and to use thep-Lucas property: ifn = ∑n_ipⁱis the basepexpansion of the integern, then[equation]The series reduced modulopis then proved algebraic over _p(X), the field of rational functions over the Galois field _p, but its degree is not a bounded function ofp. We generalize this method to characterize all formal power series that have thep-Lucas property for “many” prime numbersp, and that are furthermore algebraic over (X).     

On the Spaltenstein correspondence

In the article [Spa1], N. Spaltenstein has established a bijection between the irreducible components of _χ, the space of full flags fixed by a nilpotent element χ ? M(n, k), where k is an algebraically closed field, and the standard tableaux associated to the Young diagram of χ. In this present work we determine, when χ is of hook type, for each irreducible component X of _χ, the unique Schubert cell _X of the full flag manifold = (V) (where V is vector space of dimension n over k), such that X ∩ _X is a dense subspace in X. This result will allow us to optimize the computation of _χ and when k = is the complex field, to see that the graph resolution of the partition (2, 1, …, 1) of n is related to the Dynkin diagram of sl(n, ).     

Properties of multilevel block -circulants

In a previous paper we characterized unilevel block α-circulants , , 0mn-1, in terms of the discrete Fourier transform of , defined by . We showed that most theoretical and computational problems concerning A can be conveniently studied in terms of corresponding problems concerning the Fourier coefficients F₀,F₁,…,F_n-1 individually. In this paper we show that analogous results hold for (k+1)-level matrices, where the first k levels have block circulant structure and the entries at the (k+1)-st level are unstructured rectangular matrices.     

The statistical distribution of the zeros of random paraorthogonal polynomials on the unit circle

The orthogonal polynomials on the unit circle are defined by the recurrence relation

where for any k0. If we consider n complex numbers and , we can use the previous recurrence relation to define the monic polynomials Φ₀,Φ₁,…,Φ_n. The polynomial Φ_n(z)=Φ_n(z;α₀,…,α_n-2,α_n-1) obtained in this way is called the paraorthogonal polynomial associated to the coefficients α₀,α₁,…,α_n-1.We take α₀,α₁,…,α_n-2 i.i.d. random variables distributed uniformly in a disk of radius r<1 and α_n-1 another random variable independent of the previous ones and distributed uniformly on the unit circle. For any n we will consider the random paraorthogonal polynomial Φ_n(z)=Φ_n(z;α₀,…,α_n-2,α_n-1). The zeros of Φ_n are n random points on the unit circle.We prove that for any the distribution of the zeros of Φ_n in intervals of size near e^iθ is the same as the distribution of n independent random points uniformly distributed on the unit circle (i.e., Poisson). This means that, for large n, there is no local correlation between the zeros of the considered random paraorthogonal polynomials.     

Slope-changing solutions of elliptic problems on

We consider the problem on , where F is a smooth function periodic of period 1 in all its variables. We are going to find a non-degeneracy condition on F for which the following holds. If we are given a sequence of positive integers and a sequence of real numbers (the slopes), then we shall find an increasing sequence {Q_i} of integers and a solution u which is entire, periodic in (x₂,…,x_n) and which is close to the plane α₁(x₁−Q_i)+u(Q_i,0,…,0) for .     

Cycles in 2-connected graphs

Let be a class of graphs on n vertices. For an integer c, let be the smallest integer such that if G is a graph in with more than edges, then G contains a cycle of length more than c. A classical result of Erdös and Gallai is that if is the class of all simple graphs on n vertices, then . The result is best possible when n-1 is divisible by c-1, in view of the graph consisting of copies of K_c all having exactly one vertex in common. Woodall improved the result by giving best possible bounds for the remaining cases when n-1 is not divisible by c-1, and conjectured that if is the class of all 2-connected simple graphs on n vertices, thenwhere , 2tc/2, is the number of edges in the graph obtained from K_c+1-t by adding n-(c+1-t) isolated vertices each joined to the same t vertices of K_c+1-t. By using a result of Woodall together with an edge-switching technique, we confirm Woodall's conjecture in this paper.